The Lagrangian Relaxation Method for Solving Integer Programming Problems

Marshall L. Fisher
Additional contact information
Marshall L. Fisher: University of Pennsylvania, Philadelphia, Pennsylvania

Management Science, 2004, vol. 50, issue 12_supplement, 1861-1871

Abstract: (This article originally appeared in Management Science, January 1981, Volume 27, Number 1, pp. 1--18, published by The Institute of Management Sciences.) One of the most computationally useful ideas of the 1970s is the observation that many hard integer programming problems can be viewed as easy problems complicated by a relatively small set of side constraints. Dualizing the side constraints produces a Lagrangian problem that is easy to solve and whose optimal value is a lower bound (for minimization problems) on the optimal value of the original problem. The Lagrangian problem can thus be used in place of a linear programming relaxation to provide bounds in a branch and bound algorithm. This approach has led to dramatically improved algorithms for a number of important problems in the areas of routing, location, scheduling, assignment and set covering. This paper is a review of Lagrangian relaxation based on what has been learned in the last decade.

Keywords: programming: integer algorithms; programming: integer algorithm branch and bound; programming: integer algorithms; heuristic (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (86)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.1040.0263 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:50:y:2004:i:12_supplement:p:1861-1871

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().