Lifting linear extension complexity bounds to the mixed-integer setting

zbMATH Open1410.90131arXiv1712.02176MaRDI QIDQ4607933FDOQ4607933

Authors: Alfonso Cevallos, Stefan Weltge, Rico Zenklusen 

Publication date: 15 March 2018

Abstract: Mixed-integer mathematical programs are among the most commonly used models for a wide set of problems in Operations Research and related fields. However, there is still very little known about what can be expressed by small mixed-integer programs. In particular, prior to this work, it was open whether some classical problems, like the minimum odd-cut problem, can be expressed by a compact mixed-integer program with few (even constantly many) integer variables. This is in stark contrast to linear formulations, where recent breakthroughs in the field of extended formulations have shown that many polytopes associated to classical combinatorial optimization problems do not even admit approximate extended formulations of sub-exponential size. We provide a general framework for lifting inapproximability results of extended formulations to the setting of mixed-integer extended formulations, and obtain almost tight lower bounds on the number of integer variables needed to describe a variety of classical combinatorial optimization problems. Among the implications we obtain, we show that any mixed-integer extended formulation of sub-exponential size for the matching polytope, cut polytope, traveling salesman polytope or dominant of the odd-cut polytope, needs $Omega(n/logn)$ many integer variables, where $n$ is the number of vertices of the underlying graph. Conversely, the above-mentioned polyhedra admit polynomial-size mixed-integer formulations with only $O(n)$ or $O(nlogn)$ (for the traveling salesman polytope) many integer variables. Our results build upon a new decomposition technique that, for any convex set $C$, allows for approximating any mixed-integer description of $C$ by the intersection of $C$ with the union of a small number of affine subspaces.

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

Recommendations

• Extension complexity lower bounds for mixed-integer extended formulations
• Extended formulations in combinatorial optimization
• Extended formulations in combinatorial optimization
• Network Formulations of Mixed-Integer Programs
• Cutting planes from extended LP formulations

zbMATH Keywords

extended formulationsextension complexitymixed-integer programs

Mathematics Subject Classification ID

Mixed integer programming (90C11)

Cited In (10)

• The integrality number of an integer program
• Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
• Lattice-free simplices with lattice width \(2d - o(d)\)
• Extension complexity lower bounds for mixed-integer extended formulations
• Extended formulations for stable set polytopes of graphs without two disjoint odd cycles
• Lifting, superadditivity, mixed integer rounding and single node flow sets revisited
• Extended formulations for radial cones
• Computational aspects of relaxation complexity: possibilities and limitations
• Efficient MIP techniques for computing the relaxation complexity
• Lattice closures of polyhedra

This page was built for publication: Lifting linear extension complexity bounds to the mixed-integer setting

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