Solving a problem you never wrote down

Column generation and branch-and-price, built from a workshop cutting boards.

Boards come 25 feet long. Today's order is three pieces of 4 feet, six pieces of 9 feet and seven pieces of 10 feet. Cut each board however you like, cutting is free, and whatever is left at the end of a board is scrap.

How few boards do you need?

Have a go before reading on. It is a genuinely small puzzle, and there is a version of it you can settle in your head in about twenty seconds.

The answer is seven. But the seven is not the interesting part. The interesting part is that getting there takes two separate pieces of work, and only one of them is easy.

Showing seven is enough is easy: cut seven boards sensibly, lay out the pieces, count. Anyone can check it. Ruling out six is the hard half, and you cannot get there by trying arrangements, because there are far too many to try. You need an argument covering every arrangement at once, including the ones nobody thought of.

That asymmetry is the whole subject. And it gets worse in an interesting way: the best method anybody has for manufacturing those arguments automatically works with about four trillion unknown quantities on a real order, far more than any machine could store. It solves the problem anyway, by keeping almost every one of them missing and letting the problem itself say which one to fetch next.

That is what this guide builds.

Reading order. Chapters 1 to 3 set up the workshop and show that the obvious way of writing the question down is much weaker than a second way. Chapter 4 is why that second way cannot be written down at all. Chapters 5 to 9 build the loop that solves it regardless. Chapter 10 puts that loop inside a search, and confesses to two bugs that cost this repository real answers. Chapter 11 is what all of it is called in the literature.

This guide leans on the duality guide from chapter 6 onwards, and says so each time it does. Chapters 1 to 5 need nothing but arithmetic.

Numbers below come from the code in this folder, in exact fractions, and every one of them is checked by a test.

0What this is

Here are two arguments for why six boards cannot be enough. Both are correct. Only one of them is any use, and the difference between them is the entire subject.

First argument: count the wood. The order asks for (3×4 + 6×9 + 7×10) ÷ 25 = 136 ÷ 25 = 5.44 boards worth of wood, so even if not one inch were wasted, five boards cannot supply it. At least six.

Second argument: count the long pieces. Call a piece long if it is 9 feet or 10. The three shortest long pieces together are 9 + 9 + 9 = 27 feet, and a board is 25, so no board can carry three long pieces. Two is the most any board can hold, however it is cut. The order asks for 6 + 7 = 13 long pieces. At two to a board, 13 ÷ 2 = 6.5 boards are needed, and you cannot buy half a board.

At least seven.

And seven can be cut, so seven is the answer and the question is closed. That took twenty seconds and you checked it yourself.

Now look at what separates those two arguments. Both are lower limits. Both were obtained by ignoring some of what makes the problem hard. One of them is worth 1.06 boards more than the other, and that 1.06 is the difference between "the answer is six or seven or more, keep searching" and "the answer is seven, stop".

When people say a way of writing down a problem is stronger, this is the entire meaning. It produces limits closer to the truth, and a limit closer to the truth is what lets you stop searching sooner.

The catch is that nobody hands you the second argument. It came from noticing something about this particular order, and a real order has hundreds of lengths, where nothing whatever will be noticeable. What we need is a procedure that manufactures arguments of that quality without any noticing.

There is one. Its price is that it works with one unknown for every way of cutting a single board. Six of them for this order, once the wasteful ones are thrown out. For a paper mill, still a hundred and eighty-eight billion after the same cull, and getting on for four trillion if you keep the wasteful ones too.

In one sentence. Finding a good answer is easy and proving nothing beats it is hard, and how well you can prove it depends entirely on how the question was written down.

1The order

A workshop buys boards 25 feet long and needs shorter lengths cut from them.

Boards are identical and there are plenty of them. Each is cut once, however you like, and the leftover at the end is waste, since two offcuts cannot be glued together. Use as few boards as possible.

A pattern is one way of cutting one board. For this order there are only six worth using, in the sense that no further piece could be squeezed into the leftover:

Six patterns is few enough to draw on a single page. Enjoy that while it lasts; chapter 4 is where it stops being true.

In one sentence. A pattern is one way of cutting one board, and the decision to be made is how many boards to cut with each.

2The obvious model, and why it is too weak

Chapter 0 gave two hand-made arguments about this order. This chapter and the next are where they come from, and getting there needs two words.

To model a problem is to write it down as unknown quantities to be solved for, together with the arithmetic those quantities must satisfy. To relax a model is to then cross out one of those requirements on purpose, producing an easier problem a computer can solve quickly.

The point of doing that is not the easiness. Every arrangement satisfying the original requirements still satisfies the shortened list, so the relaxed problem is choosing from a strictly larger set of candidates, and it may find something in there the real problem could not have used. Here the aim is to use as few boards as possible, so a larger set of candidates can only bring the answer down, never up. Whatever number the relaxation reports is therefore a floor under the true one. That is where a lower limit comes from when nobody hands you a clever argument.

The requirement that gets crossed out is nearly always the same one: whole numbers. Real answers here are whole boards and whole pieces, and insisting on whole numbers is what makes a problem hard. Let the quantities go fractional and it becomes easy. So every lower limit in this guide comes from the same recipe: write the problem down, allow fractions, solve, read off the floor. The standard word for such a floor is a bound.

Now do that to the obvious model. The natural way to write cutting stock down is to decide, for each board, what comes off it: take a pile of boards, mark some of them "used", and assign pieces to them without overfilling any. The unknowns are the marks and the assignments, and every one of them is a whole-number yes-or-no.

Allow fractions, so a board may be 30% used and a piece may be split across two boards, and the answer it gives is:

total length ordered ÷ board length = (3×4 + 6×9 + 7×10) ÷ 25 = 136 ÷ 25 = 5.44 boards

which is chapter 0's first argument, arrived at mechanically rather than by noticing anything.

Why exactly that ratio, though? Because once a piece may be sawn anywhere and its two halves counted against two different boards, nothing can be stranded. A board with 6 feet spare no longer wastes them: the next piece simply starts there and finishes on the board after. Every requirement about fitting has dissolved along with the whole numbers, and the only thing left for the model to respect is material. The order asks for 136 feet of wood, each board supplies 25 feet of it, none of which need go to waste. The bound is the ratio because the relaxation removed every other obstacle.

It is a genuine lower limit, and it is useless. This is the answer you would get if boards were liquid and the leftover at the end of one flowed into the next. Round it up and six boards might do.

Six boards will not do. And the relaxation cannot see it, because the fact that makes it impossible — a 10-foot piece sits on one board and stays whole — is precisely what was relaxed away.

In one sentence. Relaxing the obvious model throws away the very thing that makes the problem hard, so its bound is far too low.

3One variable per pattern

So write the problem down differently.

Instead of asking which pieces go on which board, ask how many boards to cut with each pattern, where a pattern from chapter 1 is one complete way of cutting one board.

That gives one unknown quantity per pattern. Six patterns, six unknowns. The standard word for one of those unknown quantities is a variable, and it is used from here on.

Here is what that buys. Every pattern is a way of cutting a board that is already legal: the pieces fit, by construction. So this model has nothing left to say about fitting. It only has to say that enough pieces come out:

choose how many boards to cut with each pattern, to minimise the total number of boards, so that for each length, the pieces produced across all patterns cover the order.

Relax that, allowing a fractional number of boards cut with a pattern, and the answer is 6.5 boards.

Where does the half come from? Look back at the six patterns drawn in chapter 1 and take two of them. Cut six boards into a 4, a 9 and a 10, which uses 23 of the 25 feet available. Then cut half a board into a 4 and two 10s, the one pattern on that page getting two 10-foot pieces out of a single board.

Count what comes out. Nine-foot pieces: one from each of the six boards, so six, and six were ordered. Ten-foot pieces: six from those boards, and a half board that would have given two gives one, so seven, and seven were ordered. Four-foot pieces: six and a half of them where three were ordered, so three and a half go in the bin. Every order met, and the boards used add up to 6 + 1/2.

Nothing does better, and you can see why without solving anything, because it is chapter 0's second argument again. Three long pieces never fit on one board, since the three shortest are 9 + 9 + 9 = 27 and a board is 25. So a board carries at most two of them however it is cut, which the six drawings bear out. And cutting half a board with a pattern yields half of each of its pieces, so that ceiling survives the relaxation: two long pieces per board of cutting, whole boards or not. Thirteen long pieces at two to a board needs 13/2, and the mix above sits exactly on that ceiling.

So here are two relaxations of the same order, on the same recipe and the same crossing-out of whole numbers, landing more than a board apart. Why they differ is the one idea the whole guide is built on, so let us be precise about it.

In the obvious model, the whole numbers were the fitting. Saying "this 10-foot piece goes entirely on board 3" is a whole-number statement, and allowing fractions is exactly what let the piece be sawn in half and spread across two boards. Crossing out the whole numbers destroyed the thing that made it a cutting problem at all.

In the pattern model, the whole-number work has already been done, once, correctly, inside each pattern. A pattern is a legal way to cut one board: the pieces fit, by construction, and nothing about that can be undone later. So when the relaxation allows two and a half boards to be cut with some pattern, it is not permitting anything physically impossible about fitting; it is only permitting a fractional count of boards. Fitting is out of the relaxation's reach, because it was settled before the relaxation arrived.

The second relaxation settles the question by itself. Everything that follows is the price of getting it.

(The standard name for this reformulation is Dantzig–Wolfe decomposition. Chapter 11 comes back to it; for now the idea is all you need.)

In one sentence. Deciding in whole patterns rather than in individual pieces settles the whole-number question in advance, so crossing it out later costs almost nothing.

4Too many to write down

Here is the bill for that.

The strong model needs one variable per pattern, and patterns multiply. A paper mill cutting a 5600mm roll into ten ordered widths has this many ways to cut one roll:

3,972,952,644,549 patterns. One variable each.

You cannot write that model down, you cannot store it, and you certainly cannot hand it to a solver.

Now the part that makes this recoverable rather than hopeless. Almost all of those variables are worthless: a good answer uses a handful of patterns and leaves every other one at zero. The difficulty is not the count.

It is that you cannot tell which handful matters until the thing is solved.

In one sentence. The strong model is unwritable, and almost all of it is irrelevant, but you cannot tell which part until you have solved it.

5Start with a few

The model cannot be written down. So do not write it down. Start with a model that is obviously far too small.

Take a few patterns, say the lazy ones with each board cut into copies of a single length, and solve that. Everyone calls it the restricted master: the real model, restricted to the handful of patterns somebody actually bothered to write down. It is the real problem with almost all of its variables missing.

Our order has three lazy patterns: a board cut into six 4-foot pieces, a board cut into two 9s, a board cut into two 10s. With only those three on the table there is nothing to decide, because each ordered length has exactly one source. Here is the whole calculation, and it is arithmetic you can do in your head:

• Three 4-foot pieces, six to a board, is half a board of cutting.
• Six 9-foot pieces, two to a board, is three boards.
• Seven 10-foot pieces, two to a board, is three and a half.

Add them up: 7 boards.

That number is an honest upper bound on the relaxation, since those three patterns really do fill the order. It is not yet a plan you could take to the saw: half a board of cutting is not a thing, and rounding each of the three up separately costs 1 + 3 + 4 = 8 boards. And it is certainly not the answer to the strong model, which has three more patterns nobody has written down, and in the mill instance four trillion.

So the method now needs one thing, and only one. Not a way to search the missing patterns; there are far too many. A way to answer whether any of them would help without adding them, and ideally without even looking at them.

That sounds like it should be impossible. The next two chapters are why it is not, and the surprising part is that the too-small model already contains the answer.

