K-Cuts: A Variation of Gomory Mixed Integer Cuts from the LP Tableau

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.