Lagrangian Relaxation: Dualizing Complicating Constraints

Form the Lagrangian function by dualizing complicating constraints with multipliers, solve the resulting Lagrangian subproblem, and use weak duality to obtain bounds on the original optimization problem.

Step 1 of 157%

Tutorial

Introduction

Many optimization problems are easy to solve except for a small number of constraints that tie different parts of the problem together. Lagrangian relaxation removes such complicating constraints from the feasible region and pulls them into the objective function using Lagrange multipliers (also called dual prices).

Consider the maximization

\begin{aligned}z^* = \max \quad & \mathbf{c}^T \mathbf{x} \\ \text{s.t.} \quad & A\mathbf{x} \le \mathbf{b} \quad \text{(complicating)} \\ & \mathbf{x} \in X,\end{aligned}

where $X$ is "easy" (for example, a Cartesian product of bounded integer sets) but the constraint $A\mathbf{x} \le \mathbf{b}$ couples decisions across $X.$

Given a multiplier vector $\boldsymbol{\lambda} \ge \mathbf{0},$ the Lagrangian function is

L(\mathbf{x}, \boldsymbol{\lambda}) = \mathbf{c}^T \mathbf{x} + \boldsymbol{\lambda}^T (\mathbf{b} - A\mathbf{x}).

The Lagrangian subproblem (or Lagrangian relaxation) at $\boldsymbol{\lambda}$ is

L(\boldsymbol{\lambda}) = \max_{\mathbf{x} \in X} \; L(\mathbf{x}, \boldsymbol{\lambda}).

We require $\boldsymbol{\lambda} \ge \mathbf{0}$ because the dualized constraints are $\le$ inequalities in a maximization: any violation must be penalized, not rewarded. If the dualized constraint were an equality $A\mathbf{x} = \mathbf{b},$ then $\boldsymbol{\lambda}$ would be unrestricted in sign.