Cook, Kannan and Schrijver's example revisited

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

In 1990, Cook, Kannan and Schrijver [W. Cook, R. Kannan, A. Schrijver, Chvátal closures for mixed integer programming problems, Mathematical Programming 47 (1990) 155-174] proved that the split closure (the 1st 1-branch split closure) of a polyhedron is again a polyhedron. They also gave an example of a mixed-integer polytope in R2 + 1 whose 1-branch split rank is infinite. We generalize this example to a family of high-dimensional polytopes and present a closed-form description of the k th 1-branch split closure of these polytopes for any k ≥ 1. Despite the fact that the m-branch split rank of the (m + 1)-dimensional polytope in this family is 1, we show that the 2-branch split rank of the (m + 1)-dimensional polytope is infinite when m ≥ 3. We conjecture that the t-branch split rank of the (m + 1)-dimensional polytope of the family is infinite for any 1 ≤ t ≤ m - 1 and m ≥ 2.

Original languageEnglish (US)
Pages (from-to)724-734
Number of pages11
JournalDiscrete Optimization
Volume5
Issue number4
DOIs
StatePublished - Nov 2008
Externally publishedYes

Bibliographical note

Funding Information:
The authors are grateful to an anonymous referee for reading the proofs carefully and providing a detailed list of suggestions that have helped us improve this paper. The second author was supported by NSF grant DMI-348611.

Keywords

  • Mixed-integer programming
  • Split closure
  • Split cuts
  • Split rank

Fingerprint Dive into the research topics of 'Cook, Kannan and Schrijver's example revisited'. Together they form a unique fingerprint.

Cite this