LP Duality

The question

A workshop makes benches ($x$ per week) and shelves ($y$ per week). A bench earns 7 and a shelf earns 5. A bench takes 2 cutting hours and 1 finishing hour; a shelf takes 1 cutting hour and 2 finishing hours. There are 14 cutting hours and 16 finishing hours a week, and the market takes at most 6 benches. As a linear program:

$$max7x+5y\text{s.t.}2x+y\le 14,x+2y\le 16,x\le 6,x,y\ge 0.$$

The planner's software says: make 4 benches and 6 shelves, for a profit of 58, and nothing does better. The owner's auditor doesn't trust software she can't read. She asks: what could you hand me that proves 58 is the best, which I can check with a pencil?

This module answers that question for every linear program. It assumes you can write a problem as an LP and know that an optimum sits at a corner of the feasible region (module 15). The section on games uses mixed strategies from module 14, and the section on flows uses cuts from module 11.

Two ways that don't satisfy the auditor

List every corner. An optimum of a bounded, feasible LP is attained at a corner, and each corner is where two of the five lines (three constraints and two axes) meet. Here that is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ small systems, of which five give feasible corners:

from fractions import Fraction as F
from itertools import combinations

c = [7, 5]                        # profit per bench, per shelf
A = [[2, 1], [1, 2], [1, 0]]      # cutting, finishing, bench limit
b = [14, 16, 6]

def corners(A, b):
    """Feasible points where two of the lines (constraints or axes) cross."""
    lines = list(zip(A, b)) + [([-1, 0], 0), ([0, -1], 0)]
    found = set()
    for (p, e), (q, f) in combinations(lines, 2):
        det = p[0] * q[1] - p[1] * q[0]
        if det == 0:
            continue
        x = F(e * q[1] - p[1] * f, det)
        y = F(p[0] * f - e * q[0], det)
        if x >= 0 and y >= 0 and all(r[0] * x + r[1] * y <= bi for r, bi in zip(A, b)):
            found.add((x, y))
    return sorted(found)

pts = corners(A, b)
assert pts == [(0, 0), (0, 8), (4, 6), (6, 0), (6, 2)]
assert [7 * x + 5 * y for x, y in pts] == [0, 40, 58, 42, 52]

That convinces the auditor here, but with $n$ products and $m$ resources there can be $\left(\genfrac{}{}{0ex}{}{m+n}{n}\right)$ candidate corners: 70 at $m=n=4$, and about $1.1\times {10}^{23}$ at $m=n=40$. Re-running the solver is cheap, but it is "trust me" again, and it costs as much as the original solve. What the auditor wants is a proof that is easier to check than the answer was to find.

Combining the constraints

Here is a proof she can check. Take 3 copies of the cutting constraint and 1 copy of the finishing constraint and add them:

$$3(2x+y)+1(x+2y)\le 3·14+1·16,\text{that is,}7x+5y\le 58.$$

The left side is exactly the profit. So every feasible plan earns at most 58, and the plan $(4,6)$ earns 58: it is optimal. The auditor has to check two things: that the multipliers are non-negative, so multiplying doesn't flip an inequality, and that the combination's coefficients match the profit's. That is a few multiplications, not a solve.

The coefficients don't even have to match exactly. If the combination gives at least 7 per bench and at least 5 per shelf, then, because $x,y\ge 0$, $7x+5y$ is at most the combination's left side, which is at most its right side. Each choice of multipliers $y_1,y_2,y_3\ge 0$ (one per constraint) with that property proves an upper bound $14y_1+16y_2+6y_3$ on the profit. Three choices:

def dot(u, v):
    return sum(F(p) * q for p, q in zip(u, v))

cols = [list(col) for col in zip(*A)]    # column j: resources one unit of product j uses
for y, bound in [((5, 0, 0), 70), ((0, F(5, 2), F(9, 2)), 67), ((3, 1, 0), 58)]:
    assert min(y) >= 0
    assert dot(cols[0], y) >= 7 and dot(cols[1], y) >= 5      # the sum row covers the profit
    assert dot(b, y) == bound
assert dot(c, (4, 6)) == 58

Think of $y_i$ as a price per unit of resource $i$. The conditions say that, at these prices, the resources a bench uses are worth at least what a bench earns, and likewise for a shelf. The bound says that the whole stock, at these prices, is worth at least any plan's profit.

The dual

The best bound of this kind is the cheapest stock value, and finding it is itself a linear program, the dual of the workshop's LP (which is then called the primal):

$$min14y_1+16y_2+6y_3\text{s.t.}2y_1+y_2+y_3\ge 7,y_1+2y_2\ge 5,y\ge 0.$$

