On the Strength of Gomory Mixed-Integer Cuts as Group Cuts

Gomory mixed-integer (GMI) cuts generated from optimal simplex tableaus are known to be useful in solving mixed-integer programs. Further, it is well-known that GMI cuts can be derived from facets of Gomory's master cyclic group polyhedron and its mixed-integer extension studied by Gomory and Johnson. In this paper we examine why cutting planes derived from other facets of master cyclic group polyhedra (group cuts) do not seem to be as useful when used in conjunction with GMI cuts. For many practical problem instances, we numerically show that once GMI cuts from di erent rows of the optimal simplex tableau are added to the formulation, all other group cuts from the same tableau rows are satisfied.

By: Sanjeeb Dash, Oktay Gunluk

Published in: Mathematical Programming , volume 115, (no 2), pages 387-407 in 2008

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .