Two problems, one number

Linear programming duality, built from a workshop with three shelves.

Two people are standing in the same small workshop, and they want completely different things.

The owner is deciding what to build. There are 44 planks stacked in the yard, 30 hours of labour in the week, 32 hours on the saw, and all of that can become tables, or chairs, or any mix of the two. Which mix earns the most?

The buyer does not care what gets built. He wants to buy the place out, the planks and the hours and the saw time, the lot, and he has to name a price for each one. Naturally he would like to pay as little as the owner will accept.

Stop for a second and notice how little those two questions have in common. One is hunting for a maximum, the other for a minimum. One is about furniture, the other about raw materials. You can work either calculation from beginning to end and never once need a number from the other.

Both come out at $350.

Change the workshop and it happens again. Different stock, different products, different prices: the two answers still land on the same number. They always do, for every problem of this shape, and if you ever find a pair that disagrees you have made an arithmetic mistake somewhere. That is a theorem, and the fact that anyone could prove such a thing is most of why this subject exists.

Every planning problem has a second problem hiding inside it, about prices. Solving either one solves both.

But the reason to care first is smaller and sharper than any theorem.

Suppose you hand me a plan and tell me it earns $350, and I would like to know whether you have really found the best one. You cannot show me by listing plans. There are infinitely many, and a search that has stopped getting lucky looks exactly like a search that has finished. Every plan you produce says the same kind of thing, at least this much is possible, and no stack of those will ever add up to and no more.

So hand me the buyer's price list instead. If it bills $350, then in four multiplications I can check that no plan anywhere on earth beats $350. Not by examining them. By examining none of them.

That price list is a receipt, and the rest of this guide is where it comes from, why one always exists, and the four or five other things it turns out to be good for. It is also why a solver can tell you what a bottleneck is costing rather than only what to do about it, and what column generation and Benders decomposition are made of underneath.

The plan. Chapters 1 and 2 set up the workshop and show why trying things can never finish the job. Chapter 3 invents the second problem, and chapters 4 and 5 are the two halves of the theorem. Chapters 6 to 8 are what practitioners actually use it for. Chapters 9 and 10 fence off what it does not say.

Three shelves, two products, no equations anywhere.

Every number below is produced by the code in this folder and asserted by a test. Exact rationals throughout, so when this page says two things are equal, it means equal.

0What this is

Watch the two panels. They have nothing to do with each other.

On the left, the owner. Every combination of tables and chairs the stock will stretch to is a candidate, and the line sweeping across them is a line of constant profit, pushed outwards until the shelves will not allow any more. It comes to rest at $350.

On the right, the buyer. Every plank, every hour of labour, every hour of saw time needs a price on it. He would like the bill to be small, and what stops him pricing everything at nothing is that the owner has to agree. Offer $25 for a table's worth of ingredients when a table sells for $30, and the owner just keeps the materials and builds the table. So the bill gets pushed down until some product is on the verge of being worth more built than sold, and stops. $350 again.

Nothing in the left panel ever mentions a price. Nothing in the right panel ever mentions a plan. One line moves up, the other moves down, and there is no step in either calculation that could possibly have known where the other was heading.

They stop on the same number.

Once you have both halves, something becomes possible that neither half could do alone. Take the plan worth $350 and the price list billing $350, put them side by side, and a few multiplications confirm that nothing beats $350, without looking at a single other plan. That is what the rest of this guide is for.

In one sentence. Two questions about the same workshop that share no ingredients have the same answer, and each one's answer certifies the other's.

1The workshop

Here is the whole workshop, in five numbers and a bit.

Three things there is a limited amount of, two things to make out of them, one question: what is the most money that can come out of this building?

Every possible plan is a point on a picture.

Try one. Build 5 tables and 2 chairs: that uses 24 planks, 16 hours of work and 17 of saw time. All three fit, so the plan sits somewhere inside the shaded region.

Now push tables as far as they will go. You stop at 10⅔ of them, and it is worth asking which shelf stopped you. Not the planks — there is still a plank and a third to spare in the yard. It is the saw, which most people do not guess.

The edges of that region come out straight for one reason: building twice as much uses twice as much. That proportionality is the only assumption in this guide, and it is what gives the picture flat sides and sharp corners rather than curves.

