## 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 R^{2 + 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