What a constraint is worth

The rung below settled that a linear program and the program built from its transpose reach the same number, and left the second program looking like a device for proving something about the first. It has variables of its own, one for each constraint, and nobody has asked what they are.

The rate, and what “worth” means here #

Each dual variable is attached to one constraint of the primal program, and the claim of this essay is that it measures exactly one thing:

The dual variable $y_i$ is the rate at which the optimum changes when the $i$-th constraint’s right-hand side is relaxed by one unit.

Relax the first constraint of the program above from $b_1 = 12$ to $b_1 = 13$ and the optimum rises by $4/5$. The dual variable on that constraint is $4/5$. Those are the same number and not by coincidence, and the figure above is that statement checked at thirty of its own intervals rather than asserted.

The word worth in the title carries no more than that. It means worth in units of the objective: the objective is $3x_1 + 4x_2$, the right-hand side is a number on the other side of a $\le$, and a dual variable is a quantity of the first per unit of the second. It is not a cost, there is no market anywhere in this field, and nothing here is exchanged for anything. The rate is a property of a system of inequalities, in the same sense that a slope is a property of a curve, and the temptation to reach for currency should be resisted the whole way down — a program with the coefficients doubled has all its rates halved, which is a fact about arithmetic and about nothing else.

The consequence worth having is that the dual turns a solution into a list of rates: one number per constraint, saying what each one is doing to the answer. Two things happen to that list which are more interesting than the list itself. It is piecewise constant, so a rate is only a rate over an interval. And most of its entries are usually zero.

The program, and the stupidest possible solver #

Everything below is decided on one program in two variables:

$$\max\ 3x_1 + 4x_2 \quad\text{subject to}\quad 3x_1 + 2x_2 \le 12,\ \ x_1 + 4x_2 \le 10,\ \ x_1, x_2 \ge 0.$$

The solver is deliberately unimpressive. It forms every pair of constraints, solves each pair as a two-by-two system by Cramer’s rule, and throws away the points that violate something — which is how a corner of a cube gets found when the only tool available is checking all of them. Nobody would use it on a program of any size, and that is the point: no part of any picture here is about a clever procedure. How much work an optimiser does, and how that grows, is a question about cost, and cost belongs to another site in this fleet; this one owns duality as an equality and stops there.

The exactness is not fastidiousness either. A vertex is where two constraints hold with equality, and the question asked of it is whether it satisfies the others — several of which it lies exactly on. $3 \times 14/5 + 2 \times 9/5 = 12$ is a true statement; the same sum in floating point is a lucky one, and a count of feasible vertices that depends on which of those the machine computed is a rounding wearing a decision’s clothes. Every comparison in this family is on rationals.

Where the second number comes from #

The dual of that program is $\min\ 12y_1 + 10y_2$ subject to $3y_1 + y_2 \ge 3$ and $2y_1 + 4y_2 \ge 4$, with $y \ge 0$: the same coefficients read down the columns instead of along the rows, which is the transpose doing what a matrix does to a grid seen from the other side.

The dual optimum is $(4/5, 3/5)$ and $12 \times 4/5 + 10 \times 3/5 = 78/5$, which is what the primal is worth. The rung below stopped there, and it is worth noticing how little that settles about the two coordinates $4/5$ and $3/5$ individually. They are a certificate: a pair of non-negative multipliers that reproduce the objective out of the constraint rows and so bound the maximum from above. Nothing in that description says they mean anything.

Checked at every sample, not quoted #

The hero figure is the claim that they do. One right-hand side is swept over a range of whole numbers, the whole program is re-solved from scratch at each of them, and the optimum is drawn as the function of $b_1$ that it is. Then, on each interval of the sweep, two numbers are computed by routes that share nothing:

• the slope, from the difference of the two optima at the interval’s ends;
• the dual variable $y_1$, from the certificate at the optimal vertex of the program solved at the interval’s midpoint.

They are asserted equal as exact rationals. Over the default sweep that is thirty intervals, and $32 - 2 + 1 = 31$ whole values with a midpoint solve between each consecutive pair, so $31 + 30 = 61$ programs are solved to draw one graph. That is a fact about this sweep and not a bound on anything.

The result is three pieces with slopes $2$, $4/5$ and $0$. The middle piece is where the default program sits, and its algebra is short enough to see: with both inequalities binding, $3x_1 + 2x_2 = b_1$ and $x_1 + 4x_2 = 10$ give an optimum worth $4b_1/5 + 6$, so at $b_1 = 12$ the value is $4 \times 12/5 + 6 = 78/5$ and the slope is $4/5$. The dual variable was $4/5$. Two derivations that never met agree.

That is the sense in which a dual variable is a derivative — of the optimum with respect to a right-hand side, one-sided at the joints, and constant in between.

