Optimization Online


Valid inequalities based on the interpolation procedure

Sanjeeb Dash (sanjeebd***at***us.ibm.com)
Oktay Gunluk (oktay***at***watson.ibm.com)

Abstract: We study the interpolation procedure of Gomory and Johnson (1972), which generates cutting planes for general integer programs from facets of master cyclic group polyhedra. This idea has recently been re-considered by Evans (2002) and Gomory, Johnson and Evans (2003). We compare inequalities generated by this procedure with mixed-integer rounding (MIR) based inequalities discussed in Dash and Gunluk (2003). We first analyze and extend the shooting experiment described in Gomory, Johnson and Evans. We show that MIR based inequalities dominate inequalities generated by the interpolation procedure in some important cases. We also show that the Gomory mixed-integer cut is likely to dominate any inequality generated by the interpolation procedure in a certain probabilistic sense. We also generalize a result of Cornuejols, Li and Vandenbussche (2003) on comparing the strength of the Gomory mixed-integer cut with related inequalities.

Keywords: integer programming, MIR inequalities, interpolation procedure, master cyclic group polyhedra

Category 1: Integer Programming


Download: [Postscript][PDF]

Entry Submitted: 03/26/2004
Entry Accepted: 03/26/2004
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