Pruning

A studio is recording an audiobook of War and Peace (the Russian original). The first part of the epilogue, sixteen chapters, is read by four people at once, and the part is done when the busiest one finishes. Who gets which chapters? There are 4¹⁶ ways to hand them out, more than four billion, and the search tree, where each level decides the fate of one chapter, has almost six billion nodes. Below is this search on the real chapters of the novel. The ladder at the top of the scene adds prunings one after another and counts the nodes the search had to open. Under it are switches: remove any pruning or add an unsafe one.

A search that gives no reader more than the best time found so far does not finish even within three million nodes. If the long chapters are handed out first, there are 2,503,341 nodes; if readers with equal loads are not told apart, 20,355. One more check, whether the readers have enough room left for the remaining chapters, and one node remains: the root. The search had nothing to search, because the greedy method at once found a plan with 33 minutes each, and nothing better than 33 minutes exists; that is visible before starting. Switch minutes to words, and the picture changes. More on that below.

The idea

A search builds a solution step by step and walks the tree of options. Pruning is declining to open a subtree about which it is already clear that it holds nothing useful: its solutions are no better than the one found, or there are none at all, or it is a mirror copy of a branch already walked. One check at a node saves everything below it, so a pruning is the more valuable the closer to the root it fires.

Pruning by feasibility, when the start of a solution already breaks the rules, is covered in detail in the article on backtracking with sudoku and queens. Here the problem is an optimisation: we need not just some solution but the best one. Such problems have their own set of techniques, and all of them can be seen on the readers.

• The incumbent. The best solution found so far, the incumbent, serves as a bar: a branch that cannot beat the incumbent is not opened.
• A good incumbent early. The lower the bar from the very start, the more it prunes. A fast approximate method gives it, for example a greedy one.
• Order. Order by itself prunes nothing, but it decides how early the other checks fire.
• Symmetry. If two choices give mirror-image subtrees, it is enough to walk one.
• A lower bound. If even the luckiest continuation cannot beat the incumbent, the branch is not needed. And if the incumbent has reached the bound for the whole problem, the search can stop altogether.

Six prunings in turn

Take a smaller part, so that the search without tricks also finishes: Volume 2, Part 4, thirteen chapters, three readers. A chapter weighs as many minutes as it takes to read at 150 words a minute: from 4 to 17 minutes, 120 in all. The full tree has 1 + 3 + 3² + … + 3¹³ = 2,391,484 nodes. The numbers below were printed by the listing from the code section; in the scene, if you pick this part and three readers, you get the same.

1. Give no reader more than the incumbent: 32,957 nodes. The busiest reader reads at least as much as any other has already collected. If a chapter raises a reader’s load to the incumbent or above, this branch will not beat the incumbent. While there is no incumbent there is nothing to prune, but the very first finished solution gives a bar, and the tree at once slims down seventyfold.

2. The greedy incumbent from the start: 32,346. The greedy method (chapters in decreasing order, each to the least busy reader) gives 42 minutes. Ronald Graham proved in 1969 that it is off by a factor of at most 4/3 − 1/(3k), and that is a good starting bar. Here it helped little: the search found a plan no worse by itself within a few hundred nodes.

3. Long chapters first: 11,483. A long chapter placed last inflates the load low in the tree, when most of the work is already done. Placed first, it shows at once that a branch is hopeless. In backtracking the same principle is called “the hardest first”.

4. Equal loads are one reader: 1814. At the start all three readers are free, and giving the first chapter to the first, second or third is the same up to names. Without this check the search walks every solution 3! = 6 times, under every permutation of the readers, and indeed the nodes became 6.3 times fewer. The check is general: if two readers have the same load right now, their subtrees coincide up to a permutation, and one is enough.

5. The rest must fit: 43. The strongest check. If the incumbent is 42 minutes and we are looking for better, each reader can collect at most 41 minutes, that is, take at most 41 − load more. Add up this room over all readers. If it is less than the length of the remaining chapters, they cannot be handed out without missing the incumbent, and the whole branch can be closed. This is a relaxation bound: we allowed chapters to be split into pieces and asked whether there is room at least that way. If there is not enough even for split chapters, there is certainly not enough for whole ones.

