Back to Search
Start Over
Balas formulation for the union of polytopes is optimal
- Source :
- Mathematical Programming. 180:311-326
- Publication Year :
- 2019
- Publisher :
- Springer Science and Business Media LLC, 2019.
-
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.
- Subjects :
- Convex hull
Polynomial
021103 operations research
90C10, 90C11, 52B55
General Mathematics
Numerical analysis
Dimension (graph theory)
0211 other engineering and technologies
Polytope
010103 numerical & computational mathematics
02 engineering and technology
01 natural sciences
Software
Mathematics (all)
Combinatorics
Optimization and Control (math.OC)
FOS: Mathematics
Mathematics::Metric Geometry
Relaxation (approximation)
0101 mathematics
Mathematics - Optimization and Control
Mathematics
Subjects
Details
- ISSN :
- 14364646 and 00255610
- Volume :
- 180
- Database :
- OpenAIRE
- Journal :
- Mathematical Programming
- Accession number :
- edsair.doi.dedup.....5f0f30baec856ee6baca4ce5807fb644