The Lagrangian Relaxation Method for Solving Integer Programming Problems
回顾了拉格朗日松弛法，该方法将复杂整数规划问题视为简单问题加上少量约束，通过松弛约束得到易解的下界，用于分支定界算法，显著改进了路径、选址、调度等问题的求解。
(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.