Optimization Online


A note on the MIR closure and basic relaxations of polyhedra

Sanjeeb Dash(sanjeebd***at***us.ibm.com)
Oktay Gunluk(gunluk***at***us.ibm.com)
Christian Raack(raack***at***zib.de)

Abstract: Anderson, Cornuejols and Li (2005) show that for a polyhedral mixed integer set defined by a constraint system Ax >= b, where x is n-dimensional, along with integrality restrictions on some of the variables, any split cut is in fact a split cut for a "basic relaxation", i.e., one defined by a subset of linearly independent constraints. This result implies that any split cut can be obtained as an intersection cut. Equivalence between split cuts obtained from simple disjunctions of the form (x_j <= 0) or (x_j >= 1) and intersection cuts was shown earlier for 0/1-mixed integer sets by Balas and Perregaard (2002). We give a short proof of the result of Anderson, Cornuejols and Li using the equivalence between mixed-integer rounding (MIR) cuts and split cuts.

Keywords: Split cuts, MIR inequalities, Basic relaxations

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

Category 2: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 12/14/2010
Entry Accepted: 12/14/2010
Entry Last Modified: 12/14/2010

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