Lagrangian Relaxation

Imagine you are a factory scheduler juggling dozens of machines. Each job must finish before its deadline, machines cannot be double-booked, and the total overtime cost must stay below budget. Every time you add one more rule the problem gets exponentially harder — and real instances have thousands of them.

Lagrangian relaxation offers an elegant escape: instead of enforcing a troublesome constraint directly, you charge a penalty every time it is violated. The penalty is controlled by a multiplier, called the Lagrange multiplier (or dual variable), that acts like a price tag on bad behavior. With the constraint softened into a cost, the problem often breaks apart into small, easy sub-problems that you can solve independently.

The best part: the value of the relaxed problem is always less than or equal to the original optimal — a provable lower bound. Raise the multiplier price, tighten the bound. The highest achievable bound is the Lagrangian dual, and closing the gap between it and the true optimum is the central challenge of the method.

The technique was systematically developed by Marshall Fisher and others in the 1970s, building on Lagrange's 18th-century multiplier idea. It remains a cornerstone of integer programming solvers and large-scale scheduling today.

The demo below models a simple two-machine assignment problem. Two jobs must be assigned — one to each machine — but a coupling constraint says their start times must differ by at least one unit. That one constraint makes the problem hard.

We relax it by charging a penalty $\lambda$ for each unit of violation. Use the slider to set $\lambda$ manually and see how the relaxed objective changes, or press Run subgradient to let the algorithm automatically ascend toward the best (highest) lower bound.

<p class="hint">
  {{hint}}
</p>
<div class="controls">
  <label>λ = <span id="lam-val">0.00</span>
    <input type="range" id="lam" min="0" max="6" step="0.05" value="0">
  </label>
  <button id="run-btn" type="button">{{run_btn}}</button>
  <button id="reset-btn" type="button" class="ghost">{{reset_btn}}</button>
</div>
<div class="metrics">
  <div class="metric"><span class="label">{{label_dual}}</span><span id="dual" class="val">—</span></div>
  <div class="metric"><span class="label">{{label_best}}</span><span id="best" class="val">—</span></div>
  <div class="metric"><span class="label">{{label_true_opt}}</span><span id="true-opt" class="val">8</span></div>
  <div class="metric"><span class="label">{{label_gap}}</span><span id="gap" class="val">—</span></div>
</div>
<canvas id="chart" width="480" height="180"></canvas>
<div id="detail" class="detail"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.controls { display: flex; align-items: center; gap: .7rem; flex-wrap: wrap; margin-bottom: .8rem; }
label { display: flex; align-items: center; gap: .4rem; font-size: .93rem; font-weight: 600; }
input[type=range] { width: 160px; cursor: pointer; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.metrics { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .7rem; }
.metric { background: #eef2f6; border-radius: 8px; padding: .4rem .7rem; min-width: 110px; }
.metric .label { display: block; font-size: .75rem; color: #666; margin-bottom: .1rem; }
.metric .val { font: 700 1.05rem ui-monospace, monospace; color: #1d3557; }
#chart { display: block; width: 100%; max-width: 480px; border-radius: 8px;
         background: #f7f9fb; border: 1px solid #dde3ea; }
.detail { font-size: .85rem; color: #444; margin-top: .5rem; min-height: 2.5em; line-height: 1.5; }

// Code not found

Notice that as $\lambda$ increases, the penalty discourages violations and the bound tightens — but raises too high and the bound drops again. The best lower bound (the Lagrangian dual) sits at the peak of this curve. The subgradient method climbs that peak step by step, much like gradient ascent on a non-smooth landscape.

How does the method actually work — and what are its limits?

The relaxation step. Take a hard constraint $g(x) \le 0$ and move it into the objective with multiplier $\lambda \ge 0$: the new objective is $f(x) + \lambda \cdot g(x)$. The relaxed problem is easier because the coupling between variables is broken. For any fixed $\lambda$ the relaxed optimum is $\le$ the true optimum — that is the weak duality theorem.

The Lagrangian dual. Maximizing over all $\lambda \ge 0$ gives the Lagrangian dual value $L^*$ — the tightest lower bound the relaxation can produce. For convex problems $L^*$ equals the true optimum (zero gap). For integer programs there is generally a duality gap, and $L^*$ may be strictly below the integer optimum.

Subgradient method. We cannot differentiate the dual function smoothly (it is the maximum of a family of linear functions, hence piecewise linear and non-smooth). The subgradient method takes steps in the direction of the constraint violation: if a constraint is violated, raise its multiplier; if it is slack, lower it. With a carefully chosen step-size sequence, the iterates converge to $L^*$.

Complexity. Each subgradient iteration solves one relaxed sub-problem (often polynomial or even greedy). Convergence is typically $O(1/\varepsilon^2)$ iterations for an $\varepsilon$-optimal dual value — much better than solving the original integer program from scratch.

When the gap vanishes. The gap is zero for LP relaxations (by strong LP duality), and for many structured problems — the assignment problem, minimum-cost flow — the LP relaxation already has integer optimal solutions. In those cases Lagrangian relaxation recovers the exact integer optimum.

Lagrangian relaxation is not an academic curiosity — it is embedded in production solvers worldwide:

• Airline crew scheduling: millions of flights, thousands of crew rules, tight deadlines. Relaxing pairing constraints separates the problem by aircraft type, then the dual bound guides a branch-and-bound search.
• Vehicle routing: delivery trucks with capacity and time-window constraints. Relaxing the one-vehicle-per-customer constraint gives independent shortest-path sub-problems, each solved in polynomial time.
• Network design: which fiber links to build to meet traffic demands at minimum cost. Relaxing flow-conservation constraints decomposes into independent minimum-cost sub-networks.
• Power-grid unit commitment: which generators to switch on each hour. Relaxing the system-wide demand constraint decomposes into independent per-generator problems that are solved by dynamic programming.
• Integer programming solvers: modern branch-and-bound engines (CPLEX, Gurobi) use the LP relaxation, which is itself the Lagrangian dual of the integrality constraints.

The pattern is always the same: identify the coupling constraint that ties variables together, price it out, solve the decoupled sub-problems, and use the bound to prune the search. Related bounding ideas appear in linear programming duality and the column-generation technique used in large scheduling problems.

Lagrangian relaxation is a beautifully pragmatic idea: when a constraint is too expensive to enforce, charge for breaking it. The price — the Lagrange multiplier — transforms a monolithic hard problem into a family of easy sub-problems, and their combined cost is always a valid lower bound on the original.

Raise the price and the bound tightens. The subgradient method climbs toward the best possible bound, one violated constraint at a time. When the bound meets the integer optimum, you have proved optimality without ever solving the original NP-hard problem directly.

That gap between the dual bound and the true answer is not a failure — it is information. It tells the branch-and-bound solver exactly how much more it must search, and in the best cases it tells you the search is already over. Lagrangian relaxation does not make hard problems easy; it makes their hardness measurable and, often, manageable.