(This article originally appeared in Management Science, January 1981, Volume 27, Number 1, pp. 1-18, published by The Institute of Management Sciences.)#R##N##R##N#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.
['Marshall L. Fisher']
The Lagrangian Relaxation Method for Solving Integer Programming Problems