6. Stop at the lower bound: 38. For the whole problem it is known from the start that the busiest reader reads no less than the longest chapter and no less than ⌈120 / 3⌉ = 40 minutes. As soon as the incumbent reaches forty, the search stops: nothing is better. Without this check it would prove optimality by walking the rest of the tree; here, admittedly, the rest is already almost empty, and the difference is only five nodes.

From 2.4 million nodes to 38: sixty thousand times fewer. And in the scene, on the epilogue with four readers, from six billion to one.

Why nothing is lost

Each pruning throws branches away blindly, without looking at what is in them. Why does the answer stay the best? Let us state what a pruning must be like to guarantee it.

Hence the rule: you may prune by a proved lower bound or by a proved equivalence. All six checks on the readers are of this kind. A reader’s load is a lower bound for any plan in the subtree, because loads only grow. The room left is a relaxation bound. Readers with equal loads are an equivalence: swap their names in all the solutions of one subtree and you get the solutions of the other at the same cost. And “long chapters first” and “the greedy incumbent” prune nothing themselves: they only make condition (a) satisfiable earlier.

Code

One search with six flags, and for each set of flags the number of nodes. Chapter after chapter is given to each reader in turn; the loads are kept in one array and rolled back after returning from the recursion. The order of the checks at a node matters for the count: first “is this a leaf”, then “is it time to stop”, then “will the rest fit”.

prunings                                nodes  busiest
cut a reader at the record              32957       40
+ the greedy record at the start        32346       40
+ the longest chapters first            11483       40
+ equal loads are the same reader        1814       40
+ the room left must fit the rest          43       40
+ stop at the lower bound                  38       40

The scene does the same, except that its search is written as a loop with an explicit stack rather than recursion, so that the browser has time to draw between batches of nodes. The order of moves and checks is the same, and the node counts match the listing exactly.

Minutes, seconds, words

The last lines of the listing are the same part in seconds and in words, with all six prunings.

in seconds: 3252 nodes, the busiest reader 2393, the lower bound 2390
in words: 3237 nodes, the busiest reader 5982, the lower bound 5975

There were 38 nodes; now there are more than three thousand, eighty-five times as many. The chapters are the same, the prunings are the same; only the precision of the numbers changed. In minutes there are many plans where all three read exactly 40, and the very first branches find one of them, after which the bound stops the search. In seconds the lower bound of 2390 is unreachable: the best there is is 2393. To prove that, the search has to walk everything the bounds did not prune. In the scene switch minutes to words for Volume 1, Part 3 and four readers, and the count runs into millions.

For splitting numbers into two equal piles this phenomenon has been studied precisely. Ian Gent and Toby Walsh noticed in 1996, and Stephan Mertens explained in 1998 with the methods of statistical physics, that the problem has a threshold: if each number has noticeably fewer bits than there are numbers, there are many exact splits and finding one is easy; if it has more bits, there is probably one exact split or none, and optimality has to be proved by search. Mertens called his survey of this “The easiest hard problem”. Minutes per chapter take a few bits, words twelve or thirteen: we crossed this threshold without changing anything but the units of measurement.

What it costs

In the worst case pruning does not help: the readers problem is hard (splitting numbers into two equal piles reduces to it), and there are inputs where there is almost nothing to prune. The bound stays O(kⁿ). The search takes O(n) memory: the path from the root and the loads.

Time is the number of nodes times the work at a node, and checks are not free. The room check costs O(k) per node, while a simple comparison with the incumbent costs O(1). The deal pays off if a check cuts away more than it costs: here it alone shrank the tree fortyfold. Below is a measurement on the first n chapters of Volume 3, Part 2, four readers, minutes: a search that prunes only by the incumbent, and a search with all the prunings. The time axis is logarithmic.

