Simple extensions of polytopes

Volker Kaibel, Matthias Walter

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

We introduce the simple extension complexity of a polytope $$P$$P as the smallest number of facets of any simple (i.e., non-degenerate in the sense of linear programming) polytope which can be projected onto $$P$$P. We devise a combinatorial method to establish lower bounds on the simple extension complexity and show for several polytopes that they have large simple extension complexities. These examples include both the spanning tree and the perfect matching polytopes of complete graphs, uncapacitated flow polytopes for non-trivially decomposable directed acyclic graphs, hypersimplices, and random 0/1-polytopes with vertex numbers within a certain range. On our way to obtain the result on perfect matching polytopes we generalize a result of Padberg and Rao’s on the adjacency structures of those polytopes. In addition to the material in the extended abstract (Kaibel and Walter in Integer programming and combinatorial optimization. Lecture Notes in Computer Science, vol 8494. Springer, Berlin, 2014) we include omitted proofs, supporting figures, and an analysis of known upper bounding techniques.

Original languageEnglish
Pages (from-to)381-406
Number of pages26
JournalMathematical programming
Volume154
Issue number1-2
DOIs
Publication statusPublished - 31 Mar 2015
Externally publishedYes

Fingerprint

Flow graphs
Combinatorial optimization
Integer programming
Polytopes
Linear programming
Computer science
Perfect Matching
Polytope
Directed Acyclic Graph
Adjacency
Combinatorial Optimization
Decomposable
Integer Programming
Spanning tree
Facet
Complete Graph
Figure
Computer Science
Lower bound
Generalise

Keywords

  • Extended formulations
  • Flow polytopes
  • Matching polytopes
  • Simple polytopes
  • Spanning tree polytopes

Cite this

Kaibel, Volker ; Walter, Matthias. / Simple extensions of polytopes. In: Mathematical programming. 2015 ; Vol. 154, No. 1-2. pp. 381-406.
@article{0dd1df44d1f74d2d8a5893e43d8b0a11,
title = "Simple extensions of polytopes",
abstract = "We introduce the simple extension complexity of a polytope $$P$$P as the smallest number of facets of any simple (i.e., non-degenerate in the sense of linear programming) polytope which can be projected onto $$P$$P. We devise a combinatorial method to establish lower bounds on the simple extension complexity and show for several polytopes that they have large simple extension complexities. These examples include both the spanning tree and the perfect matching polytopes of complete graphs, uncapacitated flow polytopes for non-trivially decomposable directed acyclic graphs, hypersimplices, and random 0/1-polytopes with vertex numbers within a certain range. On our way to obtain the result on perfect matching polytopes we generalize a result of Padberg and Rao’s on the adjacency structures of those polytopes. In addition to the material in the extended abstract (Kaibel and Walter in Integer programming and combinatorial optimization. Lecture Notes in Computer Science, vol 8494. Springer, Berlin, 2014) we include omitted proofs, supporting figures, and an analysis of known upper bounding techniques.",
keywords = "Extended formulations, Flow polytopes, Matching polytopes, Simple polytopes, Spanning tree polytopes",
author = "Volker Kaibel and Matthias Walter",
year = "2015",
month = "3",
day = "31",
doi = "10.1007/s10107-015-0885-2",
language = "English",
volume = "154",
pages = "381--406",
journal = "Mathematical programming",
issn = "0025-5610",
publisher = "Springer",
number = "1-2",

}

Simple extensions of polytopes. / Kaibel, Volker; Walter, Matthias.

In: Mathematical programming, Vol. 154, No. 1-2, 31.03.2015, p. 381-406.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Simple extensions of polytopes

AU - Kaibel, Volker

AU - Walter, Matthias

PY - 2015/3/31

Y1 - 2015/3/31

N2 - We introduce the simple extension complexity of a polytope $$P$$P as the smallest number of facets of any simple (i.e., non-degenerate in the sense of linear programming) polytope which can be projected onto $$P$$P. We devise a combinatorial method to establish lower bounds on the simple extension complexity and show for several polytopes that they have large simple extension complexities. These examples include both the spanning tree and the perfect matching polytopes of complete graphs, uncapacitated flow polytopes for non-trivially decomposable directed acyclic graphs, hypersimplices, and random 0/1-polytopes with vertex numbers within a certain range. On our way to obtain the result on perfect matching polytopes we generalize a result of Padberg and Rao’s on the adjacency structures of those polytopes. In addition to the material in the extended abstract (Kaibel and Walter in Integer programming and combinatorial optimization. Lecture Notes in Computer Science, vol 8494. Springer, Berlin, 2014) we include omitted proofs, supporting figures, and an analysis of known upper bounding techniques.

AB - We introduce the simple extension complexity of a polytope $$P$$P as the smallest number of facets of any simple (i.e., non-degenerate in the sense of linear programming) polytope which can be projected onto $$P$$P. We devise a combinatorial method to establish lower bounds on the simple extension complexity and show for several polytopes that they have large simple extension complexities. These examples include both the spanning tree and the perfect matching polytopes of complete graphs, uncapacitated flow polytopes for non-trivially decomposable directed acyclic graphs, hypersimplices, and random 0/1-polytopes with vertex numbers within a certain range. On our way to obtain the result on perfect matching polytopes we generalize a result of Padberg and Rao’s on the adjacency structures of those polytopes. In addition to the material in the extended abstract (Kaibel and Walter in Integer programming and combinatorial optimization. Lecture Notes in Computer Science, vol 8494. Springer, Berlin, 2014) we include omitted proofs, supporting figures, and an analysis of known upper bounding techniques.

KW - Extended formulations

KW - Flow polytopes

KW - Matching polytopes

KW - Simple polytopes

KW - Spanning tree polytopes

UR - http://www.scopus.com/inward/record.url?scp=84946496046&partnerID=8YFLogxK

U2 - 10.1007/s10107-015-0885-2

DO - 10.1007/s10107-015-0885-2

M3 - Article

VL - 154

SP - 381

EP - 406

JO - Mathematical programming

JF - Mathematical programming

SN - 0025-5610

IS - 1-2

ER -