Introduction

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.

Watch the Dual Bound Climb

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">
  Two jobs compete for two machines. A <b>coupling constraint</b> says their start times must differ by ≥ 1. We relax it by charging penalty <b>λ</b> per unit of violation. The relaxed cost is always ≤ the true optimum — a valid lower bound.
</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 subgradient</button>
  <button id="reset-btn" type="button" class="ghost">Reset</button>
</div>
<div class="metrics">
  <div class="metric"><span class="label">Dual bound L(λ)</span><span id="dual" class="val">—</span></div>
  <div class="metric"><span class="label">Best bound L*</span><span id="best" class="val">—</span></div>
  <div class="metric"><span class="label">True optimum</span><span id="true-opt" class="val">8</span></div>
  <div class="metric"><span class="label">Duality 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Problem: assign Job A and Job B each to one of two machines.
// Job A on machine 1 costs 5, on machine 2 costs 9.
// Job B on machine 1 costs 7, on machine 2 costs 3.
// Coupling constraint: |startA - startB| >= 1  (startA in {0,1}, startB in {0,1})
// For simplicity we encode: xA in {0,1} (0=machine1, 1=machine2),
//                           xB in {0,1} (0=machine1, 1=machine2).
// Constraint: xA != xB  (each job to a DIFFERENT machine: xA + xB = 1)
//   encoded as coupling g(x) = (xA + xB - 1)^2  (= 0 iff exactly one is 1)
// True problem: min costA[xA] + costB[xB]  s.t. xA + xB = 1
//   Feasible solutions: (xA=0,xB=1)->5+3=8  or  (xA=1,xB=0)->9+7=16
//   True optimum = 8.
//
// Lagrangian relaxation: L(λ) = min over (xA,xB) in {0,1}^2 of
//   costA[xA] + costB[xB] + λ*(xA + xB - 1)
// This decouples into two independent 1-variable minimizations.

const costA = [5, 9];  // costA[0]=machine1, costA[1]=machine2
const costB = [7, 3];  // costB[0]=machine1, costB[1]=machine2
const TRUE_OPT = 8;    // xA=0,xB=1 -> 5+3=8

function lagrangian(lam) {
  // Decoupled: choose xA to minimize costA[xA] + lam*xA
  const fA0 = costA[0] + lam * 0;
  const fA1 = costA[1] + lam * 1;
  const xA = fA0 <= fA1 ? 0 : 1;
  const valA = Math.min(fA0, fA1);

  // Choose xB to minimize costB[xB] + lam*xB
  const fB0 = costB[0] + lam * 0;
  const fB1 = costB[1] + lam * 1;
  const xB = fB0 <= fB1 ? 0 : 1;
  const valB = Math.min(fB0, fB1);

  const L = valA + valB - lam;  // subtract lam (the -lambda constant term)
  const violation = xA + xB - 1; // coupling constraint residual
  return { L, xA, xB, violation };
}

// Pre-compute the dual curve for the chart
const STEPS = 120;
const LAM_MAX = 6;
const curve = [];
let bestL = -Infinity, bestLam = 0;
for (let i = 0; i <= STEPS; i++) {
  const lam = (i / STEPS) * LAM_MAX;
  const { L } = lagrangian(lam);
  curve.push({ lam, L });
  if (L > bestL) { bestL = L; bestLam = lam; }
}

// Canvas chart
const canvas = document.getElementById('chart');
const ctx = canvas.getContext('2d');
const W = canvas.width, H = canvas.height;
const PAD = { top: 18, right: 18, bottom: 28, left: 44 };

const minL = Math.min(...curve.map(p => p.L)) - 0.5;
const maxL = Math.max(...curve.map(p => p.L)) + 0.5;

function toX(lam) { return PAD.left + (lam / LAM_MAX) * (W - PAD.left - PAD.right); }
function toY(L)   { return PAD.top  + (1 - (L - minL) / (maxL - minL)) * (H - PAD.top - PAD.bottom); }

