An algorithm for the separation of two-row cuts
Quentin Louveaux (q.louveauxulg.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.
Entry Submitted: 03/16/2011
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|