Optimization Online


Decomposition and Dynamic Cut Generation in Integer Linear Programming

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

Abstract: 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 authors have proposed methods for integrating dynamic cut generation with various decomposition methods to yield further improvement in the computed bounds. In this paper, we describe a framework within which most of these methods can be viewed from a common theoretical perspective. We then show how the framework can be extended to obtain a new class of methods we call \emph{decompose and cut}. As a by-product, we describe how these methods can take advantage of the fact that solutions with known structure, such as those to a given combinatorial relaxation, can frequently be separated much more easily than arbitrary solutions.

Keywords: integer programming, branch and bound, branch and cut, branch and price, decomposition

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

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Lehigh University, Industrial and Systems Engineering Technical Report 03T-005, September 2003.


Entry Submitted: 09/15/2003
Entry Accepted: 09/15/2003
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