In general, the dual of $maxc·x$ subject to $Ax\le b$, $x\ge 0$ is $minb·y$ subject to $A^{\mathsf{T}}y\ge c$, $y\ge 0$. The primal has one variable per product and one constraint per resource; the dual has one variable per resource and one constraint per product. Taking the dual of the dual gives back the primal.

Weak duality, and the step not to skip

Proof, in one line:

$$c·x\le (A^{\mathsf{T}}y)·x=y·(Ax)\le y·b.$$

The first step uses $x\ge 0$ and $A^{\mathsf{T}}y\ge c$; the second uses $y\ge 0$ and $Ax\le b$. $◻$

Two consequences follow at once. If a feasible pair has equal values, both are optimal: no plan can beat $b·y$, and no price vector can go below $c·x$. And if the primal is unbounded, the dual has no feasible point at all.

Each sign condition is used exactly once, and dropping one breaks the proof. Take $y=(5,0,-3)$: its combination has coefficients $5(2,1)-3(1,0)=(7,5)$, a perfect match, and its right side is $70-18=52$. But the plan $(4,6)$ earns 58. A negative multiplier on a $\le$ constraint flips it into a $\ge$, and adding a $\ge$ to $\le$'s proves nothing.

bad = (5, 0, -3)
assert [dot(col, bad) for col in cols] == [7, 5]    # the coefficients match exactly...
assert dot(b, bad) == 52 < 58                       # ...but the "bound" is broken by (4, 6)

Where the gap comes from: complementary slackness

Expand the two inequalities of the one-line proof, and the gap between any feasible pair splits into non-negative pieces:

$$b·y-c·x=\sum _i{y}_i(b_i-a_i·x)+\sum _j{x}_j((A^{\mathsf{T}}y{)}_j-c_j).$$

The cross terms $y·Ax$ and $x·A^{\mathsf{T}}y$ are equal and cancel, which is all the proof takes. Each term is a product of two non-negative numbers: a price times the resource left over (its slack), or an amount made times how far the product's resources are worth more than its profit (its surplus).

That last condition is complementary slackness: a resource with stock left over has price 0, and a product that is made is priced exactly at its profit. It turns "is this optimal?" into checks one product and one resource at a time.

At $(4,6)$ with prices $(3,1,0)$: the slacks are $(0,0,2)$ (two benches of market left) and the only leftover resource has price 0; both products are made and both surpluses are 0. Every term vanishes. Now try the corner $(6,2)$ with the same prices:

def slacks(x):
    return [bi - dot(row, x) for row, bi in zip(A, b)]

y = (3, 1, 0)
surplus = [dot(col, y) - cj for col, cj in zip(cols, c)]
assert slacks((4, 6)) == [0, 0, 2] and surplus == [0, 0]
assert slacks((6, 2)) == [0, 6, 0]
assert dot(y, slacks((6, 2))) == 6 == dot(b, y) - dot(c, (6, 2))

The check tells you what is wrong, not just that something is: at $(6,2)$ finishing time is left idle while the prices claim it is worth 1 an hour.

Complementary slackness also finds prices. At $(4,6)$ the limit has slack, so $y_3=0$. Both products are made, so both dual constraints are tight: $2y_1+y_2=7$ and $y_1+2y_2=5$, giving $y=(3,1)$. When a corner is degenerate this leaves a small LP rather than a linear system to solve.

def best(A, b):
    return max(dot(c, p) for p in corners(A, b))

assert best(A, [15, 16, 6]) == 61 and best(A, [14, 17, 6]) == 59 and best(A, [14, 16, 7]) == 58
assert max(corners(A, [15, 16, 6]), key=lambda p: dot(c, p)) == (F(14, 3), F(17, 3))

Strong duality: why the bound always meets

Weak duality says every price vector bounds every plan. It does not say the best bound meets the best plan. It does:

Geometric intuition, not a proof. At the optimal corner $(4,6)$ the cutting and finishing constraints are tight. Their outward normals, $(2,1)$ and $(1,2)$, point "out of" the feasible region. No direction that stays feasible improves the profit exactly when the profit direction $(7,5)$ lies in the cone between those normals: $(7,5)=3(2,1)+1(1,2)$. The coefficients of that combination, with 0 for the slack constraint, are the optimal prices.

That picture is Farkas' lemma: a vector lies in a cone, or a hyperplane separates it from the cone. Its proof, and the care that degenerate corners need, are skipped here. The simplex method of module 15 proves strong duality constructively. When it stops, the entries of its final objective row under the slack columns are a dual feasible $y$ with $b·y=c·x$. So a solver that finds the optimum can hand over the certificate at no extra cost, and the course's exact simplex returns it as y.

