- Branch and bound is a systematic method for solving optimization problems
- B&B is a rather general optimization technique that applies where the greedy method and dynamic programming fail.
- However, it is much slower. Indeed, it often leads to exponential time complexities in the worst case.
- On the other hand, if applied carefully, it can lead to algorithms that run reasonably fast on average.
- The general idea of B&B is a BFS-like search for the optimal solution, but not all nodes get expanded (i.e., their children generated). Rather, a carefully selected criterion determines which node to expand and when, and another criterion tells the algorithm when an optimal solution has been found.

- Input: n jobs, n employees, and an n x n matrix A where A
_{ij}be the cost if person i performs job j. - Problem: find a one-to-one matching of the n employees to the n jobs
so that the total cost is minimized.
- formally, find a permutation f such that C(f), where
C(f)=A is minimized._{1f(1)}+ A_{2f(2)}+ ... + A_{nf(n)} - A brute-force method would generate the whole solution tree, where
every path from the root to any leaf is a solution, then evaluate the C of each solution, and finally choose the path with the minimum cost.
- Illustration on this specific instance of the job-assignment problem:
2 4 5 2 7 10 5 3 7 - In informal terms, the problem is to choose a single number from each row such that (1) no two numbers are chosen from the same columns, and
(2) the sum of the chosen numbers is minimized.
- The brute force method:
- The first idea of B&B is to develop "a predictor" of the likelihood (in a loose sense)
of a node in the solution tree that it will lead to an optimal solution. This predictor is quantitative.
- With such a predictor, the B&B works as follows:
- Which node to expand next: B&B chooses the live node with the best predictor value
- B&B simply expands that node (i.e., generate all its children)
- the predictor value of each newly generated node is computed,
the just expanded node is now designated as a
**dead node**, and the newly generated nodes are designated as live nodes. - Termination criterion: When the best node chosen for expansion turn out to be a final leaf (i.e., at level n), that when the algorithm terminates, and that node corresponds to the optimal solution. The proof of optimality will be presented later on.

- What could that predictor be?
- In the case of minimization problem, one candidate predictor of any node
is the
**cost so far**. That is, each node corresponds to (partial) solution (from the root to that node). The cost-so-far predictor is the cost of the partial solution. - Apply this preliminary algorithm on the above specific instance of
the job assignment problem
2 4 5 2 7 10 5 3 7 - A better predictor for the job assignment problem is:
(cost so far) + (sum of the minimums of the remaining rows) - Apply B&B with the new predictor to the same instance of the job assignment problem
2 4 5 2 7 10 5 3 7 - A yet another predictor is
cost so far + sum where p^{n}_{i=k+1}p_{ i}_{ i}is the minimum value in row i of the cost matrix A, such that p is not in the column of any of the terms chosen in the partial solution so far. - Apply B&B with the last predictor to the same instance of the job assignment problem
2 4 5 2 7 10 5 3 7

- Each solution is assumed to be expressible as an array X[1:n] (as was seen in Backtracking).
- A predictor, called an approximate cost function CC, is assumed to have been defined.
- Definitions:
- A
__live node__is a node that has not been expanded - A
__dead node__is a node that has been expanded - The
__expanded node__(or__E-node__for short) is the live node with the best CC value.

- A
- The general B&B algorithm follows:

Procedure B&B() begin E: nodepointer; E := new(node); -- this is the root node which -- is the dummy start node H: heap; -- A heap for all the live nodes -- H is a min-heap for minimization problems, -- and a max-heap for maximization problems. while (true) do if (E is a final leaf) then -- E is an optimal solution print out the path from E to the root; return; endif Expand(E); if (H is empty) then report that there is no solution; return; endif E := delete-top(H); endwhile end

Back to Top

Procedure Expand(E) begin - Generate all the children of E; - Compute the approximate cost value CC of each child; - Insert each child into the heap H; end

- Definition of the cost function C: For every node X in the solution tree, the cost function C(X) is the cost of the best
solution that goes through node X.
- Theorem: In the case of minimization problems, if CC(X) <= C(X) for every node X, and
if CC(X)=C(X) for every final leaf node X, then the first expanding node (best-CC node) that happens to be a final leaf corresponds to an optimal solution.
- Proof:
- Let E be the E-node that happens to be a final leaf.
- Need to prove that C(E) <= C(X) for any live node X.
- C(E)=CC(E) because E is a final leaf
- CC(E) <= CC(X) for any live node X, because E is the expanding node, that is, the minimum-CC node
- CC(X) <= C(X) by assumption.
- Therefore, C(E)=CC(E)<=CC(X) <=C(X), leading to C(E)<=C(X). Q.E.D.

- Therefore, the criteria for the approximate cost function CC for minimization problems are:
- CC(X) <= C(X) for all live nodes X
- CC(X)=C(X) for all final leaves.

- The criteria for the approximate cost function CC for maximization problems are:
- CC(X) >= C(X) for all live nodes X
- CC(X)=C(X) for all final leaves.

- Because of those criteria, CC is called an underestimate of C (in the case of minimization), and an overestimate of C (in the case of maximization)
- The closer CC is to C, the faster is the algorithm in reaching an optimal solution.

- We need to define the full record of a node
- We need to fully implement the Expand procedure
- Every node corresponds to something like X[i]=j, which signifies that the job X[i] assigned to person i is j.
- every node must store its CC value.
- each node must point to its parent so that when an optimal leaf is generated, the path from that leaf to the root can be traced and printed out as the optimal solution.
- Therefore, a node record structure should look like:
Record node Begin Parent: nodepointer; I: integer; -- person I J: integer; -- Job J is assigned to person I CC: real; End

- Take the 2nd CC formula:
CC(X at level k) = cost so far + sum where m^{n}_{i=k+1}m_{i}_{i}is the minimum of row i. - observe that if X is a pointer to a node, then
X->CC = X->Parent->CC + A _{X->I,A->J}- m_{X->I} - Write a piece of code that computes the m
_{i}s for i=1,2,...,n - Code for Expand(E):

Procedure Expand(E) begin /* Generate all the children of E; */ I := E->I; X,p: nodepointer; S[1:n]: Boolean; /* S is a bitmap set initialized to 0*/ /* S will contain all the jobs that have been assigned by the partial path from the root to E */ p := E; while (p is not the root) do S[p->J] := 1; p := p-> Parent; endwhile for job=1 to n do if S[job] = 0 then X := new(node); X->I := I + 1; X->J := job; X->Parent := E; X->CC := E->CC + A_{X->I,X->J}-m_{X->I}; Insert(X,H); endif endfor end

Exercise: The 0/1 knapsack problem is the same as the regular knapsack problem except that one cannot take a fraction of any item: either the whole item is taken, or nothing of that item is taken. Develop a B&B algorithm for the 0/1 knapsack problem.

Hint: take CC(X) to be