Symptom
The scheduler assigns jobs to machines and reports a cost of 84,300. Someone asks whether that is optimal.
You cannot answer. You can say the solver ran to completion, that a random restart found nothing better, and that the previous heuristic produced 91,000. None of that is a proof. For all you know there is an assignment at 71,000 and your search never went near it.
Worse, the follow-up question is unanswerable too: if we bought one more machine, how much would the cost drop? You could re-run the solver with an extra machine, and for one question that is fine, but there are forty such questions and each is a full solve.
Both questions have the same answer, and it is already sitting inside the solve you just did. Every linear program has a shadow program whose optimum is the same number and whose solution is a certificate of optimality and a price list at the same time.
Statement
Take a linear program in standard form.
Primal. $;\max; c^\top x ;$ subject to $; Ax \le b, ; x \ge 0$.
Dual. $;\min; b^\top y ;$ subject to $; A^\top y \ge c, ; y \ge 0$.
The dual has one variable per primal constraint and one constraint per primal variable. Constraints and variables swap roles; maximisation becomes minimisation; $A$ transposes.
Weak duality. For any feasible $x$ and any feasible $y$,
$$c^\top x \le b^\top y$$
Strong duality (von Neumann, Gale–Kuhn–Tucker, 1951). If either problem has a finite optimum, so does the other, and the two optima are equal:
$$\max\, c^\top x = \min\, b^\top y$$
Complementary slackness. Optimal $x^, y^$ satisfy, for every $i$ and $j$:
$$y_i^*\,(b_i - (Ax^*)_i) = 0 \quad\text{and}\quad x_j^*\,((A^\top y^*)_j - c_j) = 0$$A constraint with slack has a zero price; a variable in use has a tight dual constraint.
Argument
Where the dual comes from, which is the only way it stops being arbitrary. Suppose you want to prove an upper bound on the primal, without solving it. The only tool available is the constraints themselves. Take a non-negative combination of them with weights $y \ge 0$:
$$y^\top A x \le y^\top b$$Non-negativity of $y$ matters, because multiplying an inequality by a negative number flips it. Now, if the weights are chosen so that the left side dominates the objective coefficient-wise — that is, $A^\top y \ge c$ — then, since $x \ge 0$:
$$c^\top x \le (A^\top y)^\top x = y^\top A x \le y^\top b = b^\top y$$So every feasible $y$ is a proof of the bound $c^\top x \le b^\top y$, and the tightest such proof is the one minimising $b^\top y$. The dual is not a construction someone invented; it is the question “what is the best bound provable from the constraints?” written down. Weak duality is the two lines above.
Strong duality — that the best provable bound is exactly the optimum, with no gap — is the theorem. It follows from Farkas’ lemma, the separating-hyperplane statement that a system $Ax \le b$ is infeasible if and only if some non-negative combination of its rows yields the contradiction $0 \le -1$. Applied to the system “primal feasible, dual feasible, and $c^\top x \ge b^\top y$”, Farkas says that if no such point exists then a separating certificate exists, and unwinding the certificate gives the equality. The geometric content: at the optimal vertex, the objective gradient lies in the cone generated by the normals of the tight constraints, and the dual variables are exactly the coefficients of that expression.
Reading the dual as prices, which is what you actually use it for. The dual variable $y_i$ has units of objective-per-unit-of-$b_i$. That is not an analogy; it is the derivative:
$$y_i^* = \frac{\partial\,(\text{optimal value})}{\partial b_i}$$valid in a neighbourhood where the optimal basis does not change. So the scheduler’s dual solution answers the forty follow-up questions at once.
Concretely. A factory maximises profit $\max, 3x_1 + 5x_2$ subject to labour $x_1 + 2x_2 \le 100$ and material $3x_1 + 2x_2 \le 180$, with $x \ge 0$. The optimum is $x = (40, 30)$ with profit 270. The dual optimum is $y = (2, 1)$.
Read it: an extra hour of labour is worth $2 of profit, and an extra unit of material is worth $1. If labour costs $1.50 an hour on the spot market, buy it; at $2.50, do not. The dual is a complete answer to every marginal-resource question, produced by the same solve. This is why economists call these shadow prices and why every LP solver returns them alongside the primal solution — if you have never looked at that field of the output, that is the field.
Complementary slackness, and why it is the practical test. The conditions say optimality is equivalent to a pattern of “either the constraint is tight or its price is zero”. Two readings:
- A resource not fully used has zero marginal value. Slack labour means an extra hour is worth nothing. Obvious once stated, and it is half the theorem.
- A product being manufactured must exactly break even at shadow prices. If $x_j > 0$ then $\sum_i a_{ij} y_i = c_j$: the resources it consumes, priced by the dual, cost exactly what it earns. If some product earned more than its input cost, you would make more of it.
The certificate, which answers the original question. Given a claimed solution, exhibit a dual feasible $y$ with $b^\top y = c^\top x$. Weak duality then makes the pair self-verifying: no feasible primal can exceed $b^\top y$, and $x$ attains it. You do not need to trust the solver, the search, or the heuristic — the certificate is checkable in $O(\text{nnz}(A))$ arithmetic. This is why LP is in NP $\cap$ co-NP, a fact that was known long before Khachiyan proved it is in P, and it is the only tool in this series for proving that an answer you already have is the best one.
Max-flow min-cut is this theorem’s smallest instance. Write max-flow as an LP: variables are edge flows, constraints are capacities and conservation, and the objective is the value. Take the dual. Its variables turn out to be one per edge and one per vertex, and its optimal solutions are exactly the indicator vectors of $s$–$t$ cuts, with objective $\sum c(u,v)$ over the cut. Strong duality says max-flow = min-cut.
That the dual’s optimum happens to be integral — an actual cut, not a fractional blend of cuts — is a special property of this constraint matrix (total unimodularity), not a consequence of duality. Duality gives you the equality of the two optima; integrality is a separate gift from the network structure, and conflating them is the source of the misreading below.
Duals of things you already use. The pattern is worth recognising because it turns up constantly:
- Shortest path is dual to a potential/distance-labelling problem, and the dual optimal is exactly the distance labels; A*’s admissible heuristic is a feasible dual solution.
- Minimum vertex cover (LP relaxation) is dual to maximum matching (LP relaxation), which is why the two are always within a factor of 2.
- SVMs are trained in the dual, which is what makes the kernel trick possible: the dual involves only inner products of examples.
- Game theory: von Neumann’s minimax theorem for zero-sum games is strong duality applied to the payoff matrix, and it is the historical reason the theorem exists.
Forbids
Claiming optimality without a bound. A solution is optimal when a matching dual certificate exists, and not when the search stopped. Any optimality claim with no dual value behind it is a claim about the search, not the problem.
A duality gap in linear programming. If both problems are feasible, the optima are equal, full stop. This is not true for general non-convex problems and is exactly what makes LP special.
A feasible primal and an unbounded dual, or vice versa. Weak duality forbids it: a single feasible $y$ bounds the primal, and a single feasible $x$ bounds the dual.
Buying a resource for more than its shadow price. By definition of the derivative, that transaction loses money at the margin.
Does not forbid
It does not mean an LP relaxation bound is the integer optimum, and this is the live misreading, made constantly and expensively. Relaxing integrality gives an LP whose dual certifies a bound on the relaxation, not on the integer problem. A scheduler reporting “LP bound 84,300, integer solution 84,300” is proved optimal; one reporting “LP bound 71,000, integer solution 84,300” has proved nothing except that the true optimum lies between — and that gap, the integrality gap, can be arbitrarily large. Set cover’s is $\Theta(\log n)$. Every branch-and-bound solver’s progress bar is exactly this gap closing, and reading the LP bound as an achievable target is how people conclude their solver is performing badly when it is in fact optimal.
It does not require the LP to be solved by simplex. Interior-point methods produce primal and dual solutions simultaneously and are how large problems are actually solved. The theorem is about the problems, not the method.
It does not fail for degenerate problems. Degeneracy makes shadow prices non-unique — several dual optima, hence a left derivative differing from the right — but strong duality still holds. A degenerate LP still has a valid optimality certificate; you just cannot read a single unambiguous price off it, which matters when the price is what you came for.
It does not extend unchanged to non-convex optimisation, but it does extend further than LP. Convex problems satisfying Slater’s condition also have zero duality gap. For general non-convex problems the dual still gives a valid lower bound — Lagrangian relaxation — which is weaker but still a certificate, and that is the workhorse of large-scale integer programming.
It does not make solving the dual easier than the primal. They have the same complexity. You solve the dual when it has fewer constraints, or when its structure decomposes, not because duality is a shortcut.
Boundary
- Feasibility can fail on both sides. Primal infeasible and dual infeasible simultaneously is possible, and strong duality’s hypothesis excludes it. The useful corollary is Farkas: infeasibility itself has a certificate, so a solver can prove “no solution exists” as rigorously as it proves optimality.
- Shadow prices are local. Valid only while the optimal basis is unchanged. Solvers report the ranging interval; ignoring it and extrapolating a price to a large change is the most common misuse.
- Degeneracy makes prices ambiguous. See above.
- Integrality is separate. Total unimodularity, network matrices, and matroid intersection give integral optima; nothing else does automatically.
- Numerical certificates are approximate. Floating-point solvers return near-feasible duals, and a genuinely rigorous certificate needs exact or interval arithmetic — which matters when the LP bound is being used inside a proof rather than inside a report.
The habit worth forming: when a solver hands you a number, ask what certifies it. The certificate is already in the output, and it also happens to be the price list.