Lagrangian Relaxation of Capacity Constraints

Relax the coupling sector-time capacity constraints of the Bertsimas-Patterson ATFM integer program using non-negative multipliers, forming a Lagrangian that decomposes by flight. Use this decomposition to compute the Lagrangian dual value $g(\lambda)$ , which is a valid lower bound on the optimum of the original program.

Step 1 of 157%

Tutorial

Relaxing the Capacity Constraints

The Bertsimas-Patterson ATFM integer program has the structure

\begin{aligned}\min_{x} \quad & \sum_{f \in F} c_f(x^f) \\ \text{s.t.}\quad & \sum_{f \in F} a^f_{j,t}(x^f) \le C_{j,t} \quad \text{for every sector-time }(j,t), \\ & x^f \in X^f \quad \text{for every flight } f \in F. \end{aligned}

The capacity constraints in the first family are the only constraints that couple flights together: they say that for each sector-time $(j,t)$ , the total occupancy across all flights cannot exceed $C_{j,t}$ . The per-flight constraints $x^f \in X^f$ restrict each flight on its own (routing, connectivity, time windows).

Lagrangian relaxation removes the coupling constraints by absorbing them into the objective. For each capacity constraint we introduce a non-negative multiplier $\lambda_{j,t} \ge 0$ and form the Lagrangian

L(x, \lambda) \;=\; \sum_{f \in F} c_f(x^f) \;+\; \sum_{(j,t)} \lambda_{j,t}\!\left(\sum_{f \in F} a^f_{j,t}(x^f) - C_{j,t}\right)\!.

The multipliers must satisfy $\lambda_{j,t} \ge 0$ because the relaxed constraints are inequalities of the form $\le$ : a violation $\sum_f a^f_{j,t}(x^f) - C_{j,t} > 0$ should contribute a positive penalty to the objective.

The relaxed problem is

g(\lambda) \;=\; \min_{x^f \in X^f \;\forall f} L(x, \lambda),

in which the capacity constraints are gone — only the per-flight constraints $x^f \in X^f$ remain.