Polyhedra

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

    A Polyhedral Study for the Cubic Formulation of the Unconstrained Traveling Tournament Problem

  • Marije Siemann
  • Matthias Walter
    • Categories Applications - OR and Management Sciences, Polyhedra Tags ,

    We consider the unconstrained traveling tournament problem, a sports timetabling problem that minimizes traveling of teams. Since its introduction about 20 years ago, most research was devoted to modeling and reformulation approaches. In this paper we carry out a polyhedral study for the cubic integer programming formulation by establishing the dimension of the integer hull … Read more

    Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs

  • Matthias Walter
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , ,

    Cutting planes are a key ingredient to successfully solve mixed-integer linear programs. For specific problems, their strength is often theoretically assessed by showing that they are facet-defining for the corresponding mixed-integer hull. In this paper we experimentally investigate the dimensions of faces induced by general-purpose cutting planes generated by a state-of-the-art solver. Therefore, we relate … Read more

    Valid Inequalities for Mixed Integer Bilevel Linear Optimization Problems

  • Ted K. Ralphs
  • Sahar Tahernejad
    • Categories Cutting Plane Approaches, Game Theory, Polyhedra Tags , ,

    Despite the success of branch-and-cut methods for solving mixed integer bilevel linear optimization problems (MIBLPs) in practice, there have remained some gaps in the theory surrounding these methods. In this paper, we take a first step towards laying out a theory of valid inequalities and cutting-plane methods for MIBLPs that parallels the existing theory for … Read more