M.V. Galati – Optimization Online

Decomposition in Integer Programming

Published: 2004/12/23, Updated: 2005/08/16

(Mixed) Integer Linear Programming, Cutting Plane Approaches column generation, cutting planes, dantzig-wolfe, decomposition, integer programming, lagrangian relaxation

Both cutting plane methods and traditional decomposition methods are procedures that compute a bound on the optimal value of an integer linear program (ILP) by constructing an approximation to the convex hull of feasible solutions. This approximation is obtained by intersecting the polyhedron associated with the continuous relaxation, which has an explicit representation, with an … Read more

Decomposition and Dynamic Cut Generation in Integer Linear Programming

Published: 2003/09/15, Updated: 2005/08/16

M.V. Galati

Ted K. Ralphs

(Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Branch-and-Bound, branch-and-cut, branch-and-price, decomposition, integer programming

Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen the linear programming relaxation. Recently, a number of … Read more