Optimization Online


Strengthening lattice-free cuts using non-negativity

Ricardo Fukasawa (rfukasaw***at***isye.gatech.edu )
Oktay Gunluk (gunluk***at***us.ibm.com)

Abstract: In recent years there has been growing interest in generating valid inequalities for mixed-integer programs using sets with 2 or more constraints. In particular, Andersen et.al (2007) and Borozan and Cornue'jols (2007) study sets defined by equations that contain exactly one integer variable per row. The integer variables are not restricted in sign. Cutting planes based on this approach have already been used by Espinoza (2008) for general mixed-integer problems and there is also ongoing computational research in this area. In this paper, we restrict the model studied in the earlier papers and require the integer variables to be non-negative. We extend the results in Andersen et.al (2007) and Borozan and Cornue'jols (2007) to our case and show that cuts generated by their approach can be strengthened by using the non-negativity of the integer variables. In particular, it is possible to obtain cuts which have negative coefficients for some variables.

Keywords: Mixed integer programming, valid inequalities, lattice free polyhedra.

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

Category 2: Integer Programming (Cutting Plane Approaches )


Download: [PDF]

Entry Submitted: 05/14/2009
Entry Accepted: 05/14/2009
Entry Last Modified: 09/09/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