LP Duality, in depth: deriving the dual, weak and strong duality, complementary slackness, shadow prices and the dual simplex method

Deriving the dual: the best upper bound

Take a small production problem. Three products earn 5, 4 and 3 per unit. Three resources have 5, 11 and 8 units available, and the products consume them according to the rows of the constraints below.

maximise   5x1 + 4x2 + 3x3
subject to 2x1 + 3x2 +  x3 <= 5      (resource 1)
           4x1 +  x2 + 2x3 <= 11     (resource 2)
           3x1 + 4x2 + 2x3 <= 8      (resource 3)
           x1, x2, x3 >= 0

Ask a cheaper question first: can we prove the optimum is at most some number? Multiply each constraint by a non-negative multiplier y_i and add. If the combined coefficient of each x_j is at least its objective coefficient, then, since x ≥ 0, the objective is at most 5y1 + 11y2 + 8y3. For example y = (0, 0, 2) gives coefficients 6, 8 and 4, which beat 5, 4 and 3, so the optimum is at most 16. The best such bound is itself a linear program: the dual.

minimise   5y1 + 11y2 + 8y3
subject to 2y1 + 4y2 + 3y3 >= 5      (product 1)
           3y1 +  y2 + 4y3 >= 4      (product 2)
            y1 + 2y2 + 2y3 >= 3      (product 3)
           y1, y2, y3 >= 0

Solving both with HiGHS through SciPy gives the primal optimum x = (2, 0, 1) with value 13 and the dual optimum y = (1, 0, 1) with value 13. The bound is tight. Read y_i as the price of resource i: product 2 consumes resources worth 3 + 0 + 4 = 7 per unit but earns 4, so it is not made, and indeed x2 = 0.

Dualising any LP

Real models mix maximisation and minimisation, equality constraints and free variables. Rather than converting everything to one standard form, use the correspondence below. Each primal constraint gets one dual variable, each primal variable gets one dual constraint, the objective vector and right-hand side swap roles, and the matrix is transposed.

Read the table right to left to dualise a minimisation. Two checks catch most mistakes: the dual of the dual is the primal, and every sign follows from the bound argument. A ≥ constraint in a maximisation only helps bound the objective from above if multiplied by a non-positive number, and an equality can be multiplied by anything.

Weak and strong duality

Write the primal as max c·x subject to Ax ≤ b, x ≥ 0, and the dual as min b·y subject to Aᵀy ≥ c, y ≥ 0. For any feasible pair there is an exact identity that does most of the work in this article:

b.y - c.x  =  y.(b - Ax)  +  x.(A^T y - c)
             (dual price x primal slack) + (primal amount x dual surplus)

Both terms on the right are sums of products of non-negative numbers, so the gap is non-negative. That is weak duality. Two consequences follow at once: if the primal is unbounded, the dual is infeasible, and if feasible x and y have equal objective values, both are optimal.

Strong duality says that if the primal has a finite optimum, so does the dual, with the same value. The cleanest proof uses Farkas' lemma: exactly one of two systems is solvable, either Ax ≤ b with x ≥ 0, or y ≥ 0 with Aᵀy ≥ 0 and b·y < 0. The second is a certificate of infeasibility. If the primal optimum is z*, the system Ax ≤ b, c·x ≥ z* + ε, x ≥ 0 is infeasible for every ε > 0, and normalising its Farkas certificate yields a dual feasible y with b·y < z* + ε. The simplex method gives a constructive proof: its final reduced costs are a dual optimum.

Complementary slackness: a checkable certificate

The identity above also says when the gap is exactly zero: every term must vanish. For each constraint, either it is tight or its price is zero. For each variable, either it is zero or its reduced cost is zero. These are the complementary slackness conditions, and together with feasibility they are necessary and sufficient for optimality. In the example, resource 2 has slack (it uses 4·2 + 2·1 = 10 of 11), and its price y2 is 0. Product 2 has positive surplus (7 − 4 = 3) and is not made. The other constraints and variables are tight on both sides.

That gives an optimality certificate anyone can check with two matrix-vector products, without trusting the solver. Put a checker like this in tests whenever an LP drives a real decision.

import numpy as np

def check_certificate(A, b, c, x, y, tol=1e-9):
    """Primal: max c.x, Ax <= b, x >= 0.  Dual: min b.y, A^T y >= c, y >= 0."""
    A, b, c, x, y = (np.asarray(v, dtype=float) for v in (A, b, c, x, y))
    slack = b - A @ x               # per constraint, must be >= 0
    surplus = A.T @ y - c           # per variable, must be >= 0
    report = {
        "primal_feasible": bool((slack >= -tol).all() and (x >= -tol).all()),
        "dual_feasible": bool((surplus >= -tol).all() and (y >= -tol).all()),
        "gap": float(b @ y - c @ x),  # = y.slack + x.surplus
    }
    ok = (report["primal_feasible"] and report["dual_feasible"]
          and abs(report["gap"]) <= tol * (1.0 + abs(c @ x)))
    return bool(ok), report

A = [[2, 3, 1], [4, 1, 2], [3, 4, 2]]
print(check_certificate(A, [5, 11, 8], [5, 4, 3], [2, 0, 1], [1, 0, 1]))
# (True, {'primal_feasible': True, 'dual_feasible': True, 'gap': 0.0})
# For badly scaled models, scale tol by the magnitudes of A, x and y.

