Branch and bound

The air network has 3468 airports and 37,733 pairs with a direct flight in both directions. What is the largest group of airports where you can fly from each to each without a connection? This is the maximum clique of a graph, a problem for which no fast algorithm is known. Branch and bound finds it and proves there is no larger one: 38 airports. The upper bound decides everything. If you assume a clique can take in all the remaining candidates, the search tree grows to 1,123,506 nodes. If you bound it by the number of colours in a colouring of the candidates, to 242.

Under the map is a fork. The orange line is the size of the best clique found, and it only rises. The blue one is how much the unexplored part can still give, and it only falls. When they meet, the search is over: nothing better exists. With the colouring bound the blue line starts low, and branches are cut off right at the root.

The idea

Backtracking builds a solution step by step: here it adds to the clique one airport after another from those connected to all already taken. Branch and bound adds two numbers to it. The incumbent is the best solution found so far. The bound of a branch is a number guaranteed to be no less than the best solution inside it. If the bound is no greater than the incumbent, the branch is not opened.

A branch in which nothing better than the incumbent can be found may be skipped entirely; for this you need a bound that never underestimates. The closer the bound is to the truth, the more branches are cut off; an expensive but accurate bound often pays for itself many times over.

The colouring bound

The simplest bound for a clique is “those taken plus all candidates”: you cannot take more than there are candidates. But there are hundreds of candidates and a clique among them has dozens, so such a bound cuts off almost nothing. A colouring works more precisely. Colour the candidates greedily: each vertex gets the first colour in which it has no neighbours yet.

Etsuji Tomita and Tomokazu Seki made a fast algorithm out of this in 2003. The candidates are ordered by colour and tried from the end, from the highest colour. A vertex's colour number is a bound for all candidates up to and including it: there are no more colours than that among them. As soon as “taken + colour number” is no greater than the incumbent, the whole remaining tail of the branch is discarded with one comparison. The colouring is recomputed at every node: it is expensive, but it pays for itself a thousandfold.

Code

Airports are sorted by the number of connections: strong vertices give a good incumbent sooner. The listing compares both bounds on the hundred best-connected airports: on the whole network the simple bound would take many seconds in Python.

What it costs

The clique problem is NP-hard, and the worst case of branch and bound is exponential with any bound. But real graphs are usually far from the worst case, and the difference between bounds is orders of magnitude.

On a hundred and fifty airports the simple bound takes four seconds in Python, while the colouring needs 25 milliseconds even on two hundred. With the colouring the whole network of 3468 airports is solved in 11 milliseconds in Go, while the simple bound already takes more than a second on five hundred airports.

Easy mistakes

• A bound that underestimates. If a bound is ever less than the best solution in a branch, pruning will throw out the optimum, and the answer will be “good but not the best”, without any error message.
• A strict comparison. A branch is useless if its bound is no greater than the incumbent: “≤”, not “<”. With a strict sign the answer is right, but the tree is larger.
• A poor first incumbent. While the incumbent is small, there is nothing to cut off. A good initial solution, a greedy one, or ordering vertices by degree, shrinks the tree more than it seems.
• A bound dearer than the savings. A colouring at each node costs O(k²) comparisons; in small branches the simple bound is simpler and faster. Good solvers switch between them.
• The order of exploration. Depth-first search saves memory and finds an incumbent quickly; “best bound first” proves optimality with fewer nodes but keeps the whole queue. For huge trees that is the difference between megabytes and gigabytes.

Where it is used

Integer programming solvers are the method's main users: the bound of a branch there is the solution of the same problem without the requirement of integers, computed by the simplex method. The exact travelling salesman: a lower bound from spanning trees. The knapsack with huge weights, where a table does not fit: a greedy bound with a fractional last item. Cliques and colourings: in network analysis, chemistry, timetables.

History

Ailsa Land and Alison Doig described the method in 1960 as “an automatic method of solving discrete programming problems”, for integer problems with a linear bound. The name “branch and bound” stuck after the 1963 paper by John Little, Katta Murty, Dura Sweeney and Caroline Karel on the travelling salesman problem. In 1972 Richard Karp included the clique in the list of 21 NP-complete problems. The algorithm with a colouring bound was proposed by Etsuji Tomita and Tomokazu Seki in 2003, and its descendants are still among the fastest exact clique algorithms.

Problems

The largest group of airports pairwise connected by direct flights, with an answer that can be checked.