Now find the best plan. Take all the plans worth some particular amount, which is a straight line, and slide the line outwards.

The last plan the line still touches is the best one: 9 tables and 4 chairs, worth $350.

It stops on a corner, and it was always going to. Slide a straight line across a straight-sided shape and the last point it touches is a corner, unless the line happens to be parallel to an edge — in which case it leaves along that whole edge, and the edge has corners at both ends. Either way, some corner does as well as anything. Every method in this repository is built on that one observation.

Try it yourself → Change what a table and a chair sell for, and watch the best corner jump from one to the next.

In one sentence. The plans form a region with flat sides, and the best one is always at a corner.

2A good plan cannot prove itself best

You have a plan worth $350. How would you know there is nothing better?

The obvious move is to try more plans. So try a lot of them.

The curve flattens. Now look at that flattening and ask what it is telling you, because the answer is nothing at all. A flat curve looks identical whether you have found the best plan or have merely stopped getting lucky, and nothing anywhere in the search can tell those two apart.

Being more thorough will not rescue it. The region is a continuum: seven tables and four and a half chairs sits inside it, and so does everything between that plan and its neighbours. Enumeration here is not slow. It is not defined.

The real trouble is deeper, and it is about what a plan is capable of saying. A plan you can actually build is a statement of the form at least this much is possible. Pile up as many as you like and you still have a floor, and floors do not become ceilings by being stacked higher.

We need a statement of the opposite kind — no more than this is possible — and no plan will ever be one. It has to come from somewhere else entirely.

In one sentence. Plans give you floors, never ceilings, so no amount of searching can certify that you are finished.

3Charging for the ingredients

So stop building things.

Put a price on each of the three things in stock instead: so much per plank, so much per hour of work, so much per hour of saw time. Any prices you like, as long as none of them is negative. This will look like a detour for about two paragraphs.

Those three prices imply a price for a table, because a table is 4 planks, 2 hours and 3 of saw time. Try $7 a plank, $3 an hour and nothing at all for the saw. Then a table's ingredients come to 4×7 + 2×3 = $34, and a chair's to 2×7 + 3×3 = $23.

Look at what just happened. A table sells for $30 and its ingredients are priced at $34. A chair sells for $20 and its ingredients are priced at $23. At these prices, both products are worth more as raw material than as furniture.

Now suppose that is true of every product, and follow any plan at all through two steps.

Step one. Whatever the plan builds, the ingredients it eats are worth at least what the finished goods sell for. That holds product by product, and a plan is nothing but a number of each, so adding up preserves it.

Step two. Those ingredients came out of the building, so they are worth at most what is in the building. You cannot use more planks than you own, and no price is negative.

Chain them together. What the plan earns is at most what its ingredients are worth, and what its ingredients are worth is at most the value of everything on the shelves. So the plan earns at most the value of everything on the shelves.

Now read that argument back and ask which plan it was about.

It never says. It holds for the best plan, the worst plan, and every plan in between, all at once. Which makes the value of the building at these prices a number that no plan can beat.

There is the ceiling chapter 2 said could not come from plans. It came from prices.

It needs one condition, the one we checked a moment ago:

every product is priced at least as high as it sells for

Both halves of that matter, and the animation is here to make the failure concrete.

Watch the left panel first. Raising the plank price alone covers tables long before it covers chairs, and while either bar is short the prices prove nothing whatever. A price list that covers one product and not the other is worth exactly as much as no price list at all. Not a weaker claim. No claim.

Then watch what happens once both bars clear their lines. There is room to trade a lower plank price for a higher hourly rate, stay legal the whole way, and bring the ceiling down.

Try it yourself → Set the three prices by hand and find out how low you can push the ceiling before one of the products slips under its price.

In one sentence. A price list that covers every product proves an upper limit on what the workshop can earn, without reference to any plan.

4Every honest price list is a ceiling

That claim carries the whole guide, so let us watch it happen on real numbers rather than take it on trust.

Take any plan; it does not have to be a good one. Take any price list that covers both products. Line up three numbers.

The plan builds 10 tables and 2 chairs, earning $340. The prices are $7 a plank, $3 an hour, nothing for saw time. Then:

• $340 ≤ $386, because every product is priced at least what it earns, so the ingredients a plan eats are worth at least what the plan makes.
• $386 ≤ $398, because a plan cannot use more of anything than there is.

