Polyhedra

Relating Single-Scenario Facets to the Convex Hull of the Extensive Form of a Stochastic Single-Node Flow Polytope

  • Victor A. Gonzalez
  • Andrew J. Schaefer
  • Mehdi Hemmati
  • David T. Mildebrath
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Stochastic Programming Tags , ,

    Stochastic mixed-integer programs (SMIPs) are a widely-used modeling paradigm for sequential decision making under uncertainty. One popular solution approach to solving SMIPs is to solve the so-called “extensive form” directly as a large-scale (deterministic) mixed-integer program. In this work, we consider the question of when a facet-defining inequality for the convex hull of a deterministic, … Read more

    Decomposing the Train Scheduling Problem into Integer Optimal Polytopes

  • Masoud Barah
  • James Ostrowski
  • Abbas Seifi
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Transportation Tags , ,

    This paper presents conditions for which the linear relaxation for the train scheduling problem is integer-optimal. These conditions are then used to identify how to partition a general problem’s feasible region into integer-optimal polytopes. Such an approach yields an extended formulation that contains far fewer binary variables. Our computational experiments show that this approach results … Read more

    Equivalences among the chi measure, Hoffman constant, and Renegar’s distance to ill-posedness

  • Javier F. Peña
  • Juan C. Vera
  • Luis F. Zuluaga
    • Categories Convex Optimization, Linear Programming, Polyhedra Tags , , , ,

    We show the equivalence among the following three condition measures of a full column rank matrix $A$: the chi measure, the signed Hoffman constant, and the signed distance to ill-posedness. The latter two measures are constructed via suitable collections of matrices obtained by flipping the signs of some rows of $A$. Our results provide a … Read more

    New characterizations of Hoffman constants for systems of linear constraints

  • Javier F. Peña
  • Juan C. Vera
  • Luis F. Zuluaga
    • Categories Convex Optimization, Polyhedra Tags , ,

    We give a characterization of the Hoffman constant of a system of linear constraints in $\R^n$ relative to a reference polyhedron $R\subseteq\R^n$. The reference polyhedron $R$ represents constraints that are easy to satisfy such as box constraints. In the special case $R = \R^n$, we obtain a novel characterization of the classical Hoffman constant. More … Read more

    Knapsack Polytopes – A Survey

  • Tristan Gally
  • Oliver Habeck
  • Christopher Hojny
  • Frederic Matter
  • Marc E. Pfetsch
  • Andreas Schmitt
  • Hendrik Lüthen
    • Categories 0-1 Programming, Polyhedra Tags , , , , ,

    The 0/1 knapsack polytope is the convex hull of all 0/1 vectors that satisfy a given single linear inequality with non-negative coefficients. This paper provides a comprehensive overview of knapsack polytopes. We discuss basic polyhedral properties, (lifted) cover and other valid inequalities, cases for which complete linear descriptions are known, geometric properties for small dimensions, … Read more

    A Linear Programming Based Approach to the Steiner Tree Problem with a Fixed Number of Terminals

  • Shabbir Ahmed
  • George L. Nemhauser
  • Matias Siebert
    • Categories Linear Programming, Network Optimization, Polyhedra Tags , , ,

    We present a set of integer programs (IPs) for the Steiner tree problem with the property that the best solution obtained by solving all, provides an optimal Steiner tree. Each IP is polynomial in the size of the underlying graph and our main result is that the linear programming (LP) relaxation of each IP is … Read more

    On prime and minimal representations of a face of a polyhedron

  • Ta Van Van Tu
    • Categories Combinatorial Optimization, Multi-Criteria Optimization, Polyhedra

    In this paper, a new method for determining all minimal representations of a face of a polyhedron is proposed. A main difficulty for determining prime and minimal representations of a face is that the deletion of one redundant constraint can change the redundancy of other constraints. To reduce computational efforts in finding all minimal representations … Read more

    Strong Mixed-Integer Formulations for Power System Islanding and Restoration

  • Ignacio Aravena
  • Shmuel Oren
  • Deepak Rajan
  • Georgios Patsakis
    • Categories Branch and Cut Algorithms, Integer Programming, Polyhedra Tags , , , , ,

    The Intentional Controlled Islanding (ICI) and the Black Start Allocation (BSA) are two examples of problems in the power systems literature that have been formulated as Mixed Integer Programs (MIPs). A key consideration in both of these problems is that each island must have at least one energized generator. In this paper, we provide three … Read more

    Exploiting Partial Correlations in Distributionally Robust Optimization

  • Karthyek Murthy
  • Karthik Natarajan
  • Divya Padmanabhan
    • Categories Polyhedra, Robust Optimization, Semi-definite Programming Tags , , ,

    In this paper, we identify partial correlation information structures that allow for simpler reformulations in evaluating the maximum expected value of mixed integer linear programs with random objective coefficients. To this end, assuming only the knowledge of the mean and the covariance matrix entries restricted to block-diagonal patterns, we develop a reduced semidefinite programming formulation, … Read more

    Tight MIP formulations for bounded length cyclic sequences

  • Thomas Kalinowski
  • Tomas Lidén
  • Hamish Waterer
    • Categories 0-1 Programming, Polyhedra, Scheduling

    We study cyclic binary strings with bounds on the lengths of the intervals of consecutive ones and zeros. This is motivated by scheduling problems where such binary strings can be used to represent the state (on/off) of a machine. In this context the bounds correspond to minimum and maximum lengths of on- or off-intervals, and … Read more