Balas formulation for the union of polytopes is optimal
From MaRDI portal
Publication:2297650
DOI10.1007/s10107-018-01358-9zbMath1434.90102arXiv1711.00891OpenAlexW2963666922MaRDI QIDQ2297650
Michele Conforti, Marco Di Summa, Yuri Faenza
Publication date: 20 February 2020
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1711.00891
Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Mixed integer programming (90C11)
Related Items
Ideal, non-extended formulations for disjunctive constraints admitting a network representation, Shadows of Newton polytopes, Worst-case analysis of clique MIPs
Cites Work
- Relative Stanley-Reisner theory and upper bound theorems for Minkowski sums
- Lower bounds on the sizes of integer programs without additional variables
- Disjunctive programming: Properties of the convex hull of feasible points
- The Cayley trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings
- Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix
- On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space
- Small and strong formulations for unions of convex sets from the Cayley embedding
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- Mixed-integer linear representability, disjunctions, and variable elimination
- Approximate extended formulations
- Exponential Lower Bounds for Polytopes in Combinatorial Optimization
- Mixed Integer Linear Programming Formulation Techniques
- The maximum number of faces of the Minkowski sum of three convex polytopes
- Constructing Extended Formulations from Reflection Relations
- Extremal Combinatorics
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Integer Programming
- Modelling with integer variables
- Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations
- The Matching Polytope has Exponential Extension Complexity
- A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints
- Extended formulations in combinatorial optimization
