کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
478045 | 1446006 | 2015 | 7 صفحه PDF | دانلود رایگان |
• We analyze split cuts from the perspective of cut generating functions.
• We show that k-cuts give all the split cuts for the mixed-integer corner relaxation.
• This implies that all splits are restrictions of splits for the infinite relaxation.
• We construct pure-integer IPs with arbitrarily bad split closure.
We analyze split cuts from the perspective of cut generating functions via geometric lifting. We show that α-cuts, a natural higher-dimensional generalization of the k-cuts of Cornuéjols et al., give all the split cuts for the mixed-integer corner relaxation. As an immediate consequence we obtain that the k-cuts are equivalent to split cuts for the 1-row mixed-integer relaxation. Further, we show that split cuts for finite-dimensional corner relaxations are restrictions of split cuts for the infinite-dimensional relaxation. In a final application of this equivalence, we exhibit a family of pure-integer programs whose split closure has arbitrarily bad integrality gap. This complements the mixed-integer example provided by Basu et al. (2011).
Journal: European Journal of Operational Research - Volume 243, Issue 3, 16 June 2015, Pages 745–751