Lagrange Multipliers and the Lagrangian

In a routing problem with hard side constraints (e.g., crew-time, fuel-budget, fleet-availability), it is often easier to absorb a complicating constraint into the objective using a price called a Lagrange multiplier than to enforce it directly. This is the foundation of Lagrangian relaxation.

Consider the constrained minimization problem

$$\begin{align*}\text{minimize} \quad & f(\mathbf{x}) \\ \text{subject to} \quad & g(\mathbf{x}) = b.\end{align*}$$

The Lagrangian is the function

$$L(\mathbf{x},\lambda) = f(\mathbf{x}) + \lambda\bigl(g(\mathbf{x}) - b\bigr),$$

where $\lambda \in \mathbb{R}$ is the Lagrange multiplier for the constraint.

The quantity $g(\mathbf{x}) - b$ is the constraint residual -- it is zero at any feasible point and nonzero when the constraint is violated. The multiplier $\lambda$ is the per-unit price charged for that residual.

For instance, with $f(x) = 4x$ and the constraint $x = 3$:

$$L(x,\lambda) = 4x + \lambda(x - 3).$$

At the feasible point $x = 3$ we have $L(3,\lambda) = 12 + 0 = 12 = f(3),$ matching the original objective. At an infeasible point $x = 5$ with $\lambda = 2$ we have $L(5,2) = 20 + 2 \cdot 2 = 24.$