Many large optimisation problems have a natural decomposition blocked by a small number of shared resources: a global inventory pool that several regional planners compete for, a fleet of vehicles that multiple route planners request, or first-stage decisions in a stochastic programme that must be the same across all scenarios. Solving the coupled monolith is expensive; solving each local problem in isolation ignores the shared constraint. Dual decomposition resolves this tension by creating a private copy of the shared variable for each subproblem and attaching a Lagrange multiplier price to penalise disagreement between copies.
The algorithm proceeds in iterations. At each iteration: (1) a price coordinator broadcasts the current price vector to all subproblems; (2) each subproblem solves independently, treating the price as a fixed per-unit cost on its copy of the shared variable; (3) the coordinator collects each subproblem’s proposed value for the shared variable and updates prices — raising prices wherever total demand exceeds supply, lowering them where supply exceeds demand. The cycle repeats until all subproblem copies agree. When they agree, the prices are the dual variables certifying joint optimality.
The central computational advantage is parallelism: all subproblems run simultaneously in step (2). The coordinator only exchanges a compact price vector, not the full subproblem data. When subproblems are large and many, this is a dramatic speed improvement over solving the monolith.
Setup: A city logistics operator must allocate 20 refrigerated trucks across 5 delivery zones for the week. Each truck is a shared resource: the fleet manager’s model has a single constraint capping total allocation at 20, but each zone planner needs to run its own routing model to know how many trucks it can usefully employ given its customer locations and time windows.
Step 1 — initialise prices: The coordinator sets truck prices at zero. Each zone planner solves its routing problem and requests as many trucks as the model can absorb. Say Zones 1–5 request 8, 6, 5, 4, and 4 trucks (total: 27 — exceeding the 20 available).
Step 2 — price update: Total demand (27) exceeds supply (20), so the coordinator raises the truck price — making each zone’s routing model penalise truck usage more heavily. Each zone planner re-solves and reduces its request. After a few iterations, requests converge to 7, 5, 4, 3, 1 (total: 20). No zone can profitably acquire a truck that another zone values more highly.
Result: The final allocation equates the marginal value of a truck across zones — the correct market-clearing price for a scarce shared resource. The ECCO Shoes case study in issue 2026-05-05 applies the same principle: global inventory (the shared variable) is priced across country-level replenishment subproblems until supply and demand agree.
Common conflation: Both dual decomposition and Lagrangian relaxation use Lagrange multipliers, so practitioners often treat them as the same technique.
The architectural difference: Lagrangian relaxation dualizes a coupling constraint directly into the objective of a single model — the problem remains one model with a modified objective, and the solver balances the penalised constraint violation internally. Dual decomposition goes further: it creates physically separate subproblems, each holding a private copy of the shared variable, communicating only through the price vector the coordinator broadcasts. The distinction matters when subproblems benefit from running on separate machines, or when subproblems have fundamentally different structures (a routing model and an inventory model, say) that are best handled by different solvers. Lagrangian relaxation tightens a single model’s bounds; dual decomposition enables independent parallel solvers.
Common conflation: Both decompose a large problem into master and sub-problems. But the decomposition criterion and communication mechanism differ.
Benders splits by variable type: “complicating variables” (usually integer) go into a master problem, continuous variables into a subproblem. The subproblem returns a Benders cut — a constraint that the master must satisfy — and the master re-solves with the accumulated cuts until convergence. The split is one-way and structural: the master commands; the subproblem responds with a cut.
Dual decomposition splits by ownership: each subproblem holds its own copy of the shared variable and proposes a value; the coordinator responds with an updated price. The split is symmetric and iterative: all subproblems are peers; none is a master. Benders decomposes by what the variable does (it complicates the master). Dual decomposition decomposes by who owns it (each subproblem needs its own copy to be solvable independently).
Dual decomposition duplicates shared variables across independently-solved subproblems and enforces agreement through iteratively-updated Lagrange multiplier prices; all subproblems run in parallel and communicate only the price vector.