The rules table

Real LPs mix $\le$, $\ge$ and $=$ constraints, and some variables are free. The same idea, a combination that bounds the objective, gives the dual of any of them. A multiplier on a $\ge$ constraint must be $\le 0$ (so it flips into a $\le$), a multiplier on an equation may have either sign, and a free variable's coefficient must match exactly, since $x_j$ could be negative. For a max primal:

Weak and strong duality and complementary slackness hold for every pair built by this table. The two classic uses follow.

Minimax is duality

In a zero-sum game with payoff matrix $M$ (the row player receives $M_{ij}$), the row player picks a mixed strategy $p$ to maximize the payoff $u$ she is guaranteed whatever column is played:

$$maxu\text{s.t.}u-\sum _i{M}_{ij}{p}_i\le 0\text{ for every column }j,\sum _i{p}_i=1,p\ge 0,u\text{ free}.$$

Apply the table. Column $j$'s constraint is a $\le$, so its multiplier $q_j\ge 0$. The equation gets a free multiplier $v$. Each $p_i\ge 0$ gives a $\ge$ constraint, $v-{\sum }_j{M}_{ij}{q}_j\ge 0$, and the free $u$ gives an equation, ${\sum }_j{q}_j=1$. The objective is $v$. So the dual is

$$minv\text{s.t.}\sum _j{M}_{ij}{q}_j\le v\text{ for every row }i,\sum _j{q}_j=1,q\ge 0,$$

which is the column player's problem: hold the row player to at most $v$. Both LPs are feasible and bounded, so strong duality gives $maxu=minv$. That is von Neumann's minimax theorem, which module 14 used, now proved in one line.

Take $M=\left(\begin{array}{ccc}3& -1& 1\\ -2& 4& 0\end{array}\right)$. The row strategy $p=(2/3,1/3)$ guarantees $2/3$ against every column; the column strategy $q=(0,1/6,5/6)$ holds every row to $2/3$. Each strategy is a certificate for the other.

M = [[3, -1, 1], [-2, 4, 0]]
p, q = [F(2, 3), F(1, 3)], [0, F(1, 6), F(5, 6)]
row_pays = [dot(p, col) for col in zip(*M)]          # what p earns against each column
col_holds = [dot(row, q) for row in M]               # what each row earns against q
assert min(row_pays) == max(col_holds) == F(2, 3)
assert row_pays == [F(4, 3), F(2, 3), F(2, 3)]

Complementary slackness explains the zero in $q$: against $p$, column 0 pays the row player $4/3>2/3$. Its constraint is slack, so its multiplier $q_0$ must be 0. The column player never plays it.

Max-flow min-cut is duality

Module 11's pipeline sends water from $s$ to $t$; its maximum is 10, and the cut $\{s,a,b,c\}$ of capacity 10 proves it. Write the flow problem as an LP: one variable per pipe, a capacity constraint per pipe ($\le$) and a conservation equation per station. The table gives the dual one price ${\ell }_e\ge 0$ per pipe and one free number $d_v$ per station. After fixing $d_s=0$ and $d_t=1$ (a sketch; the bookkeeping is routine), it reads:

$$min\sum _e{\mathrm{c}\mathrm{a}\mathrm{p}}_e{\ell }_e\text{s.t.}{\ell }_{uv}\ge d_v-d_u\text{ for every pipe }u\to v,\ell \ge 0.$$

Along any path from $s$ to $t$ the $d$'s climb from 0 to 1, so the path's prices add up to at least 1: the dual asks for the cheapest way to "block" every path. A cut $S$ gives a feasible dual: $d_v=0$ inside $S$, 1 outside, and price 1 on each pipe leaving $S$. Its value is the cut's capacity. So weak duality is "every flow is at most every cut", and strong duality says the cheapest blocking prices cost exactly the maximum flow.

CAP = {("s", "a"): 4, ("s", "b"): 9, ("s", "c"): 6, ("a", "b"): 6, ("a", "c"): 5,
       ("a", "t"): 2, ("b", "d"): 8, ("c", "b"): 3, ("d", "t"): 9}
FLOW = {("s", "a"): 4, ("s", "b"): 6, ("a", "b"): 2, ("a", "t"): 2, ("b", "d"): 8, ("d", "t"): 8}
for v in "abcd":                                              # conservation
    assert sum(f for (p, w), f in FLOW.items() if w == v) == sum(f for (p, w), f in FLOW.items() if p == v)
assert all(0 <= FLOW.get(e, 0) <= cap for e, cap in CAP.items())
value = sum(f for (p, w), f in FLOW.items() if p == "s")

