Branch and Bound
Branch and Bound
Branch and Bound
Terminology
Definition 1 Live node is a node that has been generated but whose children have not yet been generated.
Definition 2 E-node is a live node whose children are currently being explored. In other words, an E-node is a node currently
being expanded.
Definition 3 Dead node is a generated node that is not to be expanded or explored any further. All children of a dead node
have already been expanded.
Definition 4 Branch-and-bound refers to all state space search methods in which all children of an E-node are generated
before any other live node can become the E-node.
– In BFS, exploration of a new node cannot begin until the node currently being explored is fully explored
General method
• Just like backtracking, we will use bounding functions to avoid generating subtrees that do not contain an answer node
• Example: 4-queens
– Selection rule does not give preference to nodes that will lead to answer quickly but just queues those behind the
current live nodes
∗ In 4-queen problem, if three queens have been placed on the board, it is obvious that the answer may be reached
in one more move
∗ The rigid selection rule requires that other live nodes be expanded and then, the current node be tested
– Rank the live nodes by using a heuristic ĉ(·)
Branch and Bound 2
where h(x) is the cost of reaching x from root and f (·) is any nondecreasing function
∗ The effort spent in reaching the live node cannot be reduced and all we are concerned with at this point is to
minimize the effort reaching the solution from the live node
· This is faulty logic
· Using f (·) ≡ 0 biases search algorithm to make deep probes into the search tree
· Note that we would expect ĝ(y) ≤ ĝ(x) for y which is a child of x
· Following x, y becomes E node; then a child of y becomes E node, and so on, until a subtree is fully
searched
· Subtrees of nodes in other children of x are not considered until y is fully explored
· But ĝ(x) is only an estimate of the true cost
· It is possible that for two nodes w and z, ĝ(w) < ĝ(z) and z is much closer to answer than w
· By using f (·) 6≡ 0, we can force the search algorithm to favor a node z close to the root over node w,
reducing the possiblity of deep and fruitless search
– A search strategy that uses a cost function ĉ(x) = f (h(x)) + ĝ(x) to select the next E-node would always choose
for its next E-node a live node with least ĉ(·)
∗ Such a search strategy is called an LC-search (Least Cost search)
∗ Both BFS and DFS are special cases of LC-search
∗ In BFS, we use ĝ(x) ≡ 0 and f (h(x)) as the level of node x
· LC search generates nodes by level
∗ In DFS, we use f (h(x)) ≡ 0 and ĝ(x) ≥ ĝ(y) whenever y is a child of x
– An LC-search coupled with bounding functions is called an LC branch-and-bound search
– Cost function
∗ If x is an answer node, c(x) is the cost of reaching x from the root of state space tree
∗ If x is not an answer node, c(x) = ∞, provided the subtree x contains no answer node
∗ If subtree x contains an answer node, c(x) is the cost of a minimum cost answer node in subtree x
∗ ĉ(·) with f (h(x)) = h(x) is an approximation to c(·)
• The 15-puzzle
Branch and Bound 3
∗ ĉ(x) = f (x) + ĝ(x) where f (x) is the length of the path from root to x and ĝ(x) is an estimate of the length
of a shortest path from x to a goal node in the subtree with root x
∗ One possible choice for ĝ(x) is the number of nonblank tiles not in their goal position
∗ There are at least ĝ(x) moves to transform state x to a goal state
· ĉ(x) is a lower bound on c(x)
· ĉ(x) in the configuration below is 1 but you need more moves
1 2 3 4
5 6 8
9 10 11 12
13 14 15 7
• Control abstractions for LC-search
– Search space tree t
– Cost function for the nodes in t: c(·)
– Let x be any node in t
∗ c(x) is the minimum cost of any answer node in the subtree with root x
∗ c(t) is the cost of the minimum cost answer node in t
– Since it is not easy to compute c(), we’ll substitute it by a heuristic estimate as ĉ()
– Algorithm LCSearch uses ĉ() to find an answer node
typedef struct
{
list_node_t * next;
list_node_t * parent;
float cost;
} list_node_t;
list_node_t list_node;
algorithm LCSearch ( t )
{
// Search t for an answer node
if ( *t is an answer node )
{
print ( *t );
return;
}
E = t; // E-node
Initialize the list of live nodes to be empty;
while ( true )
{
for each child x of E
{
if x is an answer node
{
print the path from x to t;
return;
}
Branch and Bound 5
∗ Objective is to select a subset J of n jobs such that all jobs in J can be completed by their deadline
∗ A penalty will incur only on jobs not in J
∗ For optimal solution, J should be such that the penalty is minimized among all possible subsets J
∗ Problem instance: n = 4, j1 = (5, 1, 1), j2 = (10, 3, 2), j3 = (6, 2, 1), j4 = (3, 1, 1)
∗ Solution space is all possible subsets of (j1 , j2 , j3 , j4 )
∗ Organize solution space by either of the two formulations of sum-of-subsets problem (variable or fixed tuple
size)
∗ Optimal solution comes as J = {j2 , j3 }, with a penalty cost of 8
∗ Cost function c(x) can be defined as the minimum penalty corresponding to any node in the subtree with root
x
∗ c(x) = ∞ for any non-feasible node
∗ Variable tuple size formulation
· c(3) = 8, c(2) = 9, and c(1) = 8
∗ Fixed tuple size formulation
· c(1) = 8, c(2) = 9, c(5) = 13, and c(6) = 8
∗ c(1) is the penalty corresponding to an optimal solution J
∗ Getting the estimate bound ĉ(x)
· ĉ(x) ≤ c(x) for all x
· Let Sx be the subset of jobs selected for J at node x
P
· If m = max{i|i ∈ Sx } then ĉ(x) = i < m pi is an estimate for c(x) with the property ĉ(x) ≤ c(x)
i 6∈ Sx
· For a non-feasible node, ĉ(x) = ∞
P
· In the tree with variable tuple formulation, for node 6, S6 = {j1 , j2 } and hence, m = 2; Also, i < 2 pi =
i 6∈ S2
0
P
· For node 7, S7 = {1, 3} and m = 3; therefore, i < 2 = pi = p2 = 10
i 6∈ S2
· In the tree with fixed tuple formulation, node 12 corresponds to the omission of job j1 and hence a penalty
of 5
· Node 13 corresponds to the omission of jobs j1 and j3 and hence a penalty of 13
P
∗ A simpler upper bound u(x) on the cost of a minimum-cost answer node in the subtree x is u(x) = i6∈Sx pi
· u(x) is the cost of the solution Sx corresponding to node x
• FIFO branch-and-bound
P
– FIFO branch-and-bound for job sequencing problem can begin with U = ∞ (or U = 1≤i≤n pi ) as an upper bound
on the cost of a minimum-cost answer node
– Start with node 1 as the E-node in the variable tuple formulation of the state space tree
∗ Nodes 2, 3, 4, and 5 are generated in that order
∗ u(2) = 19, u(3) = 14, u(4) = 18, and u(5) = 21
– Variable U is updated to 14 when node 3 is generated
– Since ĉ(4) and ĉ(5) are greater than U , nodes 4 and 5 get killed (or bounded)
– Only nodes 2 and 3 remain alive
– Node 2 becomes the next E-node; its children are generated as nodes 6, 7, and 8
– u(6) = 9 and so, U is updated to 9
– ĉ(7) = 10 > U and so, node 7 gets killed
– Next node 3 becomes E-node; generating node 9 and 10
– u(9) = 8 updating U to 8