Lagrangian Relaxation

Lagrangian relaxation is a classical decomposition technique that reduces an optimization problem with hard structural constraints to an easier subproblem by dualizing the complicating constraints via Lagrange multipliers that penalize violation in the objective. Systematic OR use began with the 1-tree relaxation of Held and Karp (1970, 1971) for the travelling salesman, was placed in the general MIP framework by Geoffrion (1974), and was popularized for practitioners by the Fisher (1981) handbook paper. In the problem min c·x : A₁x = b₁, A₂x = b₂, x ∈ X, if A₁x = b₁ is hard, multipliers λ dualize it: L(λ) = min c·x + λ(b₁ - A₁x) : A₂x = b₂, x ∈ X — typically this subproblem decomposes into knapsack, assignment, or shortest-path structures solvable in polynomial time. The Lagrangian dual max_λ L(λ) yields a Lagrangian bound that is never worse than the LP-relaxation bound and whose weak-duality gap is bounded by the problem's integrality gap. To solve the dual one uses the subgradient method (Held, Wolfe and Crowder 1974), bundle methods (Lemaréchal 1975), or the volume algorithm (Barahona and Anbil 2000). Lagrangian relaxation is used for primal bound generation and bound tightening inside branch and bound on GAP, set covering, MCNF, capacitated facility location, and scheduling. Wolsey (1998) chapter 10 is the standard reference.