Branch-and-Bound
or
Best-First Search

Overview

Attempt to achieve greedy performance when greedy substructure may not exist.

Recall that backtracking central idea is to cut off a branch of the problem's state-space as soon as we can deduce it cannot lead to a solution.

Combine backtracking with locally optimal choice in hopes of finding a good enough solution in a reasonable amount of time.

Often faster than brute force but not always an optimal solution when more than one solution exists.

The idea can be strengthened to deal with optimization problems that minimize or maximize an objective function, usually subject to some constraints: tour length, value of items selected, cost of an assignment, etc.

Feasible solution - a point in the problem's search space that satisfies all the problem's constraints (e.g. a Hamiltonian circuit, visiting all graph vertices once, in the traveling salesman problem where the shortest path visiting all vertices once is sought).

Optimal solution - a feasible solution with the best value of the objective function (e.g. the shortest Hamiltonian circuit in the traveling salesman problem).

Backtracking requires:

1. substructure requires a criteria to determine promising subproblems to explore
   • criteria is: consistent with previous subproblems and does not violate problem constraints

Branch-and-bound requires two additional items:

2. The value of the best solution seen so far.
3. A way to provide, for every node in the search-space tree, a bound on the best value of the objective function (lower bound for minimization, upper bound for maximization) on any solution that can be obtained by adding further components to the partial solution represented by the node.

Main idea of branch-and-bound

We can then compare a node's bound value with the best solution so far: if the bound value is not better than the best so far (less for minimization, greater for maximization) the node is non-promising and can be terminated because no solution obtained from that node can be better than the best so far.

A search path is terminated for any of the following reasons:

1. The value of the node's bound is not better than the best so far.
2. The node represents no feasible solutions because the constraints are violated.
3. The subset of feasible solutions represented by the node consists of a single point (i.e. no further choices can be made). In this case, if the objective function value is better than the best solution so far, it becomes the new best solution.

Example: Assignment Problem

Assigning n people to n jobs so that the total cost is minimized. Each person does one job and each job is assigned to one person.

4 jobs, 4 people.

Read the assignments as <Job 1, Job 2, Job 3, Job 4>:

<c,b,a,d> assigns Person c Job 1, Person b Job 2, etc.

<a,b,c,d> cost=9+4+1+4=18 <a,b,d,c> cost=9+4+9+8=30 <a,d,b,c> cost=9+6+4+8=27 <d,a,b,c> cost=7+2+3+8=20 <d,c,b,a> cost=7+8+3+8=26 etc. totaling 4! permutations

Permutations: Generate n! permutations. The following prints all the costs of the n! job assignments.

All permutations algorithm - this is a simple algorithm just to generate all n! permutations

Assumes: person ¬ a + 1 Þ person = b

Initially, X[a..d] is unassigned any Job.

Permutations( X[a..d], person )       if person = d then print cost(X)           -- Bottom of space       else              for Job Î {1, 2, 3, 4 } do                 if not assigned(X, Job)                     X[person+1] ¬ Job               -- Assign person a job                     Permutations( X[a..d], person+1 )                     X[person+1] ¬ Æ                  -- Unassign job cost( X ) returns cost of assigning Job 1..4 to person a..d assigned( X, Job ) returns true if Job is assigned person a..d

The resulting state-space for assigning Jobs {1, 2, 3, 4} to each person {a, b, c, d} is:

From the table above, the rightmost branch <d,c,b,a>, cost=7^d1 + 8^c2 + 3^b3 + 8^a4=26

Question 6

1. The algorithm generates all n! costs. In what order are the costs generated, DFS or BFS?
2. What stops the recursion (base case)?
3. What is the purpose of Line 7?
4. What is the complexity of the algorithm? 

Permutations( X[a..d], person )       if person = d then print cost(X)           -- Bottom of space       else              for Job Î {1, 2, 3, 4 } do                 if not assigned(X, Job)                     X[person+1] ¬ Job               -- Assign person a job                     Permutations( X[a..d], person+1 )                     X[person+1] ¬ Æ                  -- Unassign job cost( X ) returns cost of assigning Job 1..4 to person a..d assigned( X, Job ) returns true if Job is assigned person a..d

 

Minimum Cost

Objective function: Assignment cost e.g. (Person a, Job 1) +  (Person b, Job 2) + ... +  (Person d, Job 4)

Minimum-Cost: Generate n! permutations, evaluating the objective function (i.e. the cost) of each and keeping track of the minimum.

All permutations algorithm

Assumes: person ¬ a + 1 Þ person = b

Initially, X[a..d] is not assigned any Job.

int Minimum-Cost( X[a..d], person )       min ¬ ¥       if person = d then return cost(X)           -- cost at bottom       else              for Job Î {1, 2, 3, 4 } do                 if not assigned(X, Job)                     X[person+1] ¬ Job                     tempmin ¬ Minimum-Cost( X[a..d], person+1 )                     if tempmin < min then min ¬ tempmin                     X[person+1] ¬ Æ              return min cost( X ) returns cost of assigning Job 1..4 to person a..d assigned( X, Job ) returns true if Job is assigned person a..d