Two constraints, two lists #

Sweeping the other constraint asks a different question of the same program, and the answer is a different rate.

At $b_2 = 10$, the program’s own value, the second piece is in force and the rate is $3/5$: this is the $3/5$ of the dual optimum $(4/5, 3/5)$, arrived at from the other direction. The two rates are not comparable as measures of importance. Each is a quantity of objective per unit of its own right-hand side, and the two right-hand sides are numbers in different inequalities; a larger rate does not mean a more important constraint any more than one gradient being steeper makes one axis more important than another.

What is comparable is the shape. Both sweeps break twice, both end flat, and both begin steep. That is not an accident of the coefficients. The optimum as a function of one right-hand side is concave and piecewise linear for every linear program, because relaxing a constraint can only help and each successive unit can only help by less once other constraints begin to bind — convexity arriving as a property of the answer rather than of any drawn shape.

A rate is only a rate over an interval #

The breakpoints are the whole of the caution. Below $b_1 = 5$ the first constraint is worth $2$ per unit; above $b_1 = 30$ it is worth nothing at all, because by then the second constraint has taken over entirely and further relaxation of the first buys nothing. Anyone quoting “the value of constraint one” as a single number has quoted a value that is correct on one interval and wrong on two.

That is worth staring at, because both figures are correct and one of them cannot see something. The window decides which breakpoints appear; nothing in the narrow figure hints that the rate $4/5$ eventually stops. A rate read off a graph is a statement about the interval it was read on and about nothing outside it.

The joints themselves have no rate. At $b_1 = 5$ the slope arriving is $2$ and the slope leaving is $4/5$, so the optimum has no derivative there in the ordinary sense — the function is continuous, kinked, and perfectly well behaved, but the question “what is the constraint worth at $b_1 = 5$” has two answers. The right-hand-side axis is cut into intervals by which pair of constraints wins, in the same way the plane is cut into regions by which point is nearest, and the boundary belongs to both sides.

Every product is zero #

The second consequence is sharper and it is about which constraints matter at all.

The objective here is tilted to $3x_1 + x_2$, and that is deliberate. Run the same table on the untilted program and it is a true instance that illustrates nothing: at $(14/5, 9/5)$ both constraints bind with zero slack, both dual variables are positive — $4/5$ and $3/5$ — and both variables are in use with zero reduced cost, so all four products are zero for the same reason and there is no second reason on display. Tilted, the optimum moves to $(4, 0)$ and the four rows divide two and two.

Read the table row by row. The first constraint binds — $3 \times 4 + 2 \times 0 = 12$, no room to spare — and carries a dual variable of $1$. The second has slack $6$, since $4 + 6 = 10$, and its dual variable is exactly $0$. The variable $x_1$ is $4$ and its reduced cost is $0$; the variable $x_2$ is held at $0$ and its reduced cost is $1$. Every row multiplies to zero, and the two zeroes are not the same zero:

• a constraint with room to spare has a dual variable of zero, because relaxing something that is not pressing changes nothing;
• a variable sitting at zero has a strictly positive reduced cost, because it is sitting at zero for a reason.

That is complementary slackness, and it is an exact statement with no inequality left in it: for every $i$, either the slack is zero or the dual variable is, and never neither.

The two figures are the same sentence in two grammars, and that is the counting-two-ways of this essay. The table says the second constraint’s dual variable is $0$; the sweep says the optimum does not move when the second constraint is relaxed. Neither was computed from the other.

The other sensitivity #

Everything so far has moved a right-hand side and watched the optimum. There is a second thing that can be moved — a coefficient in the objective — and the answer to that question turns out to be the dual variables again, read a different way.

Tilt the objective. Keep $\max\ 3x_1 + c_2 x_2$ over the same region and ask how far $c_2$ can travel before the optimal vertex stops being $(14/5, 9/5)$.

A vertex is optimal exactly when the objective direction lies inside the cone spanned by the outward normals of the constraints binding there — otherwise some edge leaving the vertex improves the objective, and the optimum moves along it. The two binding rows are $(3, 2)$ and $(1, 4)$, so the condition is that

$$(3,\ c_2) = y_1(3,\ 2) + y_2(1,\ 4)$$

for some non-negative $y_1$ and $y_2$. The first coordinate gives $3y_1 + y_2 = 3$, so $y_1$ runs from $0$ to $1$; substituting into the second gives $c_2 = 12 - 10y_1$.

So the vertex stays optimal for $c_2$ anywhere between $2$ and $12$. At either end one of the multipliers hits zero, the objective becomes parallel to one of the two edges, and the optimum spreads along that edge before jumping to the next vertex.

