Valid inequalities based on simple mixed-integer sets

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

Abstract: In this paper we use facets of mixed-integer sets with two and three variables to derive valid inequalities for integer sets defined by a single equation. These inequalities also define facets of the master cyclic group polyhedron of Gomory. Facets of this polyhedron give strong valid inequalities for general mixed-integer sets, such as the well-known Gomory mixed-integer cut. In particular, our inequalities generalize the slope facets of Araoz, Gomory, Johnson and Evans (2003). In addition, they dominate the strong fractional cuts of Letchford and Lodi (2002).

Keywords: Valid inequalities, mixed-integer programming, corner polyhedra

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

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Combinatorial Optimization (Polyhedra )

Citation:

Download: [Postscript][PDF]

Entry Submitted: 09/29/2003
Entry Accepted: 09/29/2003
Entry Last Modified: 04/17/2005

Modify/Update this entry