In one sentence. Solving a deliberately impoverished model is free, and the only question left is whether anything is missing from it.

6What the prices are telling you

Solve the restricted master and it hands back more than a number. It hands back prices, one per ordered length.

A price answers one specific question. Suppose the customer rang and asked for one more 9-foot piece: how much extra cutting would that cost, in boards? That number is the price of a 9-foot piece. The duality guide is where these come from and why one exists for every ordered length at once. At the first round they come out as

and each one is readable straight off the lazy pattern that supplies it. The only source of 4-foot pieces here is a board cut into six, so one more of them costs a sixth of a board. The only source of 9-foot pieces is a board cut into two, so one more costs half a board. The 10s the same, for the same reason.

Be clear about what these are. They are not the prices of the real problem. They are what this impoverished three-pattern model currently believes, and they will move as better patterns arrive.

Now the move the whole method rests on. Take any pattern, written down or not.

Cutting a board with it costs one board. The pieces that come off it are worth, at these prices, some amount. So the pattern is worth adding exactly when

the pieces it yields are worth more than one board.

Check that on the three patterns the model already holds. Six 4-foot pieces at 1/6 each: worth exactly 1. Two 9s at 1/2 each: exactly 1. Two 10s at 1/2: exactly 1. Three sums, all landing on 1, not one of them a help.

That is no coincidence. A pattern the model is already leaning on cannot be worth more than the board it eats, or the prices would never have come out of that model in the first place. Solving forced them to be consistent with everything on the table.

One board in, pieces worth some amount out. The difference between the two is what everyone else calls the pattern's reduced cost: below zero when the pieces beat the board, which is when the pattern is worth having, and zero for the three just checked.

Now look at what that test actually needs. The prices, and the pattern's own contents. Nothing else. No solve, no model, no list.

Which means a pattern nobody has ever written down can still be judged by it. That is the crack the rest of the method goes through.

In one sentence. A pattern is worth adding when its pieces are worth more than a board, a test that needs only the prices and the pattern itself.

7The same test, from the other side

There is a second way to say all of that, and we will carry both, because each one makes a different thing obvious.

Duality puts a rule on what a price list is allowed to be. Prices are legal only when no board anywhere can be cut into pieces worth more than the board costs. A list failing that test is promising value out of nowhere, and a price list that promises value out of nowhere can be used to argue for anything.

The rule has a name, dual feasibility, and its shape is what matters here: it is one condition per pattern. One for each way of cutting a board. All four trillion of them.

The prices from chapter 6 pass that test for every pattern in the restricted master, since solving that model is what forced them to. What is open is every pattern left out of it. And a price list has no way of knowing which patterns exist: it is a list of numbers, one per length, and nothing in it records what it has never been shown.

So there are two cases, and they are the two halves of the method.

If the prices pass for the unwritten patterns too, the list is legal for the full model. Then the duality guide's check applies exactly as written: a plan and a price list that agree end the search. The number the restricted master reported is the full model's number, proved without the full model ever being built.

If some unwritten pattern fails, the prices were only legal because that pattern was missing. Writing it down is precisely what will force them to move.

Which is why the two framings are one search. Hunting for a pattern worth more than a board, and hunting for a broken dual condition, are the same hunt seen from opposite sides, and the next chapter is how you run it without a list.

In one sentence. A price list cannot tell which patterns it has never been shown, so the whole method is the search for one that would embarrass it.

8Asking for a pattern is a knapsack

The question is whether some unwritten pattern yields more than one board's worth at these prices.

Searching a list of four trillion patterns is hopeless. But nobody said the answer has to be found. It can be built.

Here is the question again, phrased as a puzzle about one board. You have 25 feet of wood in front of you and a price for each length: a 4-foot piece is worth 1/6, a 9 is worth 1/2, a 10 is worth 1/2. Cut the board so as to make the pieces on it worth as much as possible in total.

What do you cut?