Question 7

1. What is the minimum found?
2. Does the algorithm generate all n! costs or stop when the best is found?
3. Can you suggest a way to reduce the number of costs generated? 

 

Best-first: A best-first search reduces the number of possible solutions considered by always selecting the best available.

This implies that we have some initial cost that can be compared with new calculated costs to determine the best of the new ones.

We could simply pick initial job assignments randomly, assigning Job 1 to a, 2 to b, etc. giving a cost of [9+4+1+4]=18.

Ideally, we would like to use the best feasible cost as the initial cost but that is the problem we're trying to solve.

By starting with an estimated cost near the optimum the best-first algorithm will be more efficient, reducing the number of nodes in the search tree explored.

Our initial assignments are not legal, we'll have some jobs not assigned to anyone, but will be lowest cost bound possible.

1. All persons must be assigned a Job.
2. A person always gets the Job they do the cheapest.
3. Ensures we start with an initial cost £ optimum cost

person a b c d Job 2 3 3 4 cost 2 3 1 4

Initial cost: [2+3+1+4]=10 the initial lowest bound.

We can now generate legal job assignments for person a by replacing the initial (illegal but lowest cost) assignments with legal ones as below.

Read all but the initial assignments as [Job 1, Job 2, Job 3, Job 4]. a1, give person a Job 1, cost 9 for total cost = 17. a2, give person a Job 2, cost 2 for total cost = 9. a3, give person a Job 3, cost 7 for total cost = 16. a4, give person a Job 4, cost 8 for total cost = 14.

We can see that the best total cost=9 is assigning Job 2 to person a; that assignment a2 is the best and should be explored first.

For person b, we generate all assignments except to Job 2 since that has already been assigned, a2.

The best total cost=11 is assigning Job 3 to b.

On exploring node 6 to node 8 (assigning Job 1 to c cost=14) and 9 (assigning Job 4 to c cost=15), we discover that assigning Job 4 to b (cost=12) now is best.

    You'll notice we also eventually try assigning Job 1 to b (cost=13).

The optimal assignment is [6+2+1+4]=13 for nodes <2,5,13,15>. The optimal path through the search-space tree is shown in blue.

The improvement of branch-and-bound is by searching minimum partial solutions first, terminating the search when a solution found.

Best-first algorithm - Generic version (Java version for Assignment problem)

Node Best-First( Node root-state )   -- pre: root-state is lowest bounds   -- post: returns NIL if no solution otherwise best-first solution   Q ¬ Æ   state ¬ root-state                                        while true     if goal(state) return state        -- assignment goal is all people are assigned jobs     Q ¬ Q + successors(state)       -- adds immediate successors of state     if Q = Æ return NIL     state = EXTRACT-MIN( Q )       -- removes from Q and returns minimum cost state

The algorithm is greedy, always choosing the best (minimum) cost of those on the priority queue.

Question - Execute the generic algorithm starting at the root state. Show the Q and state contents.

person a b c d Job 2 3 3 4 cost 2 3 1 4

Initial cost: [2+3+1+4]=10 That will be our lowest bound.

Node Best-First( Node root-state )   Q ¬ Æ   state ¬ root-state   while true     if goal(state) return state     Q ¬ Q + successors(state)     if Q = Æ return NIL     state = EXTRACT-MIN( Q )

successors(state) returns a list of states that can legally follow state.

We assume Jobs are assigned in the order of person a, b, c, d.

If person a = 2 Job, then the only legal successors are b=1, b=3, or b=4.

successors( a2 ) returns b1, b3, b4 as successors.

Actually returned is the cost for the successor assignments. With person a = 2 Job at cost 2:

b1 is [6+2+1+4]=13

b3 is [2+2+3+4]=11

b4 is [2+2+1+7]=12

Below shows Q and state at Line 8.

Node Best-First( Node root-state )   Q ¬ Æ   state ¬ root-state   while true     if goal(state) return state     Q ¬ Q + successors(state)     if Q = Æ return NIL     state = EXTRACT-MIN( Q )

Question 8

Why not use an arbitrary initial lower bounds of <0+0+0+0> = cost 0?

Is this still a n! time problem?

 

Example: Traveling Salesman Problem

The problem can be restated as finding the shortest Hamilton cycle (visits all vertices once) in a undirected weighted graph.

The first step is to determine a reasonable lower bound.

Lower bound

We will first estimate a lower bound and then modify edge weights with actual values as the search space is explored.

We could choose the smallest distance between any vertices and multiply by |V| (e.g. 1*5 for graph below) but that is likely to be too low and fail to eliminate some branches of the state-space.

A better lower bound can be calculated by taking the average of the two smallest weights for each vertex:

	(a,c)+(a,b)+	(b,a)+(b,c)+	(c,a)+(c,e)+	(d,e)+(d,c)+	(e,c)+(e,d)
