Optimization Online


A heuristic to generate rank-1 GMI cuts

Sanjeeb Dash (sanjeebd***at***us.ibm.com)
Marcos Goycoolea (marcos.goycoolea***at***uai.cl)

Abstract: Gomory mixed-integer (GMI) cuts are among the most effective cutting planes for general mixed-integer programs (MIP). They are traditionally generated from an optimal basis of a linear programming (LP) relaxation of an MIP. In this paper we propose a heuristic to generate useful GMI cuts from additional bases of the initial LP relaxation. The cuts we generate have rank one, i.e., they do not use previously generated GMI cuts. We demonstrate that for problems in MIPLIB 3.0 and MIPLIB 2003, the cuts we generate form an important subclass of all rank-1 mixed-integer rounding cuts. Further, we use our heuristics to generate globally valid rank-1 GMI cuts at nodes of a branch-and-cut tree and use these cuts to solve a difficult problem from MIPLIB 2003, namely timtab2, without using problem-specific cuts.

Keywords: GMI cuts, rank-1 MIR cuts, MIR closure

Category 1: Integer Programming (Cutting Plane Approaches )

Citation: IBM Research Report RC24874, Oct. 2009.

Download: [Postscript][PDF]

Entry Submitted: 10/14/2009
Entry Accepted: 10/15/2009
Entry Last Modified: 10/19/2009

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