Optimization Online


Decomposition in Integer Programming

T.K. Ralphs (tkralphs***at***lehigh.edu)
M.V. Galati (matthew.galati***at***sas.com)

Abstract: 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 implicitly defined polyhedron having a description of exponential size. In this paper, we first review these classical procedures and then introduce a new class of bounding methods called integrated decomposition methods, in which the bound yielded by traditional approaches is potentially improved by introducing a second implicitly defined polyhedron. We also discuss the concept of structured separation, which is related to the well-known template paradigm for dynamically generating valid inequalities and is central to our algorithmic framework. Finally, we briefly introduce a software framework for implementing the methods discussed in the paper and illustrate the concepts through the presentation of applications.

Keywords: Integer Programming, Decomposition, Cutting Plane, Column Generation, Dantzig-Wolfe, Lagrangian relaxation

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

Category 2: Integer Programming (Cutting Plane Approaches )

Citation: Technical Report 04T-019, Lehigh University Industrial and Systems Engineering Department

Download: [Postscript][PDF]

Entry Submitted: 12/23/2004
Entry Accepted: 12/27/2004
Entry Last Modified: 08/16/2005

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