K-cuts: A variation of Gomory mixed integer cuts from the LP tableau

K-cuts: A variation of Gomory mixed integer cuts from the LP tableau

0.00 Avg rating0 Votes
Article ID: iaor2007406
Country: United States
Volume: 15
Issue: 4
Start Page Number: 385
End Page Number: 395
Publication Date: Sep 2003
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: programming: linear
Abstract:

For an integer program, a k-cut is a cutting plane generated by the Gomory mixed integer procedure from a row of the LP tableau after multiplying it by a positive integer k. With this terminology, Gomory mixed integer cuts are just 1-cuts. In this paper, we compare the k-cuts (k ≥ 2) with Gomory mixed integer cuts. In particular, we prove in the pure case that with exactly 50% probability the k-cuts perform better variable-wise than the Gomory mixed integer cuts. Some computational experiments on knapsack problems are reported to illustrate this property.

Reviews

Required fields are marked *. Your email address will not be published.