So $340 ≤ $398.

Neither step used the fact that this was a good plan, or that these were cheap prices. Both would have gone through identically for any plan and any covering price list, which means every honest price list is a ceiling over every plan at once, all of them, simultaneously.

And here is the payoff. Find a plan worth $350 and a price list charging $350. The plan says the answer is at least $350. The price list says the answer is at most $350. There is nowhere left for the answer to be. You are finished, you know you are finished, and you never examined a second plan.

(The standard name for this is weak duality. You can forget the name; the two bullets above are the whole content.)

In one sentence. Any honest price list is a ceiling over every possible plan at once, which is why a matching plan and price list end the search.

5The gap closes, every time

So plans push up from below and price lists press down from above. Whether they actually meet is a different question, and nothing in chapter 4 gives the slightest reason to expect it. Two entirely separate calculations could perfectly well stop with a gap between them that no plan and no price list could close.

They meet. The best plan earns $350, the cheapest honest price list charges $350, and the band between them closes to a point.

You would be right to suspect this particular workshop of being rigged. So here are 320 more, invented at random, with different numbers of products, different numbers of shelves and different recipes. Each one solved twice from scratch: once for its best plan, and once, as a separate problem, for its cheapest prices.

Every point sits on the diagonal. Both sides are computed in exact fractions, so the largest disagreement across all 320 is zero: not a millionth, but the zero you get from subtracting a number from itself.

Be clear about what that picture is, though: 320 pieces of evidence, not a proof, and a warning that any explanation had better account for all of them. The proof exists, and chapter 10 shows its shape by looking at what happens when the conditions fail.

This is the theorem the subject rests on, and it is called strong duality.

Two problems, then. The one about plans is the primal; the one about prices is the dual. Each is built from the other by turning it inside out, and the little table from chapter 1 is where you can watch that happen.

The plans problem reads that table across. The first row says a table takes 4 planks, 2 hours and 3 of saw time; the unknowns are how many tables and how many chairs.

The prices problem reads the same table down. The planks column says planks go out 4 to a table and 2 to a chair; the unknowns are what to charge for a plank, an hour of work and an hour of saw time.

That single change of reading direction is the entire swap. Piece by piece, on these numbers:

• The workshop had three limits, one per shelf. The prices problem has three unknowns, one price per shelf. Rows became variables.
• The workshop had two unknowns, tables and chairs. The prices problem has two rules, one per product: a table's ingredients must be charged at $30 or more, a chair's at $20 or more. Variables became rows.
• $30 and $20 were the thing the workshop pushed up. They are now the floors those two rules have to clear.
• 44, 30 and 32 were the limits the workshop pushed against. They are now the thing being pushed down, since the bill for the whole building is 44 plank prices plus 30 hourly rates plus 32 saw rates.
• Every at most turned into an at least, and looking for the largest number turned into looking for the smallest.

Do that swap twice and you are back where you started, which is the sense in which neither problem is the original.

In one sentence. The best plan and the cheapest honest price list always agree exactly, which is what makes the second problem worth solving.

6Which rules are actually holding you back

The second problem starts earning its keep here.

The best plan is 9 tables and 4 chairs. Look at what it consumes: all 44 planks, all 30 hours, and 31 of the 32 hours of saw time. One hour of saw time sits there, unused.

Now look at the prices the second problem hands back: $6.25 a plank, $2.50 an hour, and nothing at all for saw time.

Spare saw time, zero saw price. Planks all gone, planks priced. Put those side by side and the pattern is hard to miss.

A resource with something left over is worth nothing; a resource that is all used up is worth something. Which, once you have said it out loud, is obvious. If saw time is not what is stopping you, nobody would pay you for another hour of it.

The same rule runs the other way, for products rather than resources. A product that gets built is priced at exactly what it earns. A product priced above what it earns is one you are better off not building, and sure enough, in the best plan its quantity is zero.

The pairing is called complementary slackness, and in practice it is the first thing anyone looks at, because it answers the question people actually have. Not "what should I do" but "what is in my way".

Try it yourself → Change the stock levels and watch which rules become binding, and which prices switch on and off in response.

In one sentence. The prices identify the bottleneck by being zero on exactly the constraints that have slack.

7What one more plank is worth

The prices are more than a ranking of what matters. They are exact rates.

