Journal Article

The Lagrangian Relaxation Method for Solving Integer Programming Problems

Fisher, Marshall L

2004

Overview

( 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.

• Publisher: INFORMS,Institute for Operations Research and the Management Sciences
• Subject: Algorithms / Business studies / Discrete mathematics / heuristic / Heuristics / Integer programming / Integers / Lagrangian function / Lagrangian functions / Management / Management science / Mathematics / Methodology / Optimal solutions / Problem solving / Programming / programming: integer algorithm branch and bound / programming: integer algorithms / programming: integer algorithms, heuristic / Scheduling