Optimization Online


Separation of Generic Cutting Planes in Branch-and-Price Using a Basis

Marco Lübbecke(marco.luebbecke***at***rwth-aachen.de)
Jonas Witt(witt***at***or.rwth-aachen.de)

Abstract: Dantzig-Wolfe reformulation of a mixed integer program partially convexifies a subset of the constraints, i.e., it implicitly adds all valid inequalities for the associated integer hull. Projecting an optimal basic solution of the reformulation's LP relaxation to the original space does is in general not yield a basic solution of the original LP relaxation. Cutting planes in the original problem that are separated using a basis like Gomory mixed integer cuts are therefore not directly applicable. Range [22] (and others) proposed as a remedy to heuristically compute a basic solution and separate this auxiliary solution also with cutting planes that stem from a basis. This might not only cut off the auxiliary solution, but also the solution we originally wanted to separate. We discuss and extend Range's ideas to enhance the separation procedure. In particular, we present alternative heuristics and consider additional valid inequalities strengthening the original LP relaxation before separation. Our full implementation, which is the first of its kind, is done within the GCG framework. We evaluated the effects on several problem classes. Our experiments show that the separated cuts strengthen the formulation on instances where the integrality gap is not too small. This leads to a reduced number of nodes and reduced solution times.

Keywords: Brance-and-Price; Cutting Planes; Basis Heuristic

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Optimization Software and Modeling Systems


Download: [PDF]

Entry Submitted: 02/26/2015
Entry Accepted: 02/26/2015
Entry Last Modified: 02/26/2015

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