Complementary slackness is also a solving tool. Primal-dual algorithms such as the Hungarian method keep dual feasible potentials, move the primal only along edges whose dual constraint is tight, and adjust the potentials when stuck.

Shadow prices and their valid ranges

Because the optimal value equals b·y*, the dual solution tells you how the optimum moves when the right-hand side changes: one more unit of resource i is worth y_i*. These are shadow prices. In the example, resource 1 and resource 3 are each worth 1 per unit at the margin, and resource 2 is worth nothing because some of it is already unused.

The price is only valid while the optimal basis stays the same. Here the basis contains x1, x3 and the slack of resource 2. Solving the basis equations for a general right-hand side gives x1 = 2b1 - b3, x3 = 2b3 - 3b1 and slack2 = b2 - 2b1. With the other values held fixed, each must stay non-negative, which gives these ranges.

Sweeping each b_i through SciPy confirms these ranges: the optimum is piecewise linear and concave in b, so a price can only fall as you add more of a resource. SciPy reports duals in res.ineqlin.marginals for the minimised objective, so if you maximise by minimising −c·x you will see (−1, 0, −1) here. At a degenerate optimum the price can differ for increases and decreases.

The Lagrangian view

The same dual falls out of the Lagrangian, which is how duality generalises beyond LPs. Attach a multiplier y ≥ 0 to Ax ≤ b and form L(x, y) = c·x + y·(b − Ax). For any feasible x and any y ≥ 0, L(x, y) ≥ c·x because the added term is non-negative. So the dual function g(y) = max over x >= 0 of L(x, y) is an upper bound on the primal optimum.

Rewrite L as b·y + x·(c − Aᵀy). If any component of c − Aᵀy is positive, the maximum is infinite; otherwise it is b·y at x = 0. Minimising g is therefore exactly the LP dual. For convex problems the same construction gives the KKT conditions. For integer programs it gives only a bound, and the gap is what branch and bound must close, as discussed in the integer programming article.

The dual simplex method

The primal simplex method keeps the primal feasible and works towards dual feasibility, meaning non-negative reduced costs. The dual simplex method does the opposite: it keeps the reduced costs valid and pivots until the primal values are non-negative. It is the workhorse after a cut or branching bound is added to a solved LP, or a right-hand side changes: the old basis stays dual feasible, so a few pivots usually replace a fresh solve.

# Max-form tableau. Invariant: every reduced cost >= 0 (the basis is dual feasible).
while some basic value b_bar[r] < 0:
    r = argmin(b_bar)                         # leaving row: most negative basic value
    J = [j for j in nonbasic if T[r][j] < 0]
    if not J:
        return "primal infeasible"            # row r is a Farkas certificate
    # dual ratio test: the smallest ratio keeps every reduced cost >= 0
    j = argmin over j in J of reduced_cost[j] / -T[r][j]
    pivot(r, j)                               # same pivot operation as primal simplex
return "optimal"

The failure exit returns a Farkas certificate: a row whose non-negative combination of constraints cannot be satisfied.

Where duality shows up

Once you recognise duality, it turns up across algorithms and machine learning.

• Max flow and min cut. The dual of the max-flow LP is a fractional cut problem whose optimal solutions are integral, which gives the theorem in the max-flow min-cut article.
• Matching and covers. In bipartite graphs, the dual of maximum matching is minimum vertex cover, which is König's theorem. The weighted version gives the potentials behind the Hungarian algorithm; the bipartite matching article covers the unweighted algorithms.
• Min-cost flow. Dual variables are node potentials, and reduced costs cost(u,v) + pi(u) - pi(v) are what successive shortest path keeps non-negative; see advanced flow networks.
• Zero-sum games. The two players' LPs are duals, and strong duality is the minimax theorem.
• Machine learning. Soft-margin SVMs are solved in the dual, where kernels appear, and optimal transport has the Kantorovich dual over potentials.

Failure modes

• Sign errors when dualising. A ≥ constraint in a maximisation gets a non-positive dual variable. Dualise twice and compare, or derive the sign from the multiplier argument.
• Reading prices outside their range. A shadow price is a derivative. Multiplying it by a large change in capacity overstates the gain; re-solve or compute the range first.
• Solver sign conventions. APIs report duals for the problem they actually solved. Validate against a tiny problem whose duals you know, like the one above.
• No certificate. Floating-point solvers return approximately optimal points. Check feasibility and the gap before acting on the result.
• Integer models. Shadow prices from an LP relaxation do not describe the integer optimum. Use them as hints, not as valuations.

What to do next

1. Write the dual of the worked example yourself using the table, then solve both with scipy.optimize.linprog and confirm the values match.
2. Run the certificate checker on the solver output, then perturb x slightly and watch which check fails first.
3. Sweep one right-hand side, plot the optimum and match its kinks to the basis ranges.
4. Dualise an LP with an equality constraint and a free variable, then dualise it back to check your signs.
5. Write the max-flow LP for a small network, take its dual and identify the cut.
6. Implement the dual simplex loop on top of a tableau, add a new constraint to a solved LP and count the pivots compared with a fresh solve.