That is a knapsack problem, the standard name for "fill a container of fixed size with items of known size and value, as valuably as you can", and it is a small, fast, thoroughly solved kind of problem. But look at what it hands back. Whatever comes out is a pattern, and it is the most valuable pattern that exists at these prices. Not the most valuable one on any list. The most valuable one, full stop, including all the ones nobody has ever written down, because the knapsack constructed it from the wood rather than looking it up.

At the prices above it returns four 4-foot pieces and one 9-foot piece, worth 4×(1/6) + 1×(1/2) = 7/6. Seven sixths is more than one, so by chapter 6's test that pattern is worth having, and into the model it goes.

Notice what has just been avoided. No shortlist. No sampling. One knapsack solve either hands back a best pattern in existence (four patterns tie at 7/6 here, and any winner will do), or, when its best comes out at 1 or less, proves that no pattern anywhere would help, in which case the restricted model's answer is already the full model's answer.

Try it yourself → Set the three prices by hand and watch which pattern the knapsack builds.

In one sentence. Finding the missing column is a knapsack, and it returns the best pattern in existence or a proof that none would help.

9The loop, and why it is allowed to stop

Put the two halves together and they take turns.

Column generation

1. Start with any set of patterns that can fill the order at all.
2. Solve the restricted master. Read off the prices.
3. Solve the knapsack at those prices.
4. If its best pattern is worth more than one board, add it and go to 2.
5. Otherwise stop: no pattern in existence would help, so the restricted answer is the full model's answer.

Watch the number come down: 7 boards, then 6.875, then 6.5. Then the knapsack returns a pattern worth exactly 1 and the loop stops. Three patterns were added, and 6.5 boards is optimal for a model nobody wrote down.

Be exact about what step 5 claims, because it is stronger than it looks. Not that no better answer exists, but that no column exists which would improve this one. The knapsack searched every pattern implicitly rather than sampling some, so it is a proof, not a hunch.

On a slightly bigger order, 55-foot boards with four different lengths, there are thirty patterns worth using, and the loop settles having built five of them:

Twenty-five patterns were never written down and never needed to be. On the mill instance the same sentence holds with billions in place of twenty-five.

(The loop finishes holding six columns rather than five. The sixth is one of the lazy patterns it started with, a board cut into three 16-foot pieces, which leaves 7 feet spare and so is not one of the thirty worth using. It is still sitting in the model at the end, at zero.)

Try it yourself → Step the loop one round at a time and watch the prices move.

In one sentence. Alternating between a small model and a knapsack solves a model nobody wrote down, and the last round is the one that proves it.

10Branching, when the answer is 6.5 boards

Nobody cuts half a board. The relaxation says 6.5, and 6.5 is not a plan.

For this order rounding up happens to be right, and for cutting stock it nearly always is. The relaxation is famously tight, and instances where rounding up is wrong are rare and awkward to construct. But "nearly always" is not a proof, and a rounded bound is a number rather than a set of cuts. To get something you can take to the saw, the fractions have to be branched away.

The standard way to branch fractions away is branch and bound, and since this repository has no guide to it yet, here it is in full. Solve the relaxation. If some quantity comes out fractional, say a pattern used 2.5 times, then whatever the true answer is, it either uses that pattern at most 2 times or at least 3 times. There is no third case. So split the problem into those two smaller problems and solve each. Repeat, and you get a tree of ever more constrained problems.

Two things stop the tree from exploding. A branch whose extra restrictions make the problem impossible is dropped. And a branch whose relaxation already needs more boards than some whole-number answer you already have in hand cannot possibly contain anything better, so it is dropped too, unexamined.

That second one is where the whole value of a strong relaxation shows up. A bound of 6.5 prunes branches that a bound of 5.44 would have made you explore. Chapter 3 gets repaid here.

Branch-and-price is branch and bound in which the relaxation at every node of that tree is itself solved by column generation, since the model is still too big to write down at any node.

At each node

