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 language | English (US) |
---|---|
Pages (from-to) | 724-734 |
Number of pages | 11 |
Journal | Discrete Optimization |
Volume | 5 |
Issue number | 4 |
DOIs | |
State | Published - Nov 2008 |
Externally published | Yes |
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