Balas formulation for the union of polytopes is optimal

DOI10.1007/S10107-018-01358-9zbMATH Open1434.90102arXiv1711.00891OpenAlexW2963666922WikidataQ128529136 ScholiaQ128529136MaRDI QIDQ2297650FDOQ2297650

Authors: 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)

Abstract: A celebrated theorem of Balas gives a linear mixed-integer formulation for the union of two nonempty polytopes whose relaxation gives the convex hull of this union. The number of inequalities in Balas formulation is linear in the number of inequalities that describe the two polytopes and the number of variables is doubled. In this paper we show that this is best possible: in every dimension there exist two nonempty polytopes such that if a formulation for the convex hull of their union has a number of inequalities that is polynomial in the number of inequalities that describe the two polytopes, then the number of additional variables is at least linear in the dimension of the polytopes. We then show that this result essentially carries over if one wants to approximate the convex hull of the union of two polytopes and also in the more restrictive setting of lift-and-project.

Full work available at URL: https://arxiv.org/abs/1711.00891

Recommendations

• On unions and dominants of polytopes
• Compact formulations as a union of polyhedra
• A simplification for some disjunctive formulations
• Tight formulations for some simple mixed integer programs and convex objective integer programs
• On the convex hull of the union of certain polyhedra

zbMATH Keywords

convex hulllift-and-project

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Mixed integer programming (90C11)

Cites Work

• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• Constructing extended formulations from reflection relations
• Extended formulations in combinatorial optimization
• Disjunctive programming: Properties of the convex hull of feasible points
• The Cayley trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings
• Modelling with integer variables
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Relative Stanley-Reisner theory and upper bound theorems for Minkowski sums
• Extremal combinatorics. With applications in computer science
• Exponential lower bounds for polytopes in combinatorial optimization
• Approximate extended formulations
• Integer Programming
• Mixed integer linear programming formulation techniques
• 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
• Extension complexity lower bounds for mixed-integer extended formulations
• Small and strong formulations for unions of convex sets from the Cayley embedding
• Mixed-integer linear representability, disjunctions, and variable elimination
• A combinatorial approach for small and strong formulations of disjunctive constraints
• The maximum number of faces of the Minkowski sum of three convex polytopes

Cited In (6)

• Extensions of a theorem of Balas
• On unions and dominants of polytopes
• Ideal, non-extended formulations for disjunctive constraints admitting a network representation
• A case when the union of polytopes is convex
• Worst-case analysis of clique MIPs
• Shadows of Newton polytopes

This page was built for publication: Balas formulation for the union of polytopes is optimal

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2297650)