1. Impose the node's branching decisions on the master.
2. Solve that relaxation by column generation: the full loop, at every node.
3. Prune if it is impossible, or if its bound cannot beat the best whole answer found so far.
4. If the answer is whole, record it. Otherwise pick a pattern used a fractional number of times and split: one child uses it at most ⌊x⌋ times, the other at least ⌈x⌉ (those brackets mean round down and round up).

(The tree drawn is the bigger order from chapter 9, not the six-pattern one. This order branches away in three nodes, which makes for a dull picture.)

Each box hides a complete solve-price-add cycle. The tree stays small because it starts from a bound that is already nearly right.

Two traps, both of which cost this repository real answers

This is where the theory bit back. Both failures produced entirely reasonable looking trees and entirely wrong numbers.

A branching row has a price too. Tell a node "use this pattern at most zero times" and that restriction acquires a dual value, which inflates that one pattern's reduced cost. The knapsack then keeps nominating a pattern the master already holds and has pinned at zero. Reading that as "no improving column exists" stops the loop early and leaves the node's bound too high, and in a minimisation a bound that is too high prunes the optimum.

A restricted master can be infeasible at a node that is perfectly feasible. The columns that would have met the demand simply have not been generated yet. Declaring the node infeasible throws away real solutions. The fix is to give the master emergency columns at a punitive price, so it always has an answer and can produce prices; they fall out on their own as real patterns arrive.

Put both bugs back and the solver disagrees with brute force on 456 of 1230 test instances. Neither bug announces itself. The trees look sensible and the answers look plausible, and the only thing that caught them was running every small instance against an independent brute-force solver.

One more admission. Branching on a single pattern's count, as above, is a weak rule. Real implementations use Ryan–Foster branching, which splits on whether two pieces share a board and pushes the restriction down into the knapsack itself. This guide keeps the simpler rule for legibility and pays for it in tree size.

In one sentence. Branch-and-price is branch-and-bound whose relaxation is generated rather than written down, and the traps are all in the interaction between the two.

11Where this leads

The shape of what just happened is more general than cutting boards.

Dantzig–Wolfe decomposition is the name for what chapter 3 did. A problem with block structure is rewritten so its variables are whole feasible solutions of one block rather than the block's individual variables. Here the block is "one board" and its feasible solutions are the patterns. The new relaxation sits between the integer hull and the naive relaxation, which is the general reason it is tighter and why anyone tolerates the extra machinery.

Column generation is how you optimise over those solutions without listing them. The pricing problem generates them on demand, producing precisely the extreme points of the block that the current prices ask for.

Benders decomposition points the same idea the other way. It generates rows rather than columns: fix the hard decisions, solve what is left, and take the dual of that leftover problem as a new constraint to send back. Every Benders cut is a price list doing exactly the job it did in chapter 7, proving a proposal cannot be as good as it claims.

When pricing is just filtering a list

A case that resembles the above and is not.

Suppose the columns are not defined by a polyhedron but pre-generated: a fixed list of candidate driver schedules, say, computed in advance. Then there is no optimisation problem to solve for the best column. You scan the list and take the best reduced cost. The algorithm still works and the surrounding branch-and-price machinery is unchanged.

But it is no longer generating the extreme points of a block. It is reduced-cost filtering of a discretised approximation of one, and the bound you get is a bound for that approximation. If a schedule you needed is absent from the list, nothing in the method will ever say so. Whatever produced the list made a modelling decision on your behalf.

What the plain words are really called

Further reading

The cutting-stock treatment here follows the spirit of chapters 2.2 and 8 of Integer Programming by Conforti, Cornuéjols and Zambelli, which is the place to go next and does properly what this page does with pictures.

Running the code

make bootstrap    # once, from the repository root
cd branch-and-price && make verify

The solver reuses the exact-fraction simplex from the duality topic rather than carrying a second copy. This topic really is that one under load. The tests check the mathematics, the prose against the code, and branch-and-price against a brute-force solver that enumerates every pattern.