Optimization Online


An algorithm for the separation of two-row cuts

Quentin Louveaux (q.louveaux***at***ulg.ac.be)
Laurent Poirrier (lpoirrier***at***ulg.ac.be)

Abstract: We consider the question of finding deep cuts from a model constructed with two rows of a simplex tableau. To do that, we show how to reduce the complexity of setting up the polar of such model from a quadratic number of integer hull computations to a linear number of integer hull computations. Furthermore we present an algorithm that avoids computing integer hulls. A polynomial running time is not guaranteed but computational results show that the algorithm runs quickly in practice.

Keywords: Mixed-integer programming, Two rows, Cutting planes

Category 1: Integer Programming (Cutting Plane Approaches )

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

Citation: March 2010, revised September 2012. To appear in Mathematical Programming A.

Download: [PDF]

Entry Submitted: 03/16/2011
Entry Accepted: 03/16/2011
Entry Last Modified: 09/15/2012

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 Optimization Society