Optimization Online


Valid inequalities based on simple mixed-integer sets

Sanjeeb Dash (sanjeebd***at***us.ibm.com)
Oktay Gunluk (oktay***at***watson.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 )


Download: [Postscript][PDF]

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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society