The Lagrangian Relaxation Method for Solving Integer Programming Problems

TLDR

Many hard integer programming problems can be viewed as easy problems with a small set of side constraints; dualizing these constraints yields a Lagrangian problem that is easy to solve and provides a lower bound, serving as a useful replacement for linear programming relaxations in branch‑and‑bound algorithms. This paper reviews Lagrangian relaxation, summarizing lessons learned over the past decade. The method has led to dramatically improved algorithms for routing, location, scheduling, assignment, and set covering.

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.