The plank price is $6.25. That means one more plank in the yard is worth $6.25 of extra profit — to the penny, and you can watch it happen.

Add a plank. The plank line moves out, the best corner slides along the hours line, the profit goes up by $6.25. Add another. Same again.

So where does $6.25 come from? Not from a plank being worth that much to anybody. It comes from what the extra plank lets the workshop rearrange. The best plan is pressed against two rules at once, planks and hours, and the hours are just as scarce as they were a moment ago, so the plan cannot simply grow. It has to trade one product for the other along the hours line.

Every arriving plank buys the same trade in the same proportions, so the easiest way to see the rate is to scale the trade up until it comes out in whole furniture. At that size it reads: 3 more tables, 2 fewer chairs, 8 more planks. Check it against the recipes in the chapter 1 table.

• Planks. The 3 new tables need 12. The 2 dropped chairs give back 4. Net cost, 8 planks, which is exactly what arrived.
• Hours. The 3 tables need 6. The 2 chairs give back 6. Net zero, so the hours are as full after the trade as before, and the plan is still legal.
• Money. 3 tables at $30 is $90 in. 2 chairs at $20 is $40 out. The trade is worth $50.

Fifty dollars for eight planks. That is $6.25 a plank, and it is where the number comes from. How long you can keep making that trade is a separate question, and chapter 8 answers it.

This is what a dual variable is, and why the name shadow price stuck.

One warning about what kind of number it is. Planks might cost $3 at the yard. Here the forty-fifth one is worth $6.25, not because planks are valuable, but because of what else this particular workshop happens to be short of. Move the workshop and the number moves. It is a price to this building, given everything else it has, and that is exactly the number you want when deciding what to buy, what to negotiate for, and what a bottleneck is costing you.

Watch the end of that animation, though. The rate stops.

In one sentence. A dual variable is the exact rate at which the answer improves per extra unit of that resource.

8The price is only local

Keep feeding planks in and eventually the saw becomes the problem instead. From that point on, extra planks pile up in the yard and are worth nothing.

The whole curve is three straight pieces, and the plank price is the slope of the piece you happen to be standing on:

Both bends have a reason, and the odd-looking one has the better reason.

The first bend, at 20 planks. Compare the two products by what each gets out of a plank. A chair uses 2 planks and earns $20, which is $10 a plank; a table uses 4 and earns $30, which is $7.50. So while planks are the only thing running out, build chairs and nothing else, and every extra plank is half a chair, worth $10. That lasts until the chairs run into a different shelf. Ten chairs take 30 hours of work, and 30 hours is all there is; ten chairs also take exactly 20 planks. Twenty planks is where the hours run out and the cheap ride ends.

The second bend, at 45 ⅐ planks. Now the odd one. Past 20 planks, arriving planks have to buy their way in through the trade from chapter 7: eight planks in, three tables up, two chairs down. That trade leaves the hours alone. It does not leave the saw alone. Three more tables want 9 hours of saw time and two fewer chairs give back 2, so every swap of eight planks quietly eats 7 hours of saw time.

And how much saw time is there to spare? One hour, the one from chapter 6. One spare hour against 7 per swap buys you one seventh of a swap, and one seventh of eight planks is 1 ⅐ planks.

That is the whole of the ⅐. One spare saw-hour divided by the seven a swap consumes.

Which puts the workshop 1 ⅐ planks away from its plank price collapsing to nothing. That is a narrow shelf to be standing on, and standing on it unknowingly is the most common way this whole idea gets misused. A shadow price quoted without the range over which it holds is close to useless.

One last thing the picture is telling you: the pieces get flatter, never steeper. Easy uses go first, so more of a resource is never worth more per unit than the last lot was, and the curve can only bend one way.

Try it yourself → Slide the stock of any of the three resources and watch its own price step down.

In one sentence. A shadow price is a local slope with an expiry date, so it always has to be quoted with the range over which it holds.

9Profit that runs away

Two things can go wrong, and the price side has something to say about both. Here is the first.

If the rules leave a direction the workshop can travel forever, there is no best plan. Nothing stops it, the profit is unbounded, and there is simply no number to report.

Now ask what the price side makes of that. An honest price list has to be a ceiling over every plan at once, which is chapter 4. A ceiling here would have to be a number larger than every plan, and no such number exists. So there is no honest price list either — not a bad one, not a loose one, none at all.

