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

Gérard Cornuéjols, Yanjun Li, Dieter Vandenbussche

INFORMS Journal on Computing · 2003 · Volume 15 · Issue 4

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.

Keywords

Integer Programming, LP Tableau, Gomory Mixed Integer Cut, K-Cut

Enable JavaScript for citation tools and additional paper interactions.