Matpic
mathematics, in pictures
Concept

Complementary slackness

The condition that every constraint a solution uses is tight in its dual, and every dual variable that is positive names a constraint met with equality. It is what turns two matching optima into a proof of each other, and it restricts an optimal solution to a much smaller set of candidates.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

What one more unit of constraint 1 is worth. The optimum of a linear program plotted against one of its right-hand sides, as an exact piecewise linear graph, with the breakpoints marked and each piece's slope named as a dual variable.

What a constraint is worth

The rung below settled that a linear program and its dual reach the same number. This one asks what the dual's variables are, and the answer converts a solution into a rate for every constraint — piecewise constant, zero on the constraints that are not doing any work.

applied · Duality A cheapest assignment, and the proof that it is cheapest. A 4 by 4 cost table with the cheapest assignment marked, and a row price and column price beside each. Every used cell's two prices add to its cost, and the prices total the assignment's cost.

A price for every person and task

The cheapest assignment can be found without comparing it to any other. Attach a number to each person and each task so that no pair's two numbers exceed its cost, and if the numbers add to an assignment's total, that assignment is cheapest — proved, by an argument that never mentions the alternatives.

applied · Assignment

Named alongside it

The objects these essays reach for when they reach for this one.

DualityAlgorithmAssignmentCertificateConvexityDerivativeFeasible regionLinear programLinear programmingMatchingOptimisationShadow price

All concepts