Fetching the paper…

Reading the bibliography…

Finding Descriptions of Polytopes via Extended Formulations and Liftings · Around

2011

Finding Descriptions of Polytopes via Extended Formulations and Liftings

Kaibel, Volker, Loos, Andreas

Original
PDF
Post on X

Understand

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.

Built on

Some recent applications of the theory of linear inequations to extremal combinatorial analysis
Alan J. Hoffman · 1960
Earlier work this paper cites.
The path set polytope of an acyclic, directed graph with an application to machine sequencing
John H. Vande Vate · 1989
Earlier work this paper cites.
Combinatorial Matrix Theory
Richard A. Brualdi and Herbert John Ryser · 1991
Earlier work this paper cites.
Bounded stable sets: Polytopes and colorings
Jeannette Janssen and Kyriakos Kilakos · 1999
Earlier work this paper cites.

Similar

Combinatorial Optimization (Polyhedra and Efficiency)
Alexander Schrijver · 2004
Cited alongside, same era.
Packing and partitioning orbitopes
Volker Kaibel and Marc E. Pfetsch · 2008
Cited alongside, same era.
Extended formulations for packing and partitioning orbitopes
Yuri Faenza and Volker Kaibel · 2009
Cited alongside, same era.
Extended formulations in combinatorial optimization
Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli · 2010
Cited alongside, same era.

Then

Reformulation and decomposition of integer programs
Francois Vanderbeck and Laurence A. Wolsey · 2010
Later among the works it cites.
Extended formulations in combinatorial optimization
Volker Kaibel · 2011
Closest in time.
Describing Orbitopes by Linear Inequalities and Projection Based Tools
Andreas Loos · 2011
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…