So one failure drags the other with it: if the plan side runs away, the price side has nothing whatever to offer.

Only that direction, mind. Both sides can be empty at once, which is what happens to the order for 12 tables in the next chapter, so an absent price list does not on its own mean the profit is running away.

Which is also how a solver tells you. Hand it a model with a direction of escape and it does not search forever and give up. It finds the direction, reports unbounded, and the evidence it hands back is a fact about the prices.

In one sentence. Profit running away on one side is exactly the same event as no honest price list existing on the other.

10A plan that cannot exist

The second failure is the more interesting one, because of how it gets settled.

Suppose an order arrives for 12 tables. Forty-four planks make eleven tables, so the order cannot be met, and there is nothing surprising about that. What is worth watching is how it gets settled: by arithmetic you can do on the back of an envelope, rather than by a search that eventually gives up.

Two rules do all the work. Written out flat, with no symbols:

The plank rule. Each table takes 4 planks and each chair takes 2, and there are 44 planks in the building. So four times the number of tables, plus twice the number of chairs, comes to 44 at most.

The order. The number of tables must be 12 or more.

Now take a quarter of the plank rule. Cutting every number in it to a quarter of itself leaves it just as true, so four times the tables becomes plain tables, twice the chairs becomes half the chairs, and 44 becomes 11.

A quarter of the plank rule. The number of tables, plus half the number of chairs, comes to 11 at most.

Hold that against the order. Tables plus half the chairs come to 11 at most, while the tables on their own are already 12 or more. Take the tables away from both. What is left on one side is half the chairs, and what is left on the other is 11 minus 12:

half of the chairs, at most −1.

Chairs get counted, and counts do not go below zero. Even building no chairs at all gives 0, and 0 is bigger than −1. So the two rules describe no pair of numbers whatsoever. There is no plan to find, and the argument took a minute to check and settles the question for every plan at once, forever.

Now look again at what that proof was made of: a quarter of one rule, plus all of another, added together. A weighted mixture of the rules, exactly like the price lists of chapter 3, except that this mixture lands on something absurd instead of on a ceiling. It is called a Farkas certificate, and the fact that one always exists when a system is impossible is the fact strong duality is built on.

One footnote to chapter 8 before we leave, because it is how this bites people in practice. At a bend in that curve the price is not unique. Standing exactly at 45 ⅐ planks, one more plank is worth nothing and one fewer costs $6.25, and both numbers are legitimate prices. A solver will hand you one of them without mentioning the other. This is called degeneracy, and it is why a sensitivity report should be read as a range and never as a point.

In one sentence. Impossibility always has a short arithmetic proof, built by mixing the rules exactly the way a price list mixes them.

11Where this leads

Everything above is one small problem solved by hand. What makes duality worth this much attention is what gets built on top of it.

• The simplex method decides which product to bring into a plan by asking whether its dual row is violated. The "reduced cost" in any solver's log is the amount by which a product's ingredients cost less than it earns.
• Column generation turns that around. When there are too many possible products to write down, solve with a few, read the prices off the dual, and use those prices to ask whether some product you have not written down yet would be worth adding. The prices are the entire interface between the two halves.
• Dantzig–Wolfe decomposition is that idea applied to a problem with repeated structure, and branch and price is what you get when the pieces have to come out whole.
• Benders decomposition cuts the other way: fix the hard decisions, solve what is left, and take the dual of that leftover problem as a new rule to send back. Every Benders cut is a price list from chapter 3, doing the job it did there: proving a proposal cannot be as good as it claims.

The next guide, along the edge, or through the middle, takes the first of those apart: how the walk uses the dual row to choose, and what a rival method that refuses corners does instead. Solving a problem you never wrote down is the second of them under load.

What the plain words are really called

Every invented phrase in this guide has a standard name. They are here so that anything you read next is legible.

Running the code

make bootstrap    # once, from the repository root
cd lp-duality && make verify

The solver uses exact fractions throughout and Bland's pivoting rule, which is slower than the usual choice and cannot cycle. It is about 250 lines and is meant to be read. The tests check three separate things: that the mathematics is right, that the numbers written on this page still match what the code produces, and that the interactive pages compute the same values the Python does.