The Lagrangian Relaxation Method for Solving Integer Programming Problems

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

Management Science, 1981, vol. 27, issue 1, 1-18

Abstract: 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: 1981
References: Add references at CitEc
Citations: View citations in EconPapers (306)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.27.1.1 (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:27:y:1981:i:1:p:1-18

Access Statistics for this article

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