The search with only the incumbent grows as a smooth exponential: each new chapter multiplies the time by three to six, and at 17 chapters Go spends half a second. The search with all the prunings finishes in microseconds for most n, but not for all. At 22 and 23 chapters its time in Go jumps ten thousandfold compared with its neighbours; in Python these points would take seconds, and they were removed from the measurement. And at 29 chapters the search did not finish within many seconds in either language, and this point was removed from both measurements. This is not a bug in the program but a property of search known as heavy tails. Carla Gomes, Bart Selman and their co-authors showed in 2000 that for backtracking on similar inputs rare very long runs occur far more often than intuition suggests. Restarts with a random choice order help: out of ten short attempts one often slips past the trap where a single long one would have got stuck.

Unsafe prunings

The most tempting mistake is to prune by what is “most likely”. For example, by the average load: why give anyone more than ⌈sum / k⌉ if in a good plan everyone reads the same amount? In the scene, switch on the unsafe pruning, pick Volume 1, Part 3, four readers and words instead of minutes. The search walks eight and a half million nodes and answers: 9397 words, nothing better. That is the answer of the greedy method the search started from, and it is far from the best: the lower bound here is 9023 words, it is unreachable, and the best plan gives 9024. The unsafe pruning threw away every branch where someone reads more than 9023, that is, every solution better than the greedy one, and the search “proved” the optimality of an answer it never checked. Without a starting incumbent it would have answered that there is no plan at all. In minutes the same pruning “works”: there the bound is reachable. That is why such mistakes pass tests and live long.

The rule from the theorem is short: you may prune only by a proved bound or a proved equivalence. Two checks help to keep it. The first is to compare, on small inputs, the search with pruning against the search without: the answers must match. The second is to check each pruning separately, switching the others off: together, prunings sometimes mask each other’s mistakes.

Two more similar traps. Symmetry must be real: readers with equal loads are interchangeable, but readers with equal numbers of chapters are not. And a bound must bound what is needed: in A* a heuristic that overestimates the distance prunes the shortest path just as the average load pruned the best plan.

Where it works

• Integer programming. Branch and bound is search with pruning by a bound, where the bound comes from a problem with relaxed constraints: integer variables are allowed to be fractional and a linear program is solved. Ailsa Land and Alison Doig described this method in 1960, and solvers for scheduling, transport and cutting problems are built on it.
• SAT solvers. A search over variable values where each assignment immediately propagates its consequences, and each dead end turns into a new constraint that cuts off a whole class of future dead ends. More on this in the course chapter on hard problems.
• Games. Alpha-beta pruning in chess programs does not open moves that, it is already clear, the opponent will not allow. With a lucky move order it looks at roughly the square root of the number of positions full minimax looks at; Donald Knuth and Ronald Moore proved this in 1975. A walkthrough on noughts and crosses is in the course chapter on games.
• Databases. A table partitioned by dates does not read partitions that cannot satisfy the query’s condition, and storage formats like Parquet keep the minimum and maximum of each column chunk and skip whole chunks by them. This is pruning by a bound, only the branches are megabytes on disk.
• Geometry. Nearest-point search in a k-d tree does not look beyond a splitting plane if it is further away than the best point found.

History

The general method for optimisation problems, branch and bound, was published in 1960 by Ailsa Land and Alison Doig for integer programming. In 1969 Ronald Graham analysed the greedy assignment of jobs to machines (the very one that gives the readers search its starting incumbent) and proved that it is worse than the best by a factor of at most 4/3 − 1/(3k). In 1975 Knuth and Moore worked out how many positions alpha-beta pruning saves. And in 1998 Richard Korf built a search for partitioning numbers that first outputs the answer of Karmarkar and Karp’s differencing method and then improves it until it proves optimality: an early incumbent, order and bounds, all in one.

Problems

The first is the readers from the article: the greedy method is wrong on most tests, and a search without pruning runs out of time. In the second the chapters are to be recorded on 80-minute compact discs, and the goal is fewer discs; the prunings are the same, but the lower bound is trickier.