On the strength of Gomory mixed-integer cuts as group cuts

Sanjeeb Dash (sanjeebdus.ibm.com)
Oktay Gunluk (gunlukus.ibm.com)

Abstract: 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 different rows of the optimal simplex tableau are added to the formulation, all other group cuts from the same tableau rows are satisfied.

Keywords: integer programming, mixed integer rounding, cyclic group polyhedra, cutting planes

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: IBM Research report RC23967.

Download: [Postscript][PDF]

Entry Submitted: 06/12/2006
Entry Accepted: 06/13/2006
Entry Last Modified: 06/07/2007

Modify/Update this entry