lower bound = é[	(1  +  3) +	(3  +  6) +	(1  +  2) +	(3  +  4) +	(2  +  3)	]/2ù = 14

Our bounding function will be to compute the sum s of the two smallest weights for each vertex that includes edges in the possible cycle. For example, edge (a, d) must be included as weights of (a, d) and (d, a) as:

	(a,c)+(a,d)+	(b,a)+(b,c)+	(c,a)+(c,e)+	(d,e)+(d,a)+	(e,c)+(e,d)
lower bound = é[	(1  +  5) +	(3  +  6) +	(1  +  2) +	(3  +  5) +	(2  +  3)	]/2ù = 16

To reduce the state-space generated:

• We'll start at a and after visiting n-1 nodes, visit the remaining unvisited node and return to a.
   
• Also, because the graph is undirected, we will generate only tours in which b is visited before c (we're simply enforcing an arbitrary partial ordering of vertices to visit, makes the search-space smaller in this instance); that's why Node 2 below is not expanded further.

successors is assumed to return only successor states that are less than l, the current shortest length.

Node Best-First( Node root-state )   Q ¬ root-state   l ¬ ¥   while  Q != Æ     state = EXTRACT-MIN( Q )        Q ¬ Q + successors(state, l)     if goal(state) and length(state) < l then l ¬ length(state)    return l

Due to always exploring the lowest bounds available, the state-space tree is explored in node order: 0, 1, 5, 8, 6, 10, 11, 7, 3, 4

Generating a few of the states in the search space.

0	a (a,c)+(a,b)+ (b,a)+(b,c)+ (c,a)+(c,e)+ (d,e)+(d,c)+ (e,c)+(e,d)   lower bound = é[   (1  +  3) +   (3  +  6) +   (1  +  2) +   (3  +  4) +   (2  +  3) ]/2ù = 14
1	a,b (a,c)+(a,b)+ (b,a)+(b,c)+ (c,a)+(c,e)+ (d,e)+(d,c)+ (e,c)+(e,d)   lower bound = é[   (1  +  3) +   (3  +  6) +   (1  +  2) +   (3  +  4) +   (2  +  3) ]/2ù = 14
5	a,b,c (a,c)+(a,b)+ (b,a)+(b,c)+ (c,a)+(c,b)+ (d,e)+(d,c)+ (e,c)+(e,d)   lower bound = é[   (1  +  3) +   (3  +  6) +   (1  +  6) +   (3  +  4) +   (2  +  3) ]/2ù = 16
	a,b,c,d (a,c)+(a,b)+ (b,a)+(b,c)+ (c,a)+(c,d)+ (d,e)+(d,c)+ (e,c)+(e,d)   lower bound = é[   (1  +  3) +   (3  +  6) +   (1  +  4) +   (3  +  4) +   (2  +  3) ]/2ù = 15
	a,b,c,d,e (a,c)+(a,b)+ (b,a)+(b,c)+ (c,a)+(c,d)+ (d,e)+(d,c)+ (e,c)+(e,d)   lower bound = é[   (1  +  3) +   (3  +  6) +   (1  +  4) +   (3  +  4) +   (2  +  3) ]/2ù = 15
8	a,b,c,d,e,a (a,c)+(a,e)+ (b,a)+(b,c)+ (c,a)+(c,d)+ (d,e)+(d,c)+ (e,c)+(e,a)   lower bound = é[   (1  +  8) +   (3  +  6) +   (1  +  4) +   (3  +  4) +   (2  +  8) ]/2ù = 20
6	a,b,d (a,c)+(a,b)+ (b,a)+(b,d)+ (c,a)+(c,d)+ (d,e)+(d,b)+ (e,c)+(e,d)   lower bound = é[   (1  +  3) +   (3  +  7) +   (1  +  4) +   (3  +  7) +   (2  +  3) ]/2ù = 16
7	a,b,e (a,c)+(a,b)+ (b,a)+(b,e)+ (c,a)+(c,e)+ (d,e)+(d,c)+ (e,c)+(e,b)   lower bound = é[   (1  +  3) +   (3  +  9) +   (1  +  2) +   (3  +  4) +   (2  +  9) ]/2ù = 19
3	a,d (a,c)+(a,d)+ (b,a)+(b,c)+ (c,a)+(c,e)+ (d,e)+(d,a)+ (e,c)+(e,d)   lower bound = é[   (1  +  5) +   (3  +  6) +   (1  +  2) +   (3  +  5) +   (2  +  3) ]/2ù = 16
4	a,e (a,c)+(a,e)+ (b,a)+(b,c)+ (c,a)+(c,e)+ (d,e)+(d,c)+ (e,c)+(e,a)   lower bound = é[   (1  +  8) +   (3  +  6) +   (1  +  2) +   (3  +  4) +   (2  +  8) ]/2ù = 19

8 should be lower bound = 24 by the author but I get 20.

Conclusion

• Best-first can reduce the search space examined by always choosing the best choice first, eliminating less optimum solutions.