Finding descriptions of polytopes via extended formulations and liftings
From MaRDI portal
Publication:3109936
zbMATH Open1263.90076arXiv1109.0815MaRDI QIDQ3109936FDOQ3109936
Authors: Volker Kaibel, Andreas Loos 
Publication date: 26 January 2012
Abstract: We describe a technique to obtain linear descriptions for polytopes from extended formulations. The simple idea is to first define a suitable lifting function and then to find linear constraints that are valid for the polytope and guarantee lifted points to be contained in the extension. We explain the technique at an example from the literature (matching polytopes), obtain new simple proofs of results on path-set polytopes and small-cliques polytopes, and finally exploit the technique in order to derive linear descriptions of orbisacks, which are special Knapsack polytopes arising in the context of symmetry breaking in integer programming problems.
Full work available at URL: https://arxiv.org/abs/1109.0815
Recommendations
- Extended formulations for packing and partitioning orbitopes
- An algebraic approach to symmetric extended formulations
- Describing orbitopes by linear inequalities and projection based tools.
- Extended formulations in combinatorial optimization
- Projection, lifting and extended formulation integer and combinatorial optimization
Cited In (7)
- Enabling research through the SCIP Optimization Suite 8.0
- Strong IP formulations need large coefficients
- Ideal, non-extended formulations for disjunctive constraints admitting a network representation
- Lexicographical order in integer programming
- Extended formulations for Gomory corner polyhedra
- Strong cuts from compatibility relations for the dial-a-ride problem
- On the extension complexity of polytopes separating subsets of the Boolean cube
This page was built for publication: Finding descriptions of polytopes via extended formulations and liftings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3109936)
