Integer Programming

Tight and Compact MIP Formulation of Configuration-Based Combined-Cycle Units

  • Carlos M. Correa-Posada
  • Germán Morales-España
  • Andres Ramos
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , ,

    Private investors, flexibility, efficiency and environmental requirements from deregulated markets have led the existence and building of a significant number of combined-cycle gas turbines (CCGTs) in many power systems. These plants represent a complicated optimization problem for the short-term planning unit commitment (UC) carried out by independent system operators due to their multiple operating configurations. … Read more

    Maximal Covering Location Problems on networks with regional demand

  • Rafael Blanquero
  • Emilio Carrizosa
  • Boglárka Tóth
    • Categories (Mixed) Integer Nonlinear Programming, Facility Planning and Design, Global Optimization Tags , , , ,

    Covering problems are well studied in the Operations Research literature under the assumption that both the set of users and the set of potential facilities are finite. In this paper we address the following variant, which leads to a Mixed Integer Nonlinear Program (MINLP): locations of p facilities are sought along the edges of a … Read more

    Scenario-Tree Decomposition: Bounds for Multistage Stochastic Mixed-Integer Programs

  • Oleg A. Prokopyev
  • Andrew J. Schaefer
  • Gabriel L. Zenarosa
    • Categories Integer Programming, Parallel Algorithms, Stochastic Programming Tags , ,

    Multistage stochastic mixed-integer programming is a powerful modeling paradigm appropriate for many problems involving a sequence of discrete decisions under uncertainty; however, they are difficult to solve without exploiting special structures. We present scenario-tree decomposition to establish bounds for unstructured multistage stochastic mixed-integer programs. Our method decomposes the scenario tree into a number of smaller … Read more

    On a nonconvex MINLP formulation of the Euclidean Steiner tree problems in n-space

  • Claudia D'Ambrosio
  • Marcia Fampa
  • Jon Lee
  • Stefan Vigerske
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Global Optimization Tags , ,

    The Euclidean Steiner Tree Problem in dimension greater than two is notoriously difficult. The successful methods for exact solution are not based on mathematical-optimization methods — rather, they involve very sophisticated enumeration. There are two types of mathematical-optimization formulations in the literature, and it is an understatement to say that neither scales well enough to … Read more

    An SDP approach for multiperiod mixed 0–1 linear programming models with stochastic dominance constraints for risk management

  • Laureano F. Escudero
  • Dolores Romero Morales
  • Juan F. Monge
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming, Supply Chain Management

    In this paper we consider multiperiod mixed 0–1 linear programming models under uncertainty. We propose a risk averse strategy using stochastic dominance constraints (SDC) induced by mixed-integer linear recourse as the risk measure. The SDC strategy extends the existing literature to the multistage case and includes both first-order and second-order constraints. We propose a stochastic … Read more

    An Exact Extended Formulation for the Unrelated Parallel Machine Total Weighted Completion Time Problem

  • Kerem Bülbül
  • Halil Sen
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Scheduling

    The plethora of research on NP-hard parallel machine scheduling problems is focused on heuristics due to the theoretically and practically challenging nature of these problems. Only a handful of exact approaches are available in the literature, and most of these suffer from scalability issues. Moreover, the majority of the papers on the subject are restricted … Read more

    On the exact separation of rank inequalities for the maximum stable set problem

  • Stefano Coniglio
  • Stefano Gualandi
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , , , , ,

    When addressing the maximum stable set problem on a graph G = (V,E), rank inequalities prescribe that, for any subgraph G[U] induced by U ⊆ V , at most as many vertices as the stability number of G[U] can be part of a stable set of G. These inequalities are very general, as many of … Read more

    Discretization vertex orders in distance geometry

  • Andrea Cassioli
  • Oktay Gunluk
  • Carlile Lavor
  • Leo Liberti
    • Categories 0-1 Programming, Biomedical Applications, Combinatorial Optimization Tags , , , , ,

    When a weighted graph is an instance of the Distance Geometry Problem (DGP), certain types of vertex orders (called discretization orders) allow the use of a very efficient, precise and robust discrete search algorithm (called Branch-and-Prune). Accordingly, finding such orders is critically important in order to solve DGPs in practice. We discuss three types of … Read more

    Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane

  • Alberto Del Pia
  • Robert Hildebrand
  • Robert Weismantel
  • Kevin Zemmer
    • Categories (Mixed) Integer Nonlinear Programming Tags

    We complete the complexity classification by degree of minimizing a polynomial in two variables over the integer points in a polyhedron. Previous work shows that in two variables, optimizing a quadratic polynomial over the integer points in a polyhedral region can be done in polynomial time, while optimizing a quartic polynomial in the same type … Read more