Now put the program’s own value back. At $c_2 = 4$ the equation gives $y_1 = 8/10 = 4/5$, and then $y_2 = 3 - 3 \times 4/5 = 3/5$. Those are the dual variables — the same $4/5$ and $3/5$ that the sweep measured as rates and the certificate produced as multipliers, arrived at now from a question about the objective rather than about the right-hand sides.

That is the third description of the same pair of numbers, and it is the one that says what a certificate is. The dual variables are the coefficients that write the objective as a non-negative combination of the binding constraint rows. Read as multipliers they bound the optimum from above; read as slopes they say what each constraint is worth; read as coordinates in a cone they say how far the objective may be tilted before the answer changes.

The two sensitivities are not symmetric, and it is worth saying which is which. Moving a right-hand side moves the value continuously and the optimal vertex in jumps. Moving an objective coefficient leaves the vertex alone over a whole interval and then jumps it, while the value moves continuously throughout. Both are piecewise, both have breakpoints where a multiplier reaches zero, and the multiplier reaching zero is the same event in both stories.

The constraints that could be deleted #

Complementary slackness is therefore a statement about which constraints are doing work, and it is unusually blunt. A constraint with a dual variable of zero can be deleted from the program without moving the optimum. So can the whole crowd of them.

The optimum did not move, and the table says in advance that it could not have. Two constraints out of three are invisible to the answer: the optimum is determined by one inequality and one non-negativity condition, and everything else in the program is scenery. In two variables at most two constraints can be doing the work at any one vertex, however many are written down, and the dual is the object that says which two.

That is the same move as the invention of throwing things away — the observation that a question has a small skeleton and that the rest of the description can be discarded without changing the answer, provided the discarding is justified rather than guessed. Here the justification is a table of products, checked entry by entry, and it is available before anything is deleted.

What the family refuses to draw #

Two cases are refused by name rather than drawn badly, and both refusals say something.

The first is a degenerate optimum: three or more constraints passing through the same point. Add $4x_1 + x_2 \le 13$ to the original program and it passes exactly through $(14/5, 9/5)$, where the two original constraints already meet. The optimum does not move, but the dual optimum stops being a single point — the certificates $(4/5, 3/5, 0)$ and $(0, 13/15, 8/15)$ both reproduce the objective, both are non-negative, and both are worth the same, since $10 \times 13/15 + 13 \times 8/15 = 78/5$. There is then no such thing as the dual variable of a constraint, and no honest single-valued table of products. The generator tries every pair of binding rows, finds two certificates that disagree, and refuses. Drawing the case is not possible, because what would have to be drawn is a whole set of prices where the picture has one column.

The second refusal is finer. The sweep visits whole numbers, and a breakpoint need not be at a whole number. Sweeping the third constraint of the three-constraint program above meets one at $b_3 = 5/2$, where the second constraint begins to bind, and the generator stops rather than drawing a straight segment across it. It can tell, because the optimum is solved at each interval’s midpoint too, and a concave function with a kink inside an interval is strictly above the average of its endpoints there. A hidden breakpoint is the only way this drawing could lie, and it is exactly the thing the extra solve is for.

What the picture cannot show #

The theorem is a statement about every linear program with a bounded optimum. The figures are one program, or three, and what they establish is finite: on this program, at these sampled right-hand sides, the slope of the optimum equalled the dual variable computed independently, every time, and every complementary product was exactly zero. That is a genuine exhaustion of a small claim, not a small sample of a large one — but it is a small claim.

A finer sweep would add something real and something else not at all. It would add resolution about where the breakpoints are: a sweep in half-units would locate $b_3 = 5/2$ rather than refusing, and a sweep in tenths would place a breakpoint at any tenth. It would not make the equality of slope and dual variable any more general, because that equality is being checked at points, and no number of points is a proof over a continuum. Nor would it reach the theorem’s actual content, which is a claim about programs in any number of variables — where a region has no drawing at all and the argument is a separating hyperplane with no picture in it.

What the drawing does settle is the part most often taken on trust: that the sentence “the dual variable is the rate of change” is a checkable identity between two computed rationals and not a gloss. It has been checked, on every interval of every sweep here, and it has never once been off.

Where the ladder goes next #

Two rungs of this anchor have now produced a number that both sides reach, and a reading of the dual’s coordinates as rates that vanish on everything not doing work. The table has only so many shapes a row can take — a constraint with slack and no rate, or a constraint with a rate and no slack; a variable in use with nothing to spare, or a variable held down with something to spare — and a rigid little list of possibilities like that, exhausted rather than sampled, is the same pleasure as three gap lengths and never a fourth.

The next rung takes the same equality into a setting where the two sides are not a program and its transpose but two cautious parties choosing against each other, and the number they meet at acquires a second name. Nothing new is proved there. What changes is what the two numbers are called, and that is exactly the kind of re-labelling that counting one object twice has been doing to this collection from the beginning.