Polyhedra

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

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

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

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

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

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

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

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

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

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

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 are still gaps in both the theory and practice surrounding these methods. In the first part of this paper, we lay out a basic theory of valid inequalities and cutting-plane methods for MIBLPs that parallels the existing … Read more