function drawChart(currentLam, history) {
  ctx.clearRect(0, 0, W, H);
  // Axes
  ctx.strokeStyle = '#cdd9e3'; ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(PAD.left, PAD.top); ctx.lineTo(PAD.left, H - PAD.bottom);
  ctx.lineTo(W - PAD.right, H - PAD.bottom);
  ctx.stroke();
  // Axis labels
  ctx.fillStyle = '#888'; ctx.font = '11px system-ui'; ctx.textAlign = 'right';
  const yTicks = 4;
  for (let i = 0; i <= yTicks; i++) {
    const val = minL + (i / yTicks) * (maxL - minL);
    const y = toY(val);
    ctx.fillText(val.toFixed(1), PAD.left - 4, y + 4);
  }
  ctx.textAlign = 'center';
  for (let lam = 0; lam <= LAM_MAX; lam += 2) {
    ctx.fillText(lam.toFixed(0), toX(lam), H - PAD.bottom + 14);
  }
  ctx.fillText('λ', W - PAD.right + 8, H - PAD.bottom + 4);
  ctx.fillText('L(λ)', PAD.left - 32, PAD.top - 6);

  // True optimum line
  ctx.strokeStyle = '#e63946'; ctx.lineWidth = 1; ctx.setLineDash([4, 3]);
  ctx.beginPath();
  ctx.moveTo(PAD.left, toY(TRUE_OPT)); ctx.lineTo(W - PAD.right, toY(TRUE_OPT));
  ctx.stroke();
  ctx.setLineDash([]);
  ctx.fillStyle = '#e63946'; ctx.font = '10px system-ui'; ctx.textAlign = 'left';
  ctx.fillText(fmt('true opt=%TRUE_OPT%', { TRUE_OPT: TRUE_OPT }), PAD.left + 4, toY(TRUE_OPT) - 3);

  // Dual curve
  ctx.strokeStyle = '#1d3557'; ctx.lineWidth = 2;
  ctx.beginPath();
  curve.forEach(({ lam, L }, i) => {
    if (i === 0) ctx.moveTo(toX(lam), toY(L));
    else ctx.lineTo(toX(lam), toY(L));
  });
  ctx.stroke();

  // Subgradient history path
  if (history && history.length > 1) {
    ctx.strokeStyle = '#457b9d'; ctx.lineWidth = 1.5; ctx.setLineDash([3, 2]);
    ctx.beginPath();
    history.forEach(({ lam, L }, i) => {
      if (i === 0) ctx.moveTo(toX(lam), toY(L));
      else ctx.lineTo(toX(lam), toY(L));
    });
    ctx.stroke();
    ctx.setLineDash([]);
  }

  // Current lambda dot
  const { L } = lagrangian(currentLam);
  ctx.fillStyle = '#e63946';
  ctx.beginPath();
  ctx.arc(toX(currentLam), toY(L), 5, 0, 2 * Math.PI);
  ctx.fill();
}

let history = [];
let running = false;

function update() {
  const lam = parseFloat(document.getElementById('lam').value);
  document.getElementById('lam-val').textContent = lam.toFixed(2);
  const { L, xA, xB, violation } = lagrangian(lam);
  document.getElementById('dual').textContent = L.toFixed(2);
  document.getElementById('best').textContent = bestL.toFixed(2);
  document.getElementById('gap').textContent = (TRUE_OPT - Math.max(L, 0)).toFixed(2);
  const machA = xA === 0 ? 'Machine 1 (cost 5)' : 'Machine 2 (cost 9)';
  const machB = xB === 0 ? 'Machine 1 (cost 7)' : 'Machine 2 (cost 3)';
  const viol = violation === 0 ? 'coupling satisfied (different machines)' : fmt('coupling VIOLATED (same machine, violation=%violation%)', { violation: violation });
  document.getElementById('detail').innerHTML =
    fmt('At λ=%lam%: Job A → %machA%, Job B → %machB%<br>%viol%. Relaxed cost = %L%.', { lam: lam.toFixed(2), machA: machA, machB: machB, viol: viol, L: L.toFixed(2) });
  drawChart(lam, history);
}

async function runSubgradient() {
  if (running) return;
  running = true;
  history = [];
  let lam = 0;
  const T = 40;
  for (let t = 0; t < T; t++) {
    const { L, violation } = lagrangian(lam);
    history.push({ lam, L });
    const stepSize = 2.0 / (t + 1);
    lam = Math.max(0, Math.min(LAM_MAX, lam + stepSize * violation));
    document.getElementById('lam').value = lam;
    update();
    await new Promise(r => setTimeout(r, 60));
  }
  running = false;
}

document.getElementById('lam').addEventListener('input', () => { history = []; update(); });
document.getElementById('run-btn').addEventListener('click', runSubgradient);
document.getElementById('reset-btn').addEventListener('click', () => {
  history = []; running = false;
  document.getElementById('lam').value = 0;
  update();
});

update();
Result
Console

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.

The Real Complexity

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

The relaxation step. Take a hard constraint g(x)≤0g(x) \le 0 and move it into the objective with multiplier λ≥0\lambda \ge 0: the new objective is f(x)+λ⋅g(x)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 λ≥0\lambda \ge 0 gives the Lagrangian dual value L∗L^* — the tightest lower bound the relaxation can produce. For convex problems L∗L^* equals the true optimum (zero gap). For integer programs there is generally a duality gap, and L∗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∗L^*.

Complexity. Each subgradient iteration solves one relaxed sub-problem (often polynomial or even greedy). Convergence is typically O(1/ε2)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/lagrangian-relaxation/Content licensed under CC BY-NC 4.0.