کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141791 | 957091 | 2008 | 11 صفحه PDF | دانلود رایگان |
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+1R2+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 kth 1-branch split closure of these polytopes for any k≥1k≥1. Despite the fact that the mm-branch split rank of the (m+1m+1)-dimensional polytope in this family is 1, we show that the 2-branch split rank of the (m+1m+1)-dimensional polytope is infinite when m≥3m≥3. We conjecture that the tt-branch split rank of the (m+1m+1)-dimensional polytope of the family is infinite for any 1≤t≤m−11≤t≤m−1 and m≥2m≥2.
Journal: Discrete Optimization - Volume 5, Issue 4, November 2008, Pages 724–734