Advanced Algorithms · Lecture Notes
Chapter 5: Branch and Bound
In many optimization problems the number of possible solutions grows exponentially or factorially with the input. Trying every candidate one by one becomes impossible even with a few dozen items. Branch and bound shortens this search intelligently. Solutions are built step by step on a tree. For each branch, an estimate is made in advance of how good that branch can possibly be. If the estimate cannot beat the best solution found so far, the branch is never entered. These notes first present the concepts of the method, its general scheme, how the bound is chosen, and the three search strategies. They then apply the method step by step to five problems: the 0/1 knapsack, the traveling salesman, assignment, integer linear programming, and maximum clique. In each application we show why the bound is valid, explain the code line by line, and run it with a trace table. The notes end with a comparison of design paradigms.
Learning outcomes
- Paradigm
- Explain the steps of branch and bound (the state-space tree, branching, bounding, and pruning) and state how the method differs from backtracking.
- Bound design
- Build an upper bound for maximization and a lower bound for minimization; justify why a bound must be valid, that is, optimistic; obtain a bound through relaxation.
- Search strategies
- Trace the FIFO, LIFO, and least-cost (best-first) strategies on the same example and compare them in terms of the number of nodes generated and memory. Tell the design paradigms apart.
- Applications
- Solve the 0/1 knapsack, traveling salesman, assignment, integer linear programming, and maximum clique problems step by step with branch and bound.
5.1The idea of branch and bound
Solving a complex problem is sometimes like finding the right direction at a fork in the road. At each fork there are several options, and each option leads to new forks. The goal is to find the path that finally reaches the best point. Walking every path to its end gives a sure result but takes far too long. Branch and bound proposes a middle way: at each fork, we estimate where we could get to in the best case in that direction. If the estimate is worse than the best result in hand, we never go that way.
5.1.1Combinatorial optimization and the limits of brute force
The targets of branch and bound are combinatorial optimization problems. In these problems a solution is built from a finite number of discrete choices: which items to take, in what order to visit the cities, which person gets which job. The number of possible solutions is finite but very large. What we look for is the solution that maximizes or minimizes an objective function. The method aims at an exact, that is, optimal solution; it is not content with an approximate one.
The simplest solution to such problems is brute force: all candidates are generated, each is evaluated, and the best is chosen. The trouble is the growth rate of the number of candidates. In a knapsack problem with n items, each item is either taken or not; there are 2n subsets. In a traveling salesman problem with n cities, once the starting city is fixed, every ordering of the remaining cities is a separate tour; there are (n − 1)! tours. Table 5.1 shows how these two numbers grow.
| n | 2n subsets | (n − 1)! tours |
|---|---|---|
| 5 | 32 | 24 |
| 10 | 1,024 | 362,880 |
| 20 | 1,048,576 | ≈ 1.2 · 1017 |
| 40 | ≈ 1.1 · 1012 | ≈ 2.0 · 1046 |
A computer that evaluates a billion tours per second would finish all the tours of 20 cities in about 1.2 · 108 seconds, which is more than three years. For 40 cities the time required is far beyond the age of the universe. In the knapsack the growth is slower, but even with 40 items a trillion-scale number of subsets is tried. Most of these problems are NP-hard: no known algorithm can solve them in polynomial time in the worst case. Branch and bound does not change the worst case either. What it changes is the number of candidates examined in practice.
The basic idea of the method can be stated in one sentence: how good a branch can possibly be is estimated in advance, and if the estimate is not good enough, that branch is never entered. If this estimate is built correctly, the optimal solution is never lost, but most candidates are eliminated without ever being generated.
5.1.2Branching, bounding, pruning
Branch and bound is an algorithm design method that splits the solution space of an optimization problem into subproblems in the form of a tree. For each subproblem, the best value that can be reached is estimated. Subproblems whose estimate is no better than the best solution found so far are eliminated without being examined.
The name of the method comes from its two basic operations. It can be summarized in four steps:
- Branching: The problem is split into smaller subproblems. In the knapsack, the question “should item 1 be taken?” produces two subproblems: the cases in which item 1 is taken and in which it is not.
- Bounding: For each subproblem, the best value that can be reached is estimated. This estimate is called the bound.
- Pruning: Subproblems whose bound is no better than the best solution found so far are eliminated. No solution below an eliminated subproblem is generated.
- Repeat: The process continues for all the remaining subproblems. As unnecessary branches are pruned, the search gets shorter.
Figure 5.1 shows the method on a tree. We start at the root and descend by making a decision at each node. The node at the upper right has been pruned. The seven nodes below it are drawn faintly, because the algorithm never generates them. This saving grows exponentially as the depth of the tree increases. A node pruned just below the root eliminates almost half of the tree in one stroke.
The method is used in a wide range of areas. The traveling salesman, knapsack, scheduling, bin packing, and integer programming are among the first. In industry, branch and bound is also at the core of commercial optimization software that solves problems such as production planning, airline crew assignment, and logistics routing.
5.1.3Basic concepts
Branch and bound algorithms work on a tree, and the nodes of this tree can be in various states. Putting the names of the concepts down at the start makes the later traces easier to read.
The state-space tree is a tree that shows all the partial and complete solutions of a problem. The root is the state in which no decision has been made. Each level of the tree corresponds to a decision; for example, at level i the question “should item i be taken?” is answered. The leaves are the complete solutions, in which all the decisions have been made.
The state-space tree is not built in full in the program. The algorithm generates nodes as needed and forgets the nodes it has finished with. It is therefore necessary to name the states of the nodes:
- Branching and the E-node. Generating the children of a node, that is, its subproblems, is called branching. The node whose children are being generated at that moment is called the E-node (expanding node).
- Bound. An optimistic value that no solution below the node can exceed. In maximization it is an upper bound; in minimization, a lower bound.
- Live node. A node that has been generated but not yet expanded and still looks promising. All the live nodes wait in a queue-like structure. This structure can be an ordinary queue, a stack, or a priority queue.
- Dead node. A node that has been expanded, found infeasible, or pruned because its bound is insufficient. A dead node is never considered again.
- Incumbent. The value of the best complete solution found so far. Pruning decisions are made against this value. As the search proceeds,
bestonly improves: it increases in maximization and decreases in minimization.
A solution is feasible if it satisfies all the constraints of the problem. A node that violates one of the constraints is called an infeasible node. For example, a knapsack whose weight exceeds the capacity is infeasible.
best. The red dashed nodes have been pruned: one because its bound cannot beat best, the other because it is infeasible.Figure 5.2 shows these types in a single tree. The life cycle of a node is as follows. The node is generated and its bound is computed. If the bound is promising, it enters the queue as a live node; if not, it is pruned at once. When its turn comes it leaves the queue and becomes the E-node. After its children have been generated, it turns into a dead node.
5.2The paradigm
All branch and bound algorithms follow the same skeleton. Three things change from problem to problem: how a node is represented, how the children are generated, and how the bound is computed. This section first gives the skeleton and then discusses the choice of the bound, the pruning rules, and the search strategy.
5.2.1The general scheme
The code below is the branch and bound skeleton for a maximization problem. It is pseudocode close to Java: queue, bound(), isFeasible(), isComplete(), and value() take on a different meaning in each problem.
int best = -∞;
queue.add(root);
while (!queue.isEmpty()) {
Node u = queue.remove(); // strategy
if (bound(u) <= best) continue;
for (Node c : u.children()) {
if (!isFeasible(c)) continue;
if (isComplete(c) && value(c) > best)
best = value(c); // new incumbent
if (bound(c) > best)
queue.add(c); // live node
}
}
return best;The code is a single loop. Each pass of the loop has five steps:
- Select: A live node is removed from the queue. Which node comes out is decided by the search strategy: first in (FIFO), last in (LIFO), or the one with the best bound.
- Test again: The line
if (bound(u) <= best) continue;tests the node once more. The node looked promising when it entered the queue. But while it waited,bestmay have grown. If its bound is now insufficient, the node is discarded without ever being expanded. - Branch: The
forloop generates the children of the node. Infeasible children are eliminated at once bycontinue. - Update: If a child is a complete solution and its value is greater than
best,bestis raised. This solution is the new incumbent. - Bound: Only children whose bound can beat
bestare put in the queue. The others are pruned.
The loop stops when the queue is empty. At that moment best is the value of the optimal solution. The reason for this claim is simple. Every node has either been expanded or pruned. The solutions below pruned nodes cannot beat best, because the bound guarantees it. The solutions below expanded nodes have been examined one by one. So no solution better than best has been skipped.
The code is written for maximization. In minimization the directions are reversed. The bound is a lower bound, best starts at +∞, and a node with lower(c) ≥ best is pruned. The traveling salesman and assignment problems are solved in this form.
The skeleton stores only the value of the solution, not the solution itself. If we also want to know which items were taken or in what order the tour visits the cities, each node carries its own partial solution. A boolean[] array or a bit mask is enough for this. When best is updated, this information is copied as well.
5.2.2How is the bound chosen?
The whole success of branch and bound depends on the bound function. A good bound has four properties. One of them is mandatory; the other three concern efficiency.
In a maximization problem, the bound of a node u is valid if it is greater than or equal to the value of every feasible solution in the subtree of u: bound(u) ≥ value(x) for every x. In minimization the condition is reversed: lower(u) ≤ value(x). A valid bound is also called an optimistic bound, because it assumes the branch looks better than it can actually be.
- It must be valid (optimistic). This property is mandatory. If the bound falls below the true value (in maximization), the branch containing the optimum may be pruned as “not good enough.” The algorithm then returns a wrong result without raising any error.
- It must be tight. The closer the bound is to the true value, the more branches are pruned. An infinitely large “bound” is valid but prunes nothing; the algorithm degenerates into brute force.
- It must be cheap to compute. The bound is computed at every node. A very expensive bound can cost more time than the nodes it prunes.
- It is built by relaxation. The general way to obtain a bound is relaxation. One of the hard constraints of the problem is removed and the easy problem that remains is solved. When a constraint is removed, the set of feasible solutions grows. So the optimal value of the relaxed problem cannot be worse than the optimal value of the original problem; it is a valid bound.
Three examples of relaxation are treated in detail in these notes. In the knapsack, the constraint “items cannot be split” is removed and the fractional knapsack is solved. In integer programming, the constraint “the variables must be integers” is removed and an ordinary linear program is solved. In the traveling salesman problem, the constraint “the chosen edges must form a single tour” is removed and each city is left by its cheapest edge.
There is a trade-off between tightness and cheapness. In minimization, the lower bound is the smallest value that can be obtained in the best scenario. A weak lower bound prunes almost nothing and lengthens the search. A very strong lower bound requires an expensive computation at every node. The choice is made according to the balance between the number of nodes pruned and the work done per node.
Using a pessimistic value as the bound. In the knapsack, adding up the profits of just the items that fit completely seems plausible. But this value is the profit of a feasible solution, that is, a lower bound; it is not an upper bound. Let the items be (20, 2), (30, 5), (35, 7), (12, 3) and the capacity 9. At the root the items that fit completely give 20 + 30 = 50, whereas the optimum is 55 (the first and third items). The moment best is 50, this “bound” cuts the branch of the optimum and the algorithm returns 50.
5.2.3When is a node pruned?
In branch and bound algorithms a node is pruned for three reasons. All three rules answer the same question: could there be a solution better than best below this node?
- Infeasibility. If the node violates a constraint, there is no valid solution below it. Examples: the weight has exceeded the capacity, a city has been visited a second time, the linear program has no solution.
- Bound. If bound(u) ≤ best in maximization, or lower(u) ≥ best in minimization, the solutions below cannot beat the best. The node is pruned even if it is feasible.
- Completeness. If the node is a complete solution (a leaf), or if the solution of the relaxation is already feasible, there is no need to branch. For example, in integer programming, if the solution of the linear program turns out to be integral, there is no better integer solution below that node. Its value is compared with
bestand the node is closed.
Note the case of equality. A node with bound(u) = best is pruned too. Below it there is at most a solution as good as best, and a solution of that value is already in hand. If not only the value of the best solution but all the best solutions are wanted, nodes are not pruned on equality; that is a separate problem.
Backtracking uses only the first rule and completeness. What sets branch and bound apart from it is the second rule: even if the node is feasible, it is cut if it is “not good enough.” So adding a single bound line to a search written as backtracking turns it into branch and bound.
5.2.4Search strategies
In the general scheme we said “a live node is removed from the queue.” Which live node comes out depends on the type of the queue structure. There are three common strategies (Table 5.2).
| Strategy | Queue structure | How it traverses | Pros / cons |
|---|---|---|---|
| FIFO branch and bound | queue (ArrayDeque) | level by level, breadth-first | finds shallow solutions early; the number of live nodes can grow exponentially |
| LIFO branch and bound | stack (or recursion) | depth-first | memory proportional to the depth; an early complete solution raises best quickly |
| Least cost (LC, best-first) | priority queue (PriorityQueue) | the node with the most promising bound first | usually expands the fewest nodes; the queue consumes memory, and each operation costs O(log k) |
In the FIFO (first in, first out) strategy the live nodes wait in an ordinary queue. The tree is traversed level by level; this is breadth-first search. The children of the root are expanded, then the grandchildren, then their children. Solutions at shallow levels are found early. But before descending to the deep levels, all the shallow nodes accumulate in the queue. In a tree with branching factor 2, level k contains 2k nodes; if pruning is weak, the queue grows exponentially.
In the LIFO (last in, first out) strategy the live nodes wait on a stack, or the search is written directly with recursion. The tree is traversed depth-first. The stack holds only the not-yet-tried siblings of the nodes on the current path. So memory is bounded by the product of the depth and the branching factor. Another benefit is that it reaches a leaf quickly. A complete solution found early gives best a value, and pruning starts in the very first steps.
In the least cost (LC) strategy the live nodes wait in a priority queue. At each step the node with the most promising bound is expanded: in maximization the node with the largest bound, in minimization the one with the smallest. This strategy is also called best-first search. Because the most promising branch is looked at first, a good solution is found early and most of the remaining nodes are pruned. The price is the memory consumption of the priority queue and the O(log k) cost of each insertion and removal, where k is the number of nodes in the queue.
As long as the bound is valid, all three strategies find the same optimal value. The strategy changes only the amount of work, that is, the number of nodes generated and expanded, and the memory. These differences will be seen with numbers in the knapsack example.
5.2.5Least-cost search and cost estimation
In the general form of LC search, each node is assigned an estimated cost:
ĉ(x) = f(x) + ĝ(x)
Here f(x) is the cost already paid from the root to x; for example, the depth of x or the length of the path traveled so far. ĝ(x) is an estimate of the remaining cost from x to a solution. Of the live nodes, the one with the smallest ĉ is expanded.
The two extreme choices give the other strategies. If ĝ = 0, only the cost paid is considered; this is uniform-cost search. If the steps have unit cost, that is, if f is the depth of the node, the shallowest node is always chosen and the search is FIFO, that is, breadth-first. If f = 0, only the estimate of the remaining cost is considered; this is greedy best-first search, which chooses the node that looks closest to the goal. The sum of the two weighs the cost paid and the estimate of what remains together.
A good property of the estimate is that it is never greater than the true remaining cost. Such an estimate is called an admissible heuristic. This property corresponds to the valid bound in branch and bound: the remaining cost is shown as less than it is, that is, the estimate is optimistic.
The classic example is the 8-puzzle. In a 3 × 3 frame there are tiles numbered 1 to 8 and one blank. In one move, a tile adjacent to the blank slides into the blank. The goal is to bring the tiles to the arrangement 1 2 3 / 4 5 6 / 7 8, with the blank in the lower-right corner. In this problem f(x) is the number of moves made so far and ĝ(x) is the number of tiles not in place. Every misplaced tile needs at least one move. So ĝ never overestimates the number of remaining moves.
Figure 5.4 shows the first step of the search. The initial state is 1 2 3 / 4 □ 6 / 7 5 8 (□ is the blank). Only 5 and 8 are out of place; the ĉ value of the root is 0 + 2 = 2. When the root is expanded, four children arise:
- Blank up: 2 moves down; 1 □ 3 / 4 2 6 / 7 5 8. Misplaced tiles 2, 5, 8: ĉ = 1 + 3 = 4.
- Blank down: 5 moves up; 1 2 3 / 4 5 6 / 7 □ 8. Only 8 is misplaced: ĉ = 1 + 1 = 2.
- Blank left: 4 slides right; 1 2 3 / □ 4 6 / 7 5 8. Misplaced tiles 4, 5, 8: ĉ = 4.
- Blank right: 6 slides left; 1 2 3 / 4 6 □ / 7 5 8. Misplaced tiles 6, 5, 8: ĉ = 4.
The child with the smallest ĉ is “blank down,” and it is the one expanded. Of its children, “blank right” slides the 8 to the left and reaches the goal: ĉ = 2 + 0 = 2. The solution takes 2 moves and only 2 expansions were made. FIFO, by contrast, does not look at the ĉ values. It expands the nodes of the first level in the order they were generated and wastes time on a hopeless branch such as “blank up.” The A* algorithm of path finding is the counterpart of this idea on weighted graphs; the relation is discussed separately at the end of the notes.
5.2.6Comparison with backtracking
Branch and bound and backtracking traverse the same tree and their code is very similar. Both extend partial solutions and cut hopeless branches. They differ in what they look for and what they cut by (Table 5.3).
| Property | Backtracking | Branch and bound |
|---|---|---|
| Problem type | decision and search: one or all valid solutions (n-queens, Sudoku) | optimization: the best solution (largest profit, shortest tour) |
| Pruning criterion | feasibility: is a constraint violated? | feasibility + bound: can it beat best? |
| Traversal | always depth-first (recursion) | depth-first, breadth-first, or best-first |
| Extra information | only the partial solution | partial solution + bound function + best |
| Memory | O(depth) | O(depth) in the depth-first version; the size of the queue in FIFO and LC |
| Worst case | exponential | still exponential; far fewer nodes in practice |
When solving the n-queens problem, backtracking checks whether one queen attacks another. If there is an attack, it cuts the branch. All solutions or one solution are sought; there is no ordering of “better” among the solutions. Branch and bound is meaningful when there is an ordering among solutions. Even if a branch violates no constraint, it is cut if the best solution that can come out of it is worse than the one in hand.
The code counterpart of this difference is a single line. A search written for the traveling salesman or maximum clique that contains no bound test is really backtracking; it traverses the whole tree. When a single bound line such as if (lowerBound(...) < best) is added, the search turns into branch and bound.
5.2.7Advantages and disadvantages
The strengths of the method are the following:
- It finds the exact optimal solution of complex optimization problems. Unlike approximate methods, the optimality of the result is proven.
- It narrows the search space and eliminates unnecessary possibilities. With a good bound, a very small fraction of the tree is traversed.
- It is a natural framework for problems that require finding the best route or selection.
- It applies to a wide variety of problems whose solutions can be represented as a tree.
- It can be stopped early. If the search is cut off midway, a solution (
best) and the best bound in the queue are in hand. The difference between the two tells how far the solution in hand can be from the optimum at most. This information is a quality guarantee.
It has weaknesses as well:
- In the worst case the time is still exponential. In cases with a great many possibilities where the bound does not prune well, the time becomes unacceptably long.
- In the FIFO and best-first strategies, memory too can grow exponentially.
- Success depends on a good bound estimate; a weak bound prunes almost nothing.
- A bound and a branching rule specific to each problem must be designed. The implementation is more complex than backtracking.
5.3The 0/1 knapsack
To see all the parts of the method, the 0/1 knapsack problem is chosen as the first application. The problem is familiar, its state-space tree is binary, and its bound is easy to compute. The same example will be run with three different strategies and the results compared.
5.3.1The problem and its state-space tree
A brief reminder of the problem is enough. There are n items; item i has profit pi and weight wi. The capacity of the knapsack is W. A decision is made for each item: xi ∈ {0, 1}. An item is either taken whole (1) or not taken at all (0); it cannot be split. The goal is to make the decisions so that
Σ pi xi is maximal subject to Σ wi xi ≤ W
These notes do not use the dynamic programming solution of the knapsack. Dynamic programming builds a table that depends on the capacity W and takes O(nW). If W is very large or the weights are not integers, this table cannot be built; branch and bound is not affected by the size of the weights.
For branch and bound, the items are first sorted in decreasing order of profit-to-weight ratio. This order is needed for the bound computation to be valid. The state-space tree is binary. The root is the state in which no decision has been made. At level i the decision for item i is made: the left branch is “item i taken” (1), the right branch “not taken” (0). In a problem with four items the tree has five levels, and the full tree contains 25 − 1 = 31 nodes. Of these, 16 are leaves; each leaf corresponds to a subset.
The example used in these notes is given in Table 5.4. The capacity is W = 16. The items are already in decreasing order of ratio: 20, 6, 5, 2.
| Item | pi | wi | pi/wi |
|---|---|---|---|
| 1 | 40 | 2 | 20 |
| 2 | 30 | 5 | 6 |
| 3 | 50 | 10 | 5 |
| 4 | 10 | 5 | 2 |
The optimum is to take items 1 and 3: profit 40 + 50 = 90, weight 2 + 10 = 12. Brute force finds this result by trying all 16 subsets. Branch and bound reaches the same result without generating all 31 nodes. How few nodes are generated depends on the strategy used.
5.3.2Upper bound: the fractional knapsack relaxation
The knapsack is a maximization problem; an upper bound is needed for every node. This bound is built by relaxation. When the constraint “items cannot be split” is removed, the problem becomes the fractional knapsack. In the fractional knapsack, any desired fraction of an item can be taken and the same fraction of its profit is obtained. The greedy method solves this problem optimally: the items are taken whole in ratio order as long as they fit; of the first item that does not fit, the fraction that fits is taken, and the knapsack is full.
The bound of a node is computed with the same idea. At node u the decisions already made are fixed: let the profit of u be k, its weight a, and its level i. The items not yet decided, i + 1, i + 2, …, are added whole in ratio order as long as they fit. Let the first item that does not fit be m; the fraction of it that fits is added:
bound(u) = k + Σj = i+1m−1 pj + (W − a − Σj = i+1m−1 wj) · pm / wm
If all the remaining items fit, there is no m and the last term is not added. If the node itself is infeasible, that is, a > W, the bound is taken to be 0. This guarantees that the node can never beat best and will not enter the queue.
If the items are in decreasing order of pi/wi, then for every node u, bound(u) is greater than or equal to the profit of every feasible 0/1 solution in the subtree of u.
Any feasible 0/1 solution in the subtree of u keeps the decisions made at u and chooses a subset of the remaining items. This choice is also a solution of the fractional problem: the fraction of every item is 0 or 1. So the profit of the 0/1 solution cannot exceed the optimal value of the fractional problem built for the remaining items and the remaining capacity W − a. Because the items are in ratio order, the greedy method gives the optimal value of the fractional problem: every unit of remaining capacity is spent on the item that gives the highest profit per unit among the remaining items. Adding k to this value gives bound(u). ∎
The proof has two supports: every 0/1 solution is a fractional solution, and the greedy method is optimal for the fractional problem. The second support depends on the ratio order. If the items are not in ratio order, the greedy method does not find the optimum even for the fractional problem. In that case the computed value can fall below the true optimum and the bound loses its validity.
The bound of the root is computed in the example as follows. Items 1 and 2 fit completely: 40 + 30 = 70, weight 7. Item 3 has weight 10 and does not fit into the remaining 9 units. 9/10 of item 3 is taken: 9 · 50/10 = 45. So bound(root) = 70 + 45 = 115. The meaning of this number is: whichever subset of the four items is chosen, the profit cannot exceed 115. The true optimum is 90; the bound is optimistic but valid.
Forgetting to sort the items by ratio. Suppose the items are given in the order (10, 5), (40, 2), (30, 5), (50, 10) and the bound is computed in that order. At the root the first three items fit completely (weight 12, profit 80); for the remaining 4 units, 4/10 of item 4 is taken: 80 + 20 = 100. This number is smaller than 115 and does not reflect the true fractional optimum. In this example 100 is still greater than 90, but in another example the unsorted computation can fall below the optimum and the right branch is pruned.
5.3.3Code trace: bound(root)
The Java counterpart of the bound function is below. Arrays start at zero: p[0] and w[0] belong to item 1. n is the number of items and W the capacity. The class Node carries the fields level, profit, weight, and bound. The level of the root is −1; no item has been decided yet.
double bound(Node u) {
if (u.weight > W) return 0; // infeasible
double result = u.profit;
int totalW = u.weight;
int j = u.level + 1;
while (j < n && totalW + w[j] <= W) {
totalW += w[j];
result += p[j];
j++;
}
if (j < n) // fractional part
result += (W - totalW) * (double) p[j] / w[j];
return result;
}The lines do the following:
if (u.weight > W) return 0;catches an infeasible node. If the weight has exceeded the capacity, there is no feasible solution below the node; the bound of 0 keeps it out of the queue.resultstarts with the node's own profit andtotalWwith its own weight.jpoints to the first undecided item.- The
whileloop adds items whole as long as they fit. The condition has two parts: there must be an item left (j < n) and item j must fit completely into the remaining capacity. - When the loop ends, either no items are left or
jis the first item that does not fit. In the second case a fractional profit of(W - totalW) * (double) p[j] / w[j]is added. The(double)cast prevents integer division.
For one node the function looks at no more than n items; its time is O(n). It uses no extra memory. Table 5.5 is the trace of the call for the root.
| Step | Test | j | totalW | result |
|---|---|---|---|---|
| Entry | 0 ≤ 16: feasible | 0 | 0 | 0 |
| Loop 1 | 0 + w[0] = 2 ≤ 16: item 1 fits whole | 1 | 2 | 40 |
| Loop 2 | 2 + w[1] = 7 ≤ 16: item 2 fits whole | 2 | 7 | 70 |
| Loop end | 7 + w[2] = 17 > 16: item 3 does not fit | 2 | 7 | 70 |
| Fraction | j = 2 < 4: (16 − 7) · 50/10 = 45 | 2 | 7 | 115 |
Figure 5.6 shows the same computation on a bar. The green part of the bar is the items taken whole, and the hatched part is the fractional piece. The fractional piece cannot be taken in the 0/1 problem; this is why the bound is larger than the true value.
Let the items (p, w) be (20, 2), (30, 5), (35, 7), (12, 3) and W = 9. The ratios are 10, 6, 5, 4; the items are in order.
- Root. Items 1 and 2 fit whole: 20 + 30 = 50, weight 7. Item 3 does not fit (7 + 7 = 14 > 9); for the remaining 2 units, 2 · 35/7 = 10. bound(root) = 60.
- The node “item 1 skipped” (level 0, profit 0, weight 0). Item 2 fits whole: 30, weight 5. Item 3 does not fit; for the remaining 4 units, 4 · 35/7 = 20. The bound is 50.
- The node “item 1 taken, item 2 skipped” (level 1, profit 20, weight 2). Item 3 fits whole: 20 + 35 = 55, weight 9. The capacity is full; the fraction for item 4 is 0. The bound is 55.
The optimum is items 1 and 3: profit 55, weight 9. Greedy selection in ratio order takes 1 and 2 and stops at 50. After the optimum is found, the bound of the node “item 1 skipped” satisfies 50 ≤ 55 and the node is pruned: no solution without item 1 can exceed 55.
5.3.4Best-first branch and bound, step by step
Now the main example (W = 16) is solved with the best-first strategy. Each node is named with a letter and is given with its “profit / weight” pair and its bound (s). The queue is a priority queue; at each step the node with the largest bound comes out. When a child is generated, if it is feasible and its profit is greater than best, best is updated at once. In the knapsack every feasible node is a valid solution made up of the items taken; there is no need to descend to a leaf to update.
- Start. Root A: no item chosen; 0 / 0, s = 115.
best= 0. Queue: A (115). - A is removed and branched. B (item 1 taken): 40 / 2, feasible;
best= 40. The bound of B is the same as that of the root, because the bound of the root already took item 1 whole: s = 115. C (no item 1): 0 / 0. In the bound computation, items 2 and 3 fit whole: 30 + 50 = 80, weight 5 + 10 = 15. Item 4 does not fit; for the remaining 1 unit, 1 · 10/5 = 2 is added. s = 82. Queue: B (115), C (82). - B is removed and branched. D (item 2 taken): 70 / 7;
best= 70, s = 115. E (no item 2): 40 / 2; item 3 fits whole (90, weight 12), 4/5 of item 4 is added (8): s = 98. Queue: D (115), E (98), C (82). - D is removed and branched. F (item 3 taken): weight 7 + 10 = 17 > 16; infeasible, its bound is 0, pruned. G (no item 3): 70 / 7; item 4 fits whole (80, weight 12), no more items: s = 80. Because 80 > 70, G enters the queue. Queue: E (98), C (82), G (80).
- E is removed and branched. H (item 3 taken): 90 / 12, feasible;
best= 90. The bound of H is 90 + 4 · 2 = 98 and it enters the queue. I (no item 3): 40 / 2; item 4 fits whole: s = 50 ≤ 90, pruned. Queue: H (98), C (82), G (80). - H is removed and branched. J (item 4 taken): weight 17; infeasible. K (no item 4): 90 / 12, the last item; s = 90 ≤ 90, pruned. Queue: C (82), G (80).
- C and G are discarded. C is removed: 82 ≤ 90, discarded at the second test. G is removed: 80 ≤ 90, discarded. The queue is empty.
The result is best = 90, found at node H: items 1 and 3. Of the 31 nodes of the full tree, only 11 were generated: A through K. Of these, 5 were expanded: A, B, D, E, H. The queue never held more than 3 nodes.
Figure 5.7 shows the finished tree of the search. Two moments of the trace are instructive. The first is step 4. The bound of D is 115, but the “take” child of D is infeasible and the bound of the “skip” child falls to 80. The bound approaches the truth as decisions are made. The second is the last step. When C and G entered the queue they looked promising: best was 40 when C entered and 70 when G entered. When their turn came, best was 90. Without the second test both would have been expanded; the result would not have changed, but work would have been done for nothing.
Updating best only at the leaves. In the knapsack every feasible node is a solution: the chosen items go into the knapsack and the rest are not taken. In the trace above best rises to 40 in step 2, to 70 in step 3, and to 90 in step 5. If the update were held back until the leaf, best would stay at 0 for a long time and nodes like I could not be pruned.
5.3.5Java code: branchAndBound()
The Java code of best-first branch and bound is below. PriorityQueue is used as the priority queue.
int branchAndBound() {
PriorityQueue<Node> queue = new PriorityQueue<>(
(a, b) -> Double.compare(b.bound, a.bound));
Node root = new Node(-1, 0, 0);
root.bound = bound(root);
queue.add(root); int best = 0;
while (!queue.isEmpty()) {
Node u = queue.poll(); // largest bound
if (u.bound <= best || u.level == n - 1) continue;
int i = u.level + 1;
// left child: take item i
Node take = new Node(i, u.profit + p[i],
u.weight + w[i]);
if (take.weight <= W && take.profit > best)
best = take.profit;
take.bound = bound(take);
if (take.bound > best) queue.add(take);
// right child: skip item i
Node skip = new Node(i, u.profit, u.weight);
skip.bound = bound(skip);
if (skip.bound > best) queue.add(skip);
}
return best;
}The important points of the code are these:
- The comparator is reversed. By default
PriorityQueuereturns the smallest element first. The comparator(a, b) -> Double.compare(b.bound, a.bound)reverses the order, sopoll()returns the node with the largest bound. - The second test. The line
if (u.bound <= best || u.level == n - 1) continue;catches two things. The first is nodes that have gone stale while waiting in the queue (C and G in the example). The second is nodes at the last level; they have no children. The bound itself does not change in the queue; what changes isbest. - The left child. The node
takeadds item i. If the weight does not exceed the capacity and the profit is greater thanbest,bestis updated. Then its bound is computed, and if the bound exceedsbestit enters the queue. An infeasibletakenode has bound 0; it never enters the queue. - The right child. The node
skipcarries its parent's profit and weight unchanged. If the parent is feasible,skipis feasible too and its profit does not changebest. So only its bound is checked. - Changing the strategy. For FIFO, an
ArrayDequewithadd()/poll()is used; for LIFO,push()/pop(). The rest of the code is the same.
The code returns only the best value. If the chosen items are wanted as well, a boolean[] array or a bit mask is added to the class Node. Each child copies its parent's array and records its own decision. When best is updated, this array is saved too.
Cost. In the worst case all the nodes of the full tree are generated: O(2n) nodes. At each node the bound computation takes O(n) and the queue operation O(log k). The worst-case time is O(n · 2n). Memory is proportional to the number of nodes in the queue, which in the worst case is also exponential. In practice, with a good bound, the number of nodes generated stays far below this.
5.3.6FIFO branch and bound: code trace
The same example is now solved with a FIFO queue. The code uses an ArrayDeque instead of a priority queue. Children are generated by the helper method child(u, take); the method builds the child and computes its bound as well. The loop first generates the “take” child (take = 1) and then the “skip” child (take = 0).
int fifoBranchAndBound() {
ArrayDeque<Node> queue = new ArrayDeque<>();
queue.add(root); int best = 0;
while (!queue.isEmpty()) {
Node u = queue.poll(); // first in
if (u.bound <= best || u.level == n - 1) continue;
for (int take = 1; take >= 0; take--) { // take first
Node c = child(u, take); // includes bound(c)
if (c.weight <= W && c.profit > best)
best = c.profit; // new incumbent
if (c.bound > best) queue.add(c);
}
}
return best;
}In this code root has been built in advance and its bound computed. The structure of the loop is the same as in the best-first code; the only difference is that poll() returns the node that entered the queue first. Table 5.6 gives every step of the trace. The letters do not follow the order of generation; the children of C are named L and M.
| Removed | “Take” child | “Skip” child | best | Queue (front to back) |
|---|---|---|---|---|
| — | — | — | 0 | A |
| A (115) | B 40/2, 115 → queued | C 0/0, 82 → queued | 40 | B, C |
| B (115) | D 70/7, 115 → queued | E 40/2, 98 → queued | 70 | C, D, E |
| C (82) | L 30/5, 82 → queued | M 0/0, 60 ≤ 70: pruned | 70 | D, E, L |
| D (115) | F 120/17: infeasible | G 70/7, 80 → queued | 70 | E, L, G |
| E (98) | H 90/12, 98 → queued | I 40/2, 50 ≤ 90: pruned | 90 | L, G, H |
| L (82) | 82 ≤ 90: discarded at the second test | 90 | G, H | |
| G (80) | 80 ≤ 90: discarded at the second test | 90 | H | |
| H (98) | J 100/17: infeasible | K 90/12, 90 ≤ 90: pruned | 90 | empty |
The result is again 90. FIFO generated 13 nodes and expanded 6: A, B, C, D, E, H. The queue held at most 3 nodes. The source of the difference from the best-first strategy is node C. Best-first left C to the end, because C's bound (82) was smaller than that of the other nodes in the queue; by the time its turn came, best was 90 and C was never expanded. FIFO expands C third, in level order. At that moment best is only 70, and since C's bound is 82, C cannot be discarded. Expanding C generates two extra nodes (L and M) and means one extra expansion. L too ends up waiting in the queue for nothing.
5.3.7Comparing the three strategies
The same example can also be solved with the LIFO strategy. In LIFO the live nodes wait on a stack. If the children are pushed so that the “take” child comes out first, that is, the “skip” child is added first and then the “take” child, the search always descends the left branch. After A, B is expanded, then D. The “take” child of D is infeasible; the “skip” child, G (70/7, 80), is expanded. The “take” child of G adds item 4: 80/12. This is a feasible solution and best rises to 80. The search then returns to E and finds 90 at H. Finally C (82), left on the stack, is discarded. LIFO also generates 13 nodes and expands 6: A, B, D, G, E, H.
Figure 5.9 shows the three searches side by side; Table 5.7 summarizes the numbers.
| Method | Nodes generated | Expanded | Largest queue |
|---|---|---|---|
| Brute force (full tree) | 31 | 15 | — |
| FIFO branch and bound | 13 | 6 | 3 |
| LIFO branch and bound (take first) | 13 | 6 | 3 |
| Best-first (LC) | 11 | 5 | 3 |
Three conclusions follow from the table. First, all three strategies find the same optimum; the strategy affects only the amount of work. Second, best-first generated the fewest nodes in this example. This is a general tendency but not a guarantee. Third, in a small example the difference in memory is not visible: in all three the queue holds at most 3 nodes. In large examples the difference opens up. In the FIFO and best-first strategies the queue can grow exponentially; in LIFO the stack stays proportional to the depth.
The order in which the children are pushed onto the stack matters in LIFO. If the order is reversed, that is, the “skip” child comes out first, the search dives first into the branch in which item 1 is not taken. There are no good solutions in that branch; best rises slowly, first 40, then 50, 60, 80. This version generates 21 nodes and expands 10. In depth-first search, finding a good solution early speeds up the whole search. That is why the children are ordered so that the promising branch comes out first.
The items (20, 2), (30, 5), (35, 7), (12, 3) and W = 9 of Example 5.1 are solved with the best-first strategy.
- Root A: 0 / 0, s = 60. Queue: A (60).
- A is expanded. B (item 1 taken): 20 / 2, s = 60;
best= 20. C (no item 1): s = 50. Queue: B (60), C (50). - B is expanded. D (item 2 taken): 50 / 7, s = 60;
best= 50. E (no item 2): 20 / 2, s = 55. Queue: D (60), E (55), C (50). - D is expanded. F (item 3 taken): weight 14 > 9, infeasible. G (no item 3): 50 / 7; 2/3 of item 4: s = 50 + 8 = 58. Queue: G (58), E (55), C (50).
- G is expanded. H (item 4 taken): weight 10 > 9, infeasible. I (no item 4): s = 50 ≤ 50, pruned. Queue: E (55), C (50).
- E is expanded. J (item 3 taken): 55 / 9;
best= 55. The bound of J is 55; 55 ≤ 55, so it does not enter the queue. K (no item 3): s = 32 ≤ 55, pruned. Queue: C (50). - C is removed: 50 ≤ 55, discarded. The queue is empty.
The result is 55 (items 1 and 3). 11 nodes were generated and 5 were expanded. When C was added, best was 20; when it was removed, it was 55. In step 6 the value of J is written to best but J does not enter the queue. The bound of J equals its value; there is no better solution below it.
5.4The traveling salesman problem
The traveling salesman problem (TSP) is a minimization problem. As a brief reminder: n cities are given, together with the distance between every pair of cities. We look for the shortest tour that visits every city exactly once and returns to the start. The distances are kept in a matrix d; d[i][j] is the cost of going from i to j. If d[i][j] = d[j][i], the problem is symmetric. The problem is NP-hard and brute force tries (n − 1)! tours. In this section the same four-city example is examined with three different lower bounds.
5.4.1State space and the cheapest-outgoing-edge bound
The tour always starts at city 0. Each node of the state-space tree is a partial path starting at 0. The root contains only 0. The children of a node are obtained by going from the last city of the path to a city not yet visited. Nodes at depth n − 1 contain all the cities; when we return from the last city to 0, the tour is complete.
Because the problem is a minimization, each node needs a lower bound: no tour that completes that partial path can cost less than this value. The simplest lower bound rests on the following observation. To complete the tour, we must leave the current last city and each unvisited city exactly once. Each departure costs at least the cheapest edge of that city. Let the cost of the cheapest outgoing edge of city v be cheapest[v]. These values are computed once before the search begins. The lower bound is:
lower(path) = cost(path) + cheapest[last city] + Σv unvisited cheapest[v]
This bound is a relaxation. In the original problem the outgoing edges must form a single tour. In the relaxation this condition is removed: each city leaves by its own cheapest edge, and whether the edges form a tour is not examined. Because of the removed constraint, the value of the relaxation cannot exceed the cost of any tour.
For every partial path starting at 0, the cost of every tour that completes the path is greater than or equal to lower(path).
Any tour that completes the path contains the edges of the path unchanged; their sum is cost(path). In the rest of the tour, the last city is left once and every unvisited city is left once; there is no other departure. The edge leaving city v costs at least cheapest[v]. Adding these inequalities, the cost of the tour is at least lower(path). ∎
The symmetric four-city matrix used in these notes is given in Table 5.8. The last column is the minimum of each row, that is, the array cheapest.
| 0 | 1 | 2 | 3 | cheapest | |
|---|---|---|---|---|---|
| 0 | — | 3 | 2 | 15 | 2 |
| 1 | 3 | — | 21 | 5 | 3 |
| 2 | 2 | 21 | — | 8 | 2 |
| 3 | 15 | 5 | 8 | — | 5 |
At the root the path is just 0 and its cost is 0. The last city is 0, and 1, 2, 3 are unvisited. The lower bound is 0 + 2 + 3 + 2 + 5 = 12. The four thick edges in Figure 5.10 do not form a tour: the edge 0-2 has been chosen twice and city 3 is never entered. This is why the value of the relaxation is smaller than a real tour.
The bound for the path 0 → 1 is as follows. The cost of the path is d[0][1] = 3. We will leave the last city, 1: cheapest[1] = 3. The unvisited cities are 2 and 3: 2 + 5. The total is 3 + 3 + 7 = 13. The bound is larger than that of the root; as decisions are made, the bound approaches the truth.
5.4.2Code trace: tsp(0, 0, 1)
Branch and bound for the traveling salesman is written as a bounded depth-first search. It is a LIFO branch and bound; recursion plays the role of the stack.
void tsp(int city, int cost, int count) {
if (count == n) { // tour complete
int tour = cost + d[city][0];
if (tour < best) best = tour;
return;
}
for (int c = 0; c < n; c++) {
if (visited[c]) continue;
int next = cost + d[city][c];
visited[c] = true;
if (lowerBound(c, next) < best) // bound
tsp(c, next, count + 1);
visited[c] = false; // unchoose
}
}The parameters of the method are the last city of the path (city), the cost of the path (cost), and the number of cities on the path (count). The visited array marks the cities on the path; best is initially infinite. Before the first call, visited[0] = true is set and tsp(0, 0, 1) is called. The lines do the following:
if (count == n)is the base case. All the cities are on the path; we return from the last city to 0 and the tour is complete. If the tour is shorter thanbest,bestis updated.- The
forloop is the branching. Each unvisited citycis a child. Visited cities are skipped bycontinue; this is the infeasibility rule. visited[c] = true;adds the city to the path. The bound is computed after this marking, so thatlowerBoundsees citycas “visited” and counts it only as the last city.if (lowerBound(c, next) < best)is the bound rule. If the lower bound is less thanbest, the branch is entered; otherwise it is pruned.visited[c] = false;is the undo. The path returns to its old state before the loop moves on to the next city.
Table 5.9 gives all the steps of the search in order.
| Step | Edge | next | lower | best | Decision |
|---|---|---|---|---|---|
| 1 | 0 → 1 | 0 + 3 = 3 | 3 + 3 + 2 + 5 = 13 | ∞ | branch |
| 2 | 1 → 2 | 3 + 21 = 24 | 24 + 2 + 5 = 31 | ∞ | branch |
| 3 | 2 → 3 | 24 + 8 = 32 | 32 + 5 = 37 | ∞ | branch |
| 4 | tour 0 → 1 → 2 → 3 → 0 = 32 + 15 = 47 | 47 | first candidate | ||
| 5 | 1 → 3 | 3 + 5 = 8 | 8 + 5 + 2 = 15 | 47 | branch |
| 6 | 3 → 2 | 8 + 8 = 16 | 16 + 2 = 18 | 47 | branch |
| 7 | tour 0 → 1 → 3 → 2 → 0 = 16 + 2 = 18 | 18 | new best | ||
| 8 | 0 → 2 | 0 + 2 = 2 | 2 + 2 + 3 + 5 = 12 | 18 | branch |
| 9 | 2 → 1 | 2 + 21 = 23 | 23 + 3 + 5 = 31 | 18 | pruned |
| 10 | 2 → 3 | 2 + 8 = 10 | 10 + 5 + 3 = 18 | 18 | pruned |
| 11 | 0 → 3 | 0 + 15 = 15 | 15 + 5 + 3 + 2 = 25 | 18 | pruned |
A few points in the trace stand out. The first tour (47) is bad, but it gives best a finite value. Right after it, 18 is found. In step 8 the bound of the branch 0 → 2 is 12; because 12 < 18, the branch is entered. Two children of this branch are pruned. In step 10 the bound equals best: 18 ≥ 18. The best tour in this branch can be at most 18, and a tour of 18 has already been found. In step 11 the last child of the root, 0 → 3, is pruned directly, and the two tours below it are never tried.
tsp search. The value a under each node is the lower bound. The red dashed nodes are pruned. The green node completes the shortest tour (18).The result is the shortest tour 0 → 1 → 3 → 2 → 0, of length 3 + 5 + 8 + 2 = 18. The full state-space tree has 1 + 3 + 6 + 6 = 16 nodes. Branch and bound generated 10 nodes, counting the root, and called the method tsp 7 times. A search without pruning generates all 16 nodes and calls the method 16 times.
The code does not store the best tour itself. To store it, an int[] path array is kept. In the loop, path[count] = c is written before entering the branch. In the base case, if the tour is shorter than best, it is copied with bestPath = path.clone(). The copy is necessary, because the path array keeps changing during the rest of the search.
5.4.3Code trace: lowerBound(3, 8)
The bound function is short:
int lowerBound(int last, int cost) {
int lower = cost + cheapest[last];
for (int v = 0; v < n; v++)
if (!visited[v]) // not yet visited
lower += cheapest[v];
return lower;
}lower first adds the cost of the path and the cheapest departure from the last city. The loop goes through all the cities and adds the cheapest value of every unvisited city. A visited city is of two kinds. Either it is inside the path and its outgoing edge is already included in the cost, or it is the last city and its departure was added at the start. In neither case should it be added again. The function takes O(n).
The call in step 5 of the tsp trace is lowerBound(3, 8). The path is 0 → 1 → 3, its cost is 3 + 5 = 8, and visited = {0, 1, 3}.
| Step | Explanation | lower |
|---|---|---|
| Start | 8 + cheapest[3] = 8 + 5: the last city, 3, will be left once more | 13 |
| v = 0 | visited; its outgoing edge (0 → 1) is in the cost | 13 |
| v = 1 | visited; its outgoing edge (1 → 3) is in the cost | 13 |
| v = 2 | not visited; it must be left by at least cheapest[2] = 2 | 15 |
| v = 3 | visited; its departure was added at the start | 15 |
lowerBound(3, 8). The red edges are the path 0 → 1 → 3 (cost 8). The table on the right shows the cheapest value of each city and whether it is visited; only city 2 contributes to the bound.The function returns 15. Every tour in this branch costs at least 15. The real tour is 0 → 1 → 3 → 2 → 0 and costs 18. During the search best is 47, so 15 < 47 holds and the branch is entered.
What is the lower bound of the path 0 → 3 → 1 in the same matrix? The cost of the path is 15 + 5 = 20. The last city is 1: cheapest[1] = 3. The only unvisited city is 2: cheapest[2] = 2. The bound is 20 + 3 + 2 = 25. Because 25 ≥ 18, this path is pruned once the optimum has been found. The search never reaches this node anyway, because it already pruned 0 → 3 (bound 25) at the root.
5.4.4A tighter bound: the two shortest edges
The cheapest-outgoing-edge bound counts only one edge per city. But in a tour each city is entered by one edge and left by one edge. In a symmetric problem there is no distinction between entering and leaving: every city touches exactly two edges of the tour. The sum of these two edges of a city cannot be smaller than the sum of the two shortest edges touching it. If this observation is summed over all the cities, each tour edge is counted twice: once at one end and once at the other. This gives a tighter lower bound:
tour ≥ ½ · Σv (the sum of the two shortest edges touching v)
In a symmetric traveling salesman problem, the cost of every tour cannot be smaller than half of the sum, over all cities, of the two shortest edges touching each city.
Let T be a tour. Every city v touches exactly two edges of T; if the sum of these two edges is called t(v), then Σv t(v) = 2 · cost(T), because each edge is counted once at each of its ends. Let the sum of the two shortest edges touching v be e(v). Both edges of T touching v are edges touching v; their sum cannot be smaller than e(v): t(v) ≥ e(v). Summing gives 2 · cost(T) ≥ Σv e(v). ∎
The code that computes this bound at the root is:
double twoEdgeBound() {
int total = 0;
for (int v = 0; v < n; v++) {
int m1 = INF, m2 = INF; // two smallest
for (int u = 0; u < n; u++) {
if (u == v) continue;
if (d[v][u] < m1) { m2 = m1; m1 = d[v][u]; }
else if (d[v][u] < m2) m2 = d[v][u];
}
total += m1 + m2;
}
return total / 2.0; // each edge twice
}The outer loop goes through the cities. The inner loop finds, among the edges touching the city, the two smallest values, with m1 ≤ m2. If a new edge is smaller than m1, the old m1 moves to second place and the new edge becomes first. If it is smaller only than m2, it is written to second place. This is the update of a two-element “smallest values list.” Because the total counts every edge twice, the result is divided by 2.0; double division keeps the half if the total is odd. The time is O(n2).
| v | Edges | m1 | m2 | total |
|---|---|---|---|---|
| 0 | 3, 2, 15 | 2 | 3 | 5 |
| 1 | 3, 21, 5 | 3 | 5 | 13 |
| 2 | 2, 21, 8 | 2 | 8 | 23 |
| 3 | 15, 5, 8 | 5 | 8 | 36 |
The row v = 0 shows how the inner loop works. At the start m1 = m2 = ∞. At u = 1, 3 < ∞: m1 becomes 3 and the old m1 (∞) moves to m2. At u = 2, 2 < 3: m2 = 3 and m1 = 2. At u = 3, 15 is larger than both; there is no change. 2 + 3 = 5 is added to the total. In the end the total is 36 and the function returns 36 / 2 = 18.
The result is striking: the bound is 18, equal to the length of the shortest tour. As Figure 5.13 shows, the two edges chosen by each city together form a real tour. The solution of the relaxation has turned out to be feasible; that is why the bound is tight. Since at the root the bound equals the optimum, as soon as the first complete tour is found all the remaining branches are pruned by the condition lower ≥ best. On partial paths the same idea is applied by fixing the edges on the path. One or both of the edges of a city on the path are already known. The shortest edges are sought only for those that are missing.
5.4.5The reduced cost matrix
A third lower bound looks at the rows and columns of the cost matrix. The idea is this. Every tour uses exactly one cell from each row of the matrix (a departure from a city) and exactly one cell from each column (an arrival at a city). If the same number is subtracted from all the cells of a row, the cost of every tour decreases by exactly that number. The ordering of the tours does not change. The sum of the numbers subtracted from the rows and columns has been taken off the cost of every tour. Because the remaining matrix is nonnegative, this sum is a lower bound.
The procedure is as follows. The diagonal is set to ∞; one cannot go from a city to itself. From each row the minimum of that row is subtracted. Then from each column the minimum of that column is subtracted. In the end every row and every column contains at least one 0. This matrix is called the reduced cost matrix.
int reduce(int[][] m) {
int total = 0;
for (int i = 0; i < n; i++) { // rows
int mn = rowMin(m, i);
if (mn > 0 && mn < INF) {
subtractRow(m, i, mn); total += mn;
}
}
for (int j = 0; j < n; j++) { // columns
int mn = colMin(m, j);
if (mn > 0 && mn < INF) {
subtractCol(m, j, mn); total += mn;
}
}
return total;
}rowMin, subtractRow, colMin, and subtractCol are simple helper methods. The subtraction is applied only to cells that are not ∞. The condition mn > 0 skips subtracting zero. The condition mn < INF skips rows and columns that are entirely ∞; such rows arise during branching. The method modifies the matrix in place and returns the total subtracted. Both passes take O(n2).
| Step | Minimum | Result | total |
|---|---|---|---|
| Row 0: ∞, 3, 2, 15 | 2 | ∞, 1, 0, 13 | 2 |
| Row 1: 3, ∞, 21, 5 | 3 | 0, ∞, 18, 2 | 5 |
| Row 2: 2, 21, ∞, 8 | 2 | 0, 19, ∞, 6 | 7 |
| Row 3: 15, 5, 8, ∞ | 5 | 10, 0, 3, ∞ | 12 |
| Columns 0, 1, 2 | 0 | no change | 12 |
| Column 3: 13, 2, 6, ∞ | 2 | 11, 0, 4, ∞ | 14 |
When the row reduction is finished, the total is 12. This number is the same as the cheapest-outgoing-edge bound; the row minima are exactly the cheapest values. The column step adds new information. After the row reduction there is no 0 in column 3: not every city's cheapest departure goes to 3. Yet in a tour city 3 must be entered, and this entry costs at least 2. The column step brings the constraint “every city is entered once” into the bound as well and raises the bound to 14. Table 5.13 is the final form of the reduced matrix.
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | ∞ | 1 | 0 | 11 |
| 1 | 0 | ∞ | 18 | 0 |
| 2 | 0 | 19 | ∞ | 4 |
| 3 | 10 | 0 | 3 | ∞ |
With this method, branching is done by choosing an edge. Let the edge i → j be chosen in the reduced matrix of the parent node. The matrix of the child is built as follows. All the cells of row i and column j are set to ∞: there can be no other departure from i and no other arrival at j. The cell (j, i) is also set to ∞; going straight back from j to i would close a cycle too early. The matrix is reduced again. The bound of the child is computed as:
bound(child) = bound(parent) + reduced c[i][j] + the total of the new reduction
The bound of the root is 14. Three branches open from the root:
- 0 → 1. Reduced c[0][1] = 1. Row 0, column 1, and (1, 0) are set to ∞. The remaining rows: row 1 = ∞, ·, 18, 0 (minimum 0); row 2 = 0, ·, ∞, 4 (0); row 3 = 10, ·, 3, ∞ (3). 3 is subtracted from row 3: 7, ·, 0, ∞. Every column has a 0. The new reduction is 3. The bound is 14 + 1 + 3 = 18.
- 0 → 2. Reduced c[0][2] = 0. Row 0, column 2, and (2, 0) are set to ∞. Row 2 = ∞, 19, ·, 4; its minimum is 4 and it is subtracted. The other rows and columns have a 0. The bound is 14 + 0 + 4 = 18.
- 0 → 3. Reduced c[0][3] = 11. Row 0, column 3, and (3, 0) are set to ∞. Every row keeps a 0. Column 2 = 18, ∞, 3 (excluding row 0); its minimum is 3. The bound is 14 + 11 + 3 = 28.
The bound of the 0 → 3 branch is 28. As soon as the optimum 18 is found, this branch is pruned. The bounds of the 0 → 1 and 0 → 2 branches are exactly 18, and both contain the shortest tour: 0 → 1 → 3 → 2 → 0 and its reverse 0 → 2 → 3 → 1 → 0.
The reduced matrix method rests on the paper published by Little and colleagues in 1963. The method has an important advantage: it does not require symmetry. It is valid for asymmetric problems with d[i][j] ≠ d[j][i] as well. One-way streets, or vehicles that burn different amounts of fuel uphill and downhill, are examples of asymmetric problems. The two-shortest-edges bound, by contrast, depends on symmetry and cannot be used directly in an asymmetric problem.
5.4.6Comparing the three bounds
In the same four-city example the three lower bounds give three different values at the root (Figure 5.14).
| Bound | Cost per node | What it uses | Note |
|---|---|---|---|
| Cheapest outgoing edge | O(n) (cheapest[] is computed in advance) | one departure from each city | cheapest, loosest |
| Reduced matrix | O(n2) | one arrival + one departure for each city | valid for asymmetric problems too |
| Two shortest edges | O(n2) | the two edges touching each city | for the symmetric problem |
A tight bound prunes more but is more expensive at each node. The cheapest-outgoing-edge bound is computed in O(n) thanks to the cheapest array. The other two look at the whole matrix at every node. The ranking does not have to be the same in every example. The reduced matrix bound and the two-shortest-edges bound use different information, and in another example their order can change. The cheapest-outgoing-edge bound, on the other hand, cannot be larger than either of them. The row step of the reduction alone gives it. In the two-edge bound, too, the average of a city's two edges is not smaller than its cheapest edge.
For larger examples, even tighter bounds are used. The 1-tree bound leaves one city out, builds a minimum spanning tree for the rest, and connects the outside city by its two shortest edges. Every tour is a 1-tree; so the smallest 1-tree is a valid lower bound. The linear programming relaxation is the basis of the software that today solves examples with thousands of cities exactly. Which bound to choose is decided by the balance between the number of nodes pruned and the work done per node.
5.4.7A larger example: 6 cities
In the four-city example the effect of pruning is limited; the full tree is small anyway. To see the effect, a symmetric six-city example is taken (Table 5.15).
| 0 | 1 | 2 | 3 | 4 | 5 | cheapest | |
|---|---|---|---|---|---|---|---|
| 0 | — | 29 | 20 | 21 | 16 | 31 | 16 |
| 1 | 29 | — | 15 | 29 | 28 | 40 | 15 |
| 2 | 20 | 15 | — | 15 | 14 | 25 | 14 |
| 3 | 21 | 29 | 15 | — | 12 | 18 | 12 |
| 4 | 16 | 28 | 14 | 12 | — | 22 | 12 |
| 5 | 31 | 40 | 25 | 18 | 22 | — | 18 |
The cheapest-outgoing-edge bound of the root is 16 + 15 + 14 + 12 + 12 + 18 = 87. The shortest tour is 0 → 1 → 2 → 3 → 5 → 4 → 0: 29 + 15 + 15 + 18 + 22 + 16 = 115. There are other tours of the same length; the search keeps the first one it finds. The gap between the root bound and the optimum is large (87 against 115); the cheapest-outgoing-edge bound is loose in this example.
| Version | Nodes generated | tsp calls |
|---|---|---|
| Without pruning (backtracking) | 326 | 326 |
| Cheapest-outgoing-edge bound | 210 | 130 |
The search without pruning generates all the nodes of the state-space tree: 1 + 5 + 20 + 60 + 120 + 120 = 326. The 120 nodes at the last level are the (6 − 1)! = 120 tours. The bounded search generates 210 nodes; that is, lowerBound is computed 210 times (counting the root). Only in 130 of them is the branch entered and tsp called. The number of calls falls from 326 to 130, about two fifths. A tighter bound reduces these numbers markedly. For example, the two-shortest-edges bound gives 100.5 at the root for this matrix; that is much closer than 87.
5.5The assignment problem
The assignment problem is suitable for showing the minimization direction of branch and bound on a small, easy-to-follow example. The code structure is very similar to the traveling salesman search; the bound is even simpler.
5.5.1The problem and a lower bound
The assignment problem: given n people and n jobs, c[i][j] is the cost of person i doing job j. Each person is given a different job so that the total cost is minimized.
Each assignment is a permutation of the jobs; there are n! possible assignments. At level i of the state-space tree, person i is given a job that nobody has yet been given. The root is the state in which no person has a job; the leaves are complete assignments.
The lower bound rests on the following observation: every person who has not yet been given a job pays at least the smallest cost in their own row. This is a relaxation. The constraint “a single person per job” is removed; two people may choose the same cheap job. Because job clashes are ignored, the bound cannot rise above the true cost. To compute the bound quickly at every node, the suffix sums of the row minima are kept in advance:
remainingMin[i] = Σr ≥ i minj c[r][j], remainingMin[n] = 0
After person i has been given a job, if the cost of the path is next, the lower bound of that node is next + remainingMin[i + 1]. The computation takes O(1). If lower ≥ best, the branch is cut.
| person \ job | 0 | 1 | 2 | minimum |
|---|---|---|---|---|
| 0 | 5 | 8 | 4 | 4 |
| 1 | 7 | 3 | 6 | 3 |
| 2 | 2 | 9 | 5 | 2 |
In the example the row minima are 4, 3, 2. The suffix sums are remainingMin = [9, 5, 2, 0]. The lower bound of the root is 9: whichever assignment is made, the total cannot fall below 9.
The assignment problem also has a polynomial-time algorithm: the Hungarian method solves the problem in O(n3) time. So branch and bound is not needed for the pure assignment problem; it is used here to demonstrate the method. For variants with extra constraints the situation changes. For example, if some jobs cannot be given to the same person, or to two people who are tied to each other, the Hungarian method cannot be applied directly. For such problems branch and bound is truly needed. In branching, the result of the Hungarian method can also be used as a lower bound.
5.5.2Code trace: assign(0, 0)
void assign(int i, int cost) {
if (i == n) { // complete assignment
best = Math.min(best, cost);
return;
}
for (int j = 0; j < n; j++) {
if (used[j]) continue;
int next = cost + c[i][j];
if (next + remainingMin[i + 1] >= best)
continue; // bound
used[j] = true;
assign(i + 1, next);
used[j] = false; // unchoose
}
}The structure of the method is the same as that of the tsp method. i is the next person and cost is the total of the assignments made so far. The used array marks the jobs already given; this is the infeasibility rule. The bound test is made before a job is added to the partial assignment. If the branch is cut, used never changes, so no undo is needed. In the base case best is updated with Math.min.
| Step | Assignment | next | lower | best | Decision |
|---|---|---|---|---|---|
| 1 | p0 → job 0 | 5 | 5 + 5 = 10 | ∞ | branch |
| 2 | p1 → job 1 (job 0 taken) | 8 | 8 + 2 = 10 | ∞ | branch |
| 3 | p2 → job 2 (the only free job) | 13 | 13 | 13 | complete assignment |
| 4 | p1 → job 2 | 11 | 11 + 2 = 13 | 13 | cut |
| 5 | p0 → job 1 | 8 | 8 + 5 = 13 | 13 | cut |
| 6 | p0 → job 2 | 4 | 4 + 5 = 9 | 13 | branch |
| 7 | p1 → job 0 | 11 | 11 + 2 = 13 | 13 | cut |
| 8 | p1 → job 1 | 7 | 7 + 2 = 9 | 13 | branch |
| 9 | p2 → job 0 | 9 | 9 | 9 | complete assignment |
The essence of the trace is this. The first complete assignment (jobs 0, 1, 2) costs 13 and becomes best. Then three branches are cut because their bound equals 13. The cut in step 5 is significant: below the branch p0 → job 1 there are two complete assignments and neither is tried. In step 6 the branch p0 → job 2 is opened with bound 9. In this branch the assignments p1 → job 1 and p2 → job 0 give 4 + 3 + 2 = 9. The result equals the lower bound of the root; from this equality it is immediately clear that no better assignment can exist.
The search made 7 calls in all: assign(0, 0), together with four intermediate nodes and two complete assignments. A search without pruning goes through all 3! = 6 assignments; that takes 1 + 3 + 6 + 6 = 16 calls. In a four-person example the difference is larger. In the matrix in Table 5.19 the row minima are 3, 2, 3, 2 and the lower bound of the root is 10.
| person \ job | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 7 | 3 | 8 | 4 |
| 1 | 5 | 6 | 2 | 9 |
| 2 | 4 | 8 | 5 | 3 |
| 3 | 6 | 2 | 7 | 5 |
The best assignment is p0 → job 3 (4), p1 → job 2 (2), p2 → job 0 (4), p3 → job 1 (2), with a total of 12. Branch and bound reaches only 4 complete assignments in 21 calls. A search without pruning tries all 4! = 24 complete assignments and makes 65 calls.
5.6Integer linear programming
The most widespread industrial use of branch and bound is integer linear programming. The method was put forward in this field in the 1960 paper of Land and Doig. Today the commercial software that solves production planning, scheduling, and distribution problems uses advanced versions of the same idea.
5.6.1The problem and the LP relaxation
Integer linear programming (ILP) is the problem of maximizing or minimizing a linear objective function subject to linear inequality constraints. All the variables are required to be integers.
Without the integrality condition the problem would be an ordinary linear program (LP). Linear programs are solved very fast in practice by the simplex method, and in polynomial time by interior-point methods. In small examples with two variables the solution can be found graphically: the constraints define a polygon in the plane (the feasible region), and the best value is attained at one of the corners of this polygon. The integrality condition is what makes the problem NP-hard.
Branch and bound combines these two facts:
- Bound: The integrality condition is removed and the LP relaxation is solved. The feasible region of the relaxation contains all the integer points. So in maximization the LP optimum is an upper bound for the ILP optimum.
- Branching: If a variable in the LP solution is fractional, for example y = 1.5, two subproblems are built: the constraint y ≤ 1 is added to one and y ≥ 2 to the other. The fractional region in between, 1 < y < 2, is thrown away. Since there are no integer points in this region, no integer solution is lost.
- Completeness: If the LP solution of a node is already integral, there is no better integer solution below that node. This solution becomes a candidate and the node is closed.
The example problem is:
maximize Z = 5x + 4y; 6x + 4y ≤ 24, x + 2y ≤ 6, x, y ≥ 0 integers
The optimum of the LP relaxation is at the intersection of the two constraint lines. 6x + 4y = 24 and x + 2y = 6 are solved together. Multiplying the second equation by 2 and subtracting it from the first gives 4x = 12, that is, x = 3; from this y = 1.5. The value is Z = 15 + 6 = 21. The other corners are (0, 0), (4, 0), and (0, 3); their values are 0, 20, and 12. Figure 5.16 shows the region and the two optima.
5.6.2Branching with LP relaxations
The branch and bound tree is built step by step as follows:
- Root. The LP optimum is (3, 1.5), Z = 21. This value is an upper bound: no integer solution can exceed 21. y is fractional; we branch on y.
- Branch y ≤ 1. In the new LP we press against the limit y = 1. From 6x + 4 ≤ 24 comes x ≤ 3.33, and from x + 2 ≤ 6 comes x ≤ 4. The LP optimum is (3.33, 1), Z = 20.67. x is fractional; the branches x ≤ 3 and x ≥ 4 are opened.
- Branch y ≤ 1, x ≤ 3. The LP optimum is (3, 1), Z = 19. The solution is integral: the first candidate,
best= 19. - Branch y ≤ 1, x ≥ 4. The constraint 6 · 4 + 4y ≤ 24 forces y = 0. The LP optimum is (4, 0), Z = 20. It is integral and 20 > 19:
best= 20. - Branch y ≥ 2. The constraint x + 2y ≤ 6 forces x ≤ 2. The LP optimum is (2, 2), Z = 18. Because 18 ≤ 20, the branch is pruned. Even if the LP solution of this branch were integral, it could not beat
best.
The optimum is x = 4, y = 0, Z = 20. This example also shows why rounding the LP solution is not enough. If (3, 1.5) is rounded down, (3, 1) is obtained and Z = 19; it is not the best. If it is rounded up, (3, 2) is obtained: 6 · 3 + 4 · 2 = 26 > 24, which is infeasible. The true optimum (4, 0) is not near the LP point; it is found only by branching.
Branching wrongly on a fractional variable. For y = 2.6 the correct subproblems are y ≤ 2 and y ≥ 3. Branching as y = 2 and y = 3 loses all the other values of y. Branching as y ≤ 2.6 and y ≥ 2.6 leaves the existing LP solution in both subproblems and the search makes no progress. y ≤ 3 and y ≥ 2, in turn, give two overlapping subproblems; the same points are searched twice.
A second example shows the completeness rule: maximize Z = 3x + 2y; x + y ≤ 4, x ≤ 3, y ≤ 2. Brute force tries all 12 points of the grid 0 ≤ x ≤ 3, 0 ≤ y ≤ 2 and finds Z = 11 at the point (3, 1). The optimum of the LP relaxation is also (3, 1): the corner resting on the limit of x (3) and the line x + y ≤ 4. Because the solution is already integral, branch and bound ends at the root; a single LP has been solved.
Real software improves this basic scheme in several directions. The fractional variable to branch on is chosen intelligently. Extra constraints (cutting planes), which cut off the fractional solution without cutting off integer points, are added to the LP relaxation. This combination is called branch and cut. In addition, the LP of a subproblem is re-solved in a few steps starting from the solution of its parent.
5.7Maximum clique
The last application is a graph problem. The clique problem is used to find tightly connected groups in social networks, clusters of interacting proteins in biology, and error-correcting codes in coding theory.
5.7.1The problem and the bound
In an undirected graph, a set of vertices in which every two vertices are adjacent is called a clique. The maximum clique problem is the problem of finding the clique with the most vertices.
The problem is NP-hard. The search grows the current clique K step by step. The vertices that can be added to K are called candidates. For a vertex to be a candidate, it must be adjacent to all the vertices in K. To prevent the same clique from being generated again and again in different orders, vertices are added in increasing order of number: only vertices with a number greater than the last vertex added to K can be candidates.
The bound is a maximization bound and is very simple. In the best case K grows with all the candidates. So the largest clique that can be found in this branch cannot exceed |K| + |candidates| vertices. If |K| + |candidates| ≤ |best|, the current clique cannot beat best however far it is extended; the branch is pruned. The bound is valid, because every clique in the branch is the union of K and a subset of the candidates.
void clique(List<Integer> K, int start) {
if (K.size() > best.size())
best = new ArrayList<>(K);
List<Integer> cands = new ArrayList<>();
for (int v = start; v < n; v++)
if (compatible(v, K)) cands.add(v); // adjacent to K
if (K.size() + cands.size() <= best.size())
return; // bound
for (int v : cands) {
K.add(v);
clique(K, v + 1);
K.remove(K.size() - 1); // unchoose
}
}The lines of the method work as follows:
- The first two lines update
best. A clique is a feasible solution at every moment; there is no need to descend to a leaf.new ArrayList<>(K)makes a copy, becauseKchanges during the rest of the search. - The
forloop collects the candidates.compatible(v, K)checks whether v is adjacent to every vertex inK. The loop starts atstart; smaller numbers have already been tried. if (K.size() + cands.size() <= best.size()) return;is the bound rule.- The last loop is the branching. Each candidate is added to
Kin turn, the search continues fromv + 1, and the candidate is removed again.
In one call the candidate list is built in O(n · |K|) time; if adjacency is kept in a matrix, each compatible check is O(|K|). Without the bound line, the method is ordinary backtracking and traverses all the cliques.
5.7.2Code trace: clique({}, 0)
The search starts with the empty clique and start = 0. Table 5.20 gives the calls in order.
| Call | K | Candidates | |K| + |cands| | best | Decision |
|---|---|---|---|---|---|
| 1 | {} | {0, 1, 2, 3, 4, 5} | 0 + 6 | {} | continue |
| 2 | {0} | {1, 2, 3, 4} | 1 + 4 | {0} | continue |
| 3 | {0, 1} | {2, 3, 4} | 2 + 3 | {0, 1} | continue |
| 4 | {0, 1, 2} | {3, 4} | 3 + 2 | {0, 1, 2} | continue |
| 5 | {0, 1, 2, 3} | {4} | 4 + 1 | {0, 1, 2, 3} | continue |
| 6 | {0, 1, 2, 3, 4} | {} | 5 + 0 | {0, 1, 2, 3, 4} | no candidates |
| 7 | {0, 1, 2, 4} | {} | 4 + 0 ≤ 5 | 5 vertices | pruned |
| 8 | {0, 1, 3} | {4} | 3 + 1 ≤ 5 | 5 vertices | pruned |
| 9 | {0, 1, 4} | {} | 3 + 0 ≤ 5 | 5 vertices | pruned |
| 10–12 | {0, 2}, {0, 3}, {0, 4} | {3, 4}, {4}, {} | 2 + 2, 2 + 1, 2 + 0 | 5 vertices | pruned |
| 13–17 | {1}, {2}, {3}, {4}, {5} | {2, 3, 4}, {3, 4}, {4, 5}, {5}, {} | 4, 3, 3, 2, 1 | 5 vertices | pruned |
The first five calls dive deep, always adding the first candidate, and in call 6 reach the clique with five vertices. This is the largest clique of the graph. The bound of every branch opened afterward is at most 5, and all of them are pruned at once. For example, in call 8 K = {0, 1, 3}; the only candidate is 4. In the best case a clique of four vertices is obtained, and this cannot exceed 5. The remaining candidates 1–5 at the root are also tried one by one, and all are cut in the same way. For example, when K = {3}, the candidates are 4 and 5. 3, 4, 5 form a triangle, but the bound is 1 + 2 = 3 ≤ 5.
The result is {0, 1, 2, 3, 4}. The bounded search makes 17 calls. When the bound line is deleted, the search traverses all the cliques and makes 36 calls. This number is the number of cliques in the graph, counting the empty set: 25 = 32 cliques in the complete five-vertex part, plus four cliques containing vertex 5: {5}, {3, 5}, {4, 5}, {3, 4, 5}.
5.7.3A tighter bound: coloring
The bound |K| + |cands| assumes that every candidate can enter the clique. If there are non-adjacent pairs among the candidates, this assumption is very optimistic. A tighter bound comes from graph coloring. Every pair of vertices of a clique is adjacent; so all the vertices in a clique must receive different colors. If the candidates can be properly colored with k colors, at most k of the candidates can enter the same clique. The new bound is: if |K| + colors(cands) ≤ |best|, the branch is pruned.
Finding the minimum number of colors is also NP-hard. But the best coloring is not needed. Greedy coloring goes through the vertices in order and gives each vertex the smallest color not used among its neighbors. It takes O(cands2). It may use extra colors; this only loosens the bound, it does not invalidate it. The bound still cannot exceed |cands|, because in the worst case each vertex gets its own color.
In the example in Figure 5.20 the candidates form a ring of five vertices; K is empty and |best| = 3. The old bound gives 0 + 5 = 5 > 3 and the branch is opened. Greedy coloring gives vertex 0 color 1, vertex 1 color 2, vertex 2 color 1, and vertex 3 color 2. Vertex 4 is adjacent to both 3 and 0; it takes color 3. The color bound gives 0 + 3 ≤ 3 and the branch is pruned. The largest clique in the ring has only 2 vertices anyway. Most of the fastest exact clique algorithms rest on this idea. Tomita's MCQ and MCS algorithms try the candidates in color order and prune with the color bound.
5.8Other problems and the relation to A*
5.8.1Other problems solved by branch and bound
The method can be applied to almost any optimization problem whose solution is built from a sequence of decisions. The two questions to ask in each application are the same: how is the branching done, and which relaxation gives a valid bound?
- Hamiltonian path. We look for a path that visits every vertex exactly once. The weighted version is very similar to the traveling salesman and is solved with similar bounds.
- Boolean satisfiability (SAT). Truth values are assigned to the variables; partial assignments that contradict are pruned. This is the essence of the DPLL algorithm. In the maximum SAT version we want as many clauses as possible to be true; the bound is the largest number of clauses that can still be satisfied by the remaining assignments.
- Scheduling. Jobs are distributed among machines; the maximum load (makespan) or the total tardiness is minimized. The lower bound is the load the remaining jobs would create in the best case; for example, splitting the total of the remaining jobs equally among the machines.
- Bin packing. Items are placed into the smallest number of bins. The lower bound is ⌈Σ size / bin capacity⌉: even if the bins were filled perfectly, this many bins would be needed.
- Maximum coverage. k sets are chosen that cover the most elements. The upper bound is the number of elements the largest remaining sets can add.
- The assignment problem and its variants with extra constraints. The lower bound is the smallest cost of each unassigned row.
Branch and bound is meaningful for NP-hard problems. For problems with a known polynomial-time algorithm, such as maximum flow, shortest path, or minimum spanning tree, there is no need for branch and bound. For these problems the polynomial algorithm is always preferred; branch and bound takes exponential time in the worst case.
5.8.2Branch and bound, A*, and depth-first branch and bound
Best-first branch and bound and the A* algorithm of path finding are two faces of the same idea. Table 5.21 compares three closely related methods.
| Property | Best-first branch and bound (LC) | A* | Depth-first branch and bound |
|---|---|---|---|
| Selection | best bound (ĉ) | smallest f = g + h | stack or recursion |
| Bound / estimate | valid (optimistic) bound | admissible h (never overestimates) | valid bound + best |
| Goal | optimization (the best leaf) | the shortest path from start to goal | optimization |
| Memory | live nodes: can be exponential | open list: can be exponential | O(depth) |
| First complete solution | usually late but good | the first goal found is optimal | early; a solution is in hand at every moment |
A* is LC branch and bound looking for a path in a weighted graph. g(x) is the cost paid from the start to x; it corresponds to f(x) in LC search. h(x) is a lower bound on the remaining cost from x to the goal; it corresponds to ĝ(x). The number of misplaced tiles in the 8-puzzle is such an estimate. If h is admissible, the first goal node removed from the queue gives the shortest path. The reason is the same as in branch and bound. The cost of that goal is less than or equal to the f value of every node in the queue. And the f values are lower bounds for every path through those nodes.
Depth-first branch and bound is the method for cases where memory is limited. Memory is bounded by the depth, and at every moment of the search a solution is in hand. Its price is that when a bad branch is entered, the good solution is found late. There is also a middle way. IDA* (iterative deepening A*) runs a depth-first search with a threshold on f. It cuts nodes that exceed the threshold, and if the search fails, it raises the threshold and starts again. Memory stays bounded by the depth, and the order of best-first search is largely preserved.
5.9Comparing the design paradigms
Branch and bound is among the last of the algorithm design paradigms to be treated, and it combines some of the ideas of the others. Table 5.22 puts six paradigms side by side by the same criteria.
| Paradigm | Decision | Subproblems / traversal | When? | Example |
|---|---|---|---|---|
| Brute force | all candidates are generated, then tested | the full search space | if the space is very small | 88 queen placements |
| Divide and conquer | fixed splitting rule; divide, solve, combine | independent; top-down | if the subproblems do not overlap | merge sort, Strassen |
| Greedy | the option that looks best at the moment is chosen; no turning back | a single subproblem after the choice | if the greedy-choice property is proven | Dijkstra, Huffman, Kruskal |
| Dynamic programming | all options are tried and the best is stored | overlapping; mostly bottom-up | optimal substructure, a polynomial number of subproblems | Fibonacci, 0/1 knapsack, longest common subsequence |
| Backtracking | the partial solution is extended; undone if invalid | depth-first on the state-space tree | constraint satisfaction, all solutions | n-queens, Sudoku |
| Branch and bound | backtracking + pruning by a bound | depth-first, breadth-first, or best-first | NP-hard optimization, an exact result | 0/1 knapsack, traveling salesman |
When choosing a paradigm for a problem, the questions are asked in a certain order. Are the subproblems independent? Then divide and conquer is suitable. Do the subproblems overlap, and is their number polynomial? Dynamic programming is suitable. Does the locally best choice lead to the global best, and can this be proved? The greedy approach is suitable. If none of these holds and the problem is NP-hard, two options remain. If an exact result is wanted, backtracking or branch and bound is used. If an approximate result of guaranteed quality in polynomial time is enough, an approximation algorithm is used.
The same problem can be solved with more than one paradigm. The 0/1 knapsack is a good example. Dynamic programming solves it in O(nW); if the capacity is small, it is the best choice. If the capacity is very large or the weights are fractional, branch and bound comes to the fore. The greedy method, on the other hand, does not guarantee the optimum in the 0/1 version; it is correct only in the fractional version. Branch and bound takes this greedy method inside itself as a bound computation. The paradigms are not rivals of one another; they are often used as parts inside one another.
5.10Common mistakes
- Using an invalid (pessimistic) bound. In the knapsack, adding up the profits of just the items that fit completely is not an upper bound; it is the value of a feasible solution. The branch containing the optimum can be pruned, and the algorithm returns a wrong result without raising any error.
- Mixing up the direction. In maximization a node is pruned when bound ≤ best, in minimization when lower ≥ best. Writing the reverse either misses the optimum or never prunes. Remember also that
bestmust start at +∞ in minimization and at −∞ or 0 in maximization. - Not testing again after leaving the queue. The node looked promising when it was added. If
bestgrew while it waited, it is now unnecessary. In the knapsack example C and G are such nodes. Without the second test the result does not change, but unnecessary nodes are expanded. - Not sorting the items. The fractional bound may not be a valid upper bound if the items are not in decreasing order of the ratio pi/wi.
- Updating
bestonly at the leaves. In the knapsack and in clique, every feasible node is a solution. Updating early raisesbestquickly and brings more pruning. - Taking branch and bound to be the same as backtracking. Code with no bound test, for example an unpruned TSP search, is not branch and bound; it traverses the whole tree.
- Forgetting to undo. In recursive versions, if the line
visited[c] = false,used[j] = false, orK.remove(...)is forgotten, later branches run with a wrong state and feasible solutions are lost. - Storing
bestwithout copying. In the clique search, writingbest = Kstores the list that keeps changing. When the search ends,bestshows an empty list. A copy (new ArrayList<>(K),path.clone()) is essential.
5.11Summary
- Branch and bound traverses the solution space of an optimization problem as a state-space tree. The loop is: a live node is selected, its bound is tested again, the node is branched, the bounds of the children are computed, and the hopeless ones are pruned.
bestholds the value of the best complete solution found so far. - The bound must be valid (optimistic), tight, and cheap. Validity is mandatory; tightness and cheapness determine efficiency. The bound is mostly built by relaxation. An upper bound is used in maximization and a lower bound in minimization.
- A node is pruned for three reasons: infeasibility, an insufficient bound (bound ≤ best or lower ≥ best), and completeness (a leaf, or an LP solution that turns out integral). The bound rule is what separates branch and bound from backtracking.
- FIFO traverses breadth-first and uses a queue. LIFO traverses depth-first, uses a stack or recursion, and needs little memory. LC (best-first) selects the most promising node with a priority queue and usually generates the fewest nodes. All three find the same optimum.
- In the knapsack the fractional knapsack relaxation gives the upper bound. In the example bound(root) = 115 and the optimum is 90. Best-first generates 11 of the 31 nodes, FIFO and LIFO 13.
- In the traveling salesman problem, the cheapest-outgoing-edge bound adds to the cost of the path the cheapest departures of the last city and of the unvisited cities. With four cities 10 nodes are generated instead of 16. The reduced matrix (14) and the two shortest edges (18) are tighter but take O(n2) per node.
- In assignment the lower bound is the sum of the row minima of the remaining people. In integer programming the LP relaxation gives the upper bound, and a fractional variable is branched into two subproblems. In clique the bound |K| + |cands| ≤ |best| is used; coloring gives a tighter bound.
- The method is exponential in the worst case. Its practical success depends on the quality of the bound. It is not used for problems that have a polynomial algorithm.
- Independent subproblems lead to divide and conquer, overlapping subproblems to dynamic programming, and a proven greedy choice to the greedy approach. For an exact result on an NP-hard problem, backtracking or branch and bound is used.
5.12Key terms
- branch and bound
- branching
- bound
- pruning
- state-space tree
- feasible
- relaxation
- upper bound
- best-first search
- least-cost (LC) search
- depth-first branch and bound
- admissible heuristic
- A* search
- backtracking
- 0/1 knapsack
- fractional knapsack
- traveling salesman problem
- reduced cost matrix
- assignment problem
- Hungarian method
- integer linear programming
- LP relaxation
- maximum clique
- graph coloring
- NP-hard
5.13Test Yourself
Let the items (p, w) be (30, 3), (40, 5), (45, 9), (10, 4) and W = 12. What is the fractional upper bound of the root? Which nodes does best-first branch and bound expand, how many nodes does it generate, and what is the optimum?
Answer
The ratios are 10, 8, 5, 2.5; the items are in order. At the root items 1 and 2 fit whole (70, weight 8); 4/9 of item 3 is taken: 4 · 45/9 = 20. bound(root) = 90. The root is expanded: B (item 1 taken) 30/3, bound 90,
best= 30; C (no item 1) bound 40 + 7 · 5 = 75. B is expanded: D 70/8, bound 90,best= 70; E 30/3, bound 75. D is expanded: the “take” child 115/17 is infeasible; G (no item 3) 70/8, bound 70 + 10 = 80. G is expanded: H (item 4 taken) 80/12,best= 80; the bound of H is 80 and it does not enter the queue. I (no item 4) has bound 70 and is pruned. E (75) and C (75) in the queue are discarded. 4 expansions (A, B, D, G), 9 nodes. The optimum is 80: items 1, 2, and 4.If the same example is solved with a FIFO queue, how many nodes are generated and how many are expanded? Where does the difference come from?
Answer
FIFO generates 13 nodes and expands 6: A, B, C, D, E, and G. The result is again 80. FIFO expands C (bound 75) early, in level order; at that moment
bestis only 70 and C cannot be discarded. E is also expanded; its child 75/12 is not infeasible and raisesbestto 75. Best-first leaves C and E to the end; by thenbestis 80 and both are discarded.Let the symmetric distances be d(0,1) = 10, d(0,2) = 15, d(0,3) = 20, d(1,2) = 35, d(1,3) = 25, d(2,3) = 30. What are the cheapest-outgoing-edge, reduced matrix, and two-shortest-edges bounds at the root? How long is the shortest tour?
Answer
The cheapest departures are 10, 10, 15, 20: the bound is 55. In the reduction the row minima are 10 + 10 + 15 + 20 = 55. After the row reduction, the minimum in column 2 is 5 and in column 3 is 10: the bound is 55 + 5 + 10 = 70. The sums of the two shortest edges are 25, 35, 45, 45: 150 / 2 = 75. The shortest tour is 0 → 1 → 3 → 2 → 0: 10 + 25 + 30 + 15 = 80. The order is again cheapest outgoing edge ≤ reduced matrix ≤ two edges ≤ optimum. With the cheapest-outgoing-edge bound, the
tspsearch generates 15 of the 16 nodes in this example; the loose bound prunes almost nothing.For the assignment problem with cost matrix [[4, 7, 3], [2, 6, 1], [3, 9, 4]], what is
remainingMin? What is the optimal assignment, and how many calls doesassign(0, 0)make?Answer
The row minima are 3, 1, 3: remainingMin = [7, 4, 3, 0]; the lower bound of the root is 7. The search finds complete assignments of cost 14, 13, and 11 in turn. The optimum is p0 → job 1 (7), p1 → job 2 (1), p2 → job 0 (3), with a total of 11. The search makes 12 calls; a search without pruning makes 16. In this example the first branch (p0 → job 0) is bad, so pruning starts late.
Maximize Z = 3x + 5y; x + 2y ≤ 7, 3x + y ≤ 9, x, y ≥ 0 integers. How does the tree take shape when branch and bound is applied with LP relaxations (branching first on y, then on x if it is fractional)?
Answer
Root: the intersection of the two lines (2.2, 2.4), Z = 18.6; y is fractional. Branch y ≤ 2: (2.33, 2), Z = 17; x is fractional. Below it, x ≤ 2: (2, 2), Z = 16, integral,
best= 16. x ≥ 3: (3, 0), Z = 9 ≤ 16, pruned. Branch y ≥ 3: (1, 3), Z = 18, integral,best= 18. The optimum is x = 1, y = 3, Z = 18. Rounding the LP solution down would have given (2, 2) and 16.What is the largest clique in the graph with edges 0–1, 0–2, 0–3, 1–2, 1–3, 2–3, 3–4, 3–5, 4–5? How many calls does the method
cliquemake with and without the bound?Answer
The largest clique is {0, 1, 2, 3} (4 vertices). The bounded search makes 13 calls and the unbounded search 22. The number of unbounded calls is the number of cliques, counting the empty set: the 16 subsets of {0, 1, 2, 3} plus {4}, {5}, {3, 4}, {3, 5}, {4, 5}, {3, 4, 5}. In the bounded search, after {0, 1, 2, 3} has been found, for example the branch K = {3}, cands = {4, 5} is cut by 1 + 2 ≤ 4.
If, in the knapsack bound, the profits of all the remaining items are added instead of the fractional piece, is the bound valid? What does it give at the root in the W = 16 example?
Answer
It is valid: no 0/1 solution can earn more than taking all the remaining items. But because it ignores the capacity entirely, it is very loose. At the root it gives 40 + 30 + 50 + 10 = 130; the fractional bound is 115. A looser bound prunes less; the result stays correct but more nodes are generated.
In the best-first knapsack code, if the comparator is mistakenly written as
Double.compare(a.bound, b.bound), does the result stay correct? What changes?Answer
The result stays correct. As long as the pruning rule and the bound are valid, the optimum is not lost whatever the order of traversal. What changes is the order: at each step the node with the smallest bound comes out of the queue. The search busies itself with the most hopeless branches and
bestrises late. So more nodes are expanded; the strategy is no longer “best first” but “worst first.”
5.14Further reading
- E. Horowitz, S. Sahni, S. Rajasekaran, Computer Algorithms (2nd ed., 2008), chapter 8: treats LC search and the cost function ĉ = f + ĝ in detail. The knapsack and traveling salesman applications of FIFO and LC branch and bound are given in language close to that of these notes.
- A. Levitin, Introduction to the Design and Analysis of Algorithms (3rd ed., 2012), section 12.2: presents branch and bound for assignment, knapsack, and traveling salesman with short, visual examples; it is suitable to read together with backtracking.
- J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel, “An Algorithm for the Traveling Salesman Problem” (1963): the paper that first used the name “branch and bound” and introduced the reduced cost matrix method.
- R. Carraghan, P. M. Pardalos, “An Exact Algorithm for the Maximum Clique Problem” (1990): the classic clique algorithm based on the |K| + |cands| bound; the starting point of the later algorithms with a color bound.
5.15References
- R. Carraghan, P. M. Pardalos, “An Exact Algorithm for the Maximum Clique Problem”, Operations Research Letters 9(6), 1990.
- E. Horowitz, S. Sahni, S. Rajasekaran, Computer Algorithms, 2nd ed., Silicon Press, 2008 (chapter 8: Branch-and-Bound).
- A. H. Land, A. G. Doig, “An Automatic Method of Solving Discrete Programming Problems”, Econometrica 28(3), 1960.
- A. Levitin, Introduction to the Design and Analysis of Algorithms, 3rd ed., Pearson, 2012 (section 12.2).
- J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel, “An Algorithm for the Traveling Salesman Problem”, Operations Research 11(6), 1963.
- R. Neapolitan, Foundations of Algorithms, 5th ed., Jones & Bartlett, 2015 (chapter 6).
Related pages: Chapter 5 slides · Slides PDF · © Sercan Külcü. All rights reserved.