Polyhedra

Multiple-Periods Locally-Facet-Based MIP Formulations for the Unit Commitment Problem

  • Linfeng Yang
  • Shifei Chen
  • Zhaoyang Dong
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Polyhedra Tags , , , , , , ,

    The thermal unit commitment (UC) problem has historically been formulated as a mixed integer quadratic programming (MIQP), which is difficult to solve efficiently, especially for large-scale systems. The tighter characteristic reduces the search space, therefore, as a natural consequence, significantly reduces the computational burden. In literatures, many tightened formulations for a single unit with parts … Read more

    Simple odd beta-cycle inequalities for binary polynomial optimization

  • Alberto Del Pia
  • Matthias Walter
    • Categories 0-1 Programming, Bound-constrained Optimization, Polyhedra Tags , ,

    We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd beta-cycle inequalities valid for this polytope, showed that these generally have Chvátal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle … Read more

    On Polytopes with Linear Rank with respect to Generalizations of the Split Closure

  • Sanjeeb Dash
  • Yatharth Dubey
    • Categories Cutting Plane Approaches, Polyhedra Tags , , , ,

    In this paper we study the rank of polytopes contained in the 0-1 cube with respect to $t$-branch split cuts and $t$-dimensional lattice cuts for a fixed positive integer $t$. These inequalities are the same as split cuts when $t=1$ and generalize split cuts when $t > 1$. For polytopes contained in the $n$-dimensional 0-1 … Read more

    Polyhedral Analysis of a Polytope from a Service Center Location Problem with a Special Decision-Dependent Customer Demand

  • Fengqiao Luo
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Polyhedra Tags , , ,

    This paper establishes and analyzes a service center location model with a simple but novel decision-dependent demand induced from a maximum attraction principle. The model formulations are investigated in the distributionally-robust optimization framework for the capacitated and uncapacitated cases. A statistical model that is based on the maximum attraction principle for estimating customer demand and … Read more

    On the Polyhedrality of the Chvatal-Gomory Closure

  • Haoran Zhu
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , ,

    In this paper, we provide an equivalent condition for the Chvatal-Gomory (CG) closure of a closed convex set to be finitely-generated. Using this result, we are able to prove that, for any closed convex set that can be written as the Minkowski sum of a compact convex set and a closed convex cone, its CG … Read more

    Algorithms for the Clique Problem with Multiple-Choice Constraints under a Series-Parallel Dependency Graph

  • Andreas Bärmann
  • Patrick Gemander
  • Maximilian Merkert
  • Ann-Kathrin Wiertz
  • Francisco Javier Zaragoza Martínez
    • Categories Dynamic Programming, Graphs and Matroids, Polyhedra Tags , , , ,

    The clique problem with multiple-choice constraints (CPMC), i.e. the problem of finding a k-clique in a k-partite graph with known partition, occurs as a substructure in many real-world applications, in particular scheduling and railway timetabling. Although CPMC is NP-complete in general, it is known to be solvable in polynomial time when the so-called dependency graph … Read more

    Total Coloring and Total Matching: Polyhedra and Facets

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

    A total coloring of a graph G = (V, E) is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the end-points and the edge itself receive a different color. Any valid total coloring induces a partition of … Read more

    Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints

  • Simge Küçükyavuz
  • Qimeng Yu
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Polyhedra Tags , ,

    We study the polyhedral convex hull structure of a mixed-integer set which arises in a class of cardinality-constrained concave submodular minimization problems. This class of problems has an objective function in the form of $f(a^\top x)$, where $f$ is a univariate concave function, $a$ is a non-negative vector, and $x$ is a binary vector of … Read more

    Set characterizations and convex extensions for geometric convex-hull proofs

  • Andreas Bärmann
  • Oskar Schneider
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Polyhedra Tags , , , ,

    In the present work, we consider Zuckerberg’s method for geometric convex-hull proofs introduced in [Geometric proofs for convex hull defining formulations, Operations Research Letters 44(5), 625–629 (2016)]. It has only been scarcely adopted in the literature so far, despite the great flexibility in designing algorithmic proofs for the completeness of polyhedral descriptions that it offers. … Read more

    Polyhedral Analysis of Symmetric Multilinear Polynomials over Box Constraints

  • Warren Adams
  • Akshay Gupte
  • Yibo Xu
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra Tags , , , ,

    It is well-known that the convex and concave envelope of a multilinear polynomial over a box are polyhedral functions. Exponential-sized extended and projected formulations for these envelopes are also known. We consider the convexification question for multilinear polynomials that are symmetric with respect to permutations of variables. Such a permutation-invariant structure naturally implies a quadratic-sized … Read more