S = {"s", "a", "b", "c"}
d = {v: 0 if v in S else 1 for v in "sabcdt"}
price = {(u, v): 1 if u in S and v not in S else 0 for (u, v) in CAP}
assert all(price[(u, v)] >= d[v] - d[u] and price[(u, v)] >= 0 for (u, v) in CAP)
assert sum(CAP[e] * price[e] for e in CAP) == value == 10

The dual LP could in principle have a cheaper fractional optimum than every cut. It doesn't: module 11's theorem shows a cut always meets the flow, and module 17 explains why this LP always has an optimal corner with every $d_v$ and ${\ell }_e$ equal to 0 or 1.

The cost of checking

A certificate is a pair $(x,y)$. To check it, compute $Ax$ and $A^{\mathsf{T}}y$ ($mn$ multiplications each), $c·x$ ($n$) and $b·y$ ($m$), and compare: exactly $2mn+m+n$ multiplications, in exact arithmetic, whatever solver produced the pair. That is optimal up to a constant, since any checker must at least read all $mn$ entries of $A$.

Finding the pair is a solve. The course's exact simplex method (module 15) reports the duals for free, but a solve is much more work than a check. Counting the tableau cells the simplex rewrites against the check's multiplications, on one random LP per size ($m=n$, entries 1–9):

check_cost = [2 * n * n + 2 * n for n in (4, 8, 16, 32)]
assert check_cost == [40, 144, 544, 2112]
solve_cost = [100, 1134, 4624, 26136]
assert [round(s / k, 1) for s, k in zip(solve_cost, check_cost)] == [2.5, 7.9, 8.5, 12.4]

The ratio grows on these instances, because each pivot rewrites a whole tableau of about $2n^2$ cells and the number of pivots grows too. That is a measurement, not a theorem: the simplex method has no polynomial worst-case bound at all (module 17 builds an LP on which it takes exponentially many pivots), while the check is linear in the size of the input. The auditor's job really is easier than the planner's.

A problem that looks different

A courier firm claims that the fastest route from its depot to the hospital takes 11 minutes, on a map of 40 junctions and 90 one-way roads. Instead of a route list, the dispatcher hands you one number per junction and says: "check every road against these numbers, and you'll see that nothing beats 11." What must the numbers satisfy, and why would that be a proof? Nothing here mentions prices or products. The lab's last problem is a different one.

Practise

In the lab you draw the auditor's panel for a new LP, one frame per multiplier vector tried, and learn to spot a combination that is not a bound. You predict the slacks and the gap for several plans, then trace them. You find certificate prices by complementary slackness and solve a game from both players' sides. You count the cost of checking against the cost of solving. Finally you answer a request from a cooperative's board, which never says what it is.

Recap

You can now: write the dual of an LP with the rules table and read it as the best bound from combining constraints; prove weak duality in one line; certify or refute a claimed optimum with complementary slackness; read the dual variables as shadow prices; and derive the minimax theorem and max-flow min-cut as duality.

Invariant: for every primal feasible $x$ and dual feasible $y$, the gap $b·y-c·x$ equals ${\sum }_i{y}_i·{\text{slack}}_i+{\sum }_j{x}_j·{\text{surplus}}_j\ge 0$, so a pair with zero gap is optimal on both sides.

Complexity achieved: checking a certificate costs exactly $2mn+m+n$ multiplications, $O(mn)$, against re-solving (no polynomial bound for simplex) or trying up to $\left(\genfrac{}{}{0ex}{}{m+n}{n}\right)$ corners.

Failure mode: wrong signs on the multipliers. A negative price on a $\le$ constraint gives a "bound" that is not one: $(5,0,-3)$ claims 52 for a workshop that earns 58.

In real software: LP solvers report the dual values beside the solution. SciPy's scipy.optimize.linprog with the HiGHS methods returns them as res.ineqlin.marginals and res.eqlin.marginals, signed as the derivative of the minimized objective with respect to each right-hand side, and also reports each constraint's slack as residual.

Retrieval (module 11): when Ford–Fulkerson stops, why does the set of vertices reachable from $s$ in the residual graph have capacity equal to the flow's value?

Check yourself

1. Why do the prices $(3,1,0)$ prove that no workshop plan earns more than 58, and what is each of the two sign conditions for?
2. The market now takes at most 3 benches. What are the new optimal plan and prices, and why did the price of cutting hours drop to 0?
3. An auditor must confirm optimal plans for a 32 × 32 LP every day. Compare re-solving with checking a certificate: cost, and what each asks her to trust.

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.