BRANCH AND BOUND : 1 BRANCH AND BOUND Branch and bound is a state space search method in which all the children of a node are generated before expanding any of its children.
BRANCH AND BOUND (Contd..) : 2 BRANCH AND BOUND (Contd..) 1 1 1
3 4 5 2 3 4 5 2 3 4 5
6 7 8 9 8 9 6 7
Live Nodes 2,3,4,5 FIFO Branch & Bound LIFO Branch & (Breadth First Search ) Bound (D-Search)
LC- SEARCH : 3 LC- SEARCH In FIFO and LIFO Branch & Bound, the selection rule for the next E-node is rigid.
The expansion of all live-nodes is required before the node leading to an answer node.
The search for an answer node can be speeded up by using a ranking function c(.) for live nodes.
LC- SEARCH (Contd..) : 4 LC- SEARCH (Contd..) c(x) is the estimated additional computational effort or the additional cost needed to reach an answer node from the live node X.
The cost (of node X) could be (i) the number of nodes in the subtree that need to be generated before an answer node is generated or (ii) the number of levels the nearest answer node is from X.
LC- SEARCH (Contd..) : 5 LC- SEARCH (Contd..) If cost measure (i) is used then the search would always generate the minimum number of nodes every branch and bound algorithm must generate.
If cost measure (ii) is used, then the only nodes to become E-nodes are the nodes on the path from the root to the nearest answer node.
C (x) is defined as below
c(x)=f(h(x))+g(x)
LC- SEARCH (Contd..) : 6 LC- SEARCH (Contd..) h(x) is the cost of reaching x from the root and f(.) is any non decreasing function.
g (x) is the estimated additional effort or cost needed to reach an answer node from X.
A search strategy that uses a cost function c(x) = f(h(x)) + g (x) to select the next E-node, would always choose for its next E-node, a live node with least c(.). Hence such a strategy is called Least cost search or LC-Search
LC- SEARCH (Contd..) : 7 LC- SEARCH (Contd..) BFS and DFS are special cases of LC-Search
LC search with g (x)=0 and f(h(x)) = level of x is BFS
LC search with f(h(x)) =0 and g (x) >= g (y) whenever y is a child of x is DFS.
LC-Search with bounding functions is LC branch and bound search.
LC- SEARCH (Contd..) : 8 LC- SEARCH (Contd..) The Actual cost of X is denoted with c(X).
Thus c(X) is an estimation of C(X).
An LC-search expands the node with minimum cost c(X) .
But it is not necessary that LC-search always finds an answer node with minimum cost.
For two nodes X and Y with c(X) <c(y), it may be possible that c(X)>c(Y).
Even if c(X)<c(Y) it may also be possible that a minimum cost answer node may not be found.
LC- SEARCH - Algorithm : 9 LC- SEARCH - Algorithm // LC –search to find an answer node //
procedure LC(T, c)
if T is an answer node then output,
return; endif
E?T // E-node //
Initialize the list of live nodes to empty
loop
for each child X of E do
if X is an answer node then
LC- SEARCH – Algorithm (Contd..) : 10 LC- SEARCH – Algorithm (Contd..) output the path from X to T return
endif
Call ADD(X) // X is a new live node //
PARENT(X)? E // Pointer for path to root //
repeat
if there are no more live nodes then
print (“no answer node”) stop endif
call LEAST(E) // E is a pointer to current E-node //
repeat
end LC
LC search for minimum cost answer node : 11 LC search for minimum cost answer node // LC search for minimum cost answer node //
procedure LC1(T, c)
E?T // First E-node //
Initialize the list of live nodes to empty
loop
if E is an answer node then output
path from E to T return
endif
LC search for minimum cost answer node (Contd..) : 12 LC search for minimum cost answer node (Contd..) for each child X of E do
call ADD(X); PARENT(X)?E
repeat
if there are no more live nodes
then print (“no answer node”) stop
endif
call least(E)
repeat
end LC1
LC search observation : 13 LC search observation In LC- Search to find an answer node, observe that the moment an answer node is found, control is returned; otherwise the nodes are stored and the least cost one is tested if it is an answer node
In LC- Search to find a minimum cost answer node, observe that all the children are stored first and then tested for Least (E)
BOUNDING : 14 BOUNDING Thus a minimum cost answer node is found if all live nodes are examined and terminated only when no more live nodes are available
BOUNDING
Three strategies FIFO,LIFO and LC are available to find minimum cost answer node.
A cost function c(x) such that c(x) = c(x) is used to provide lower bounds on solutions
BOUNDING (Contd..) : 15 BOUNDING (Contd..) If U is an upper bound ,on the cost of a minimum cost solution, then all live nodes with c(x)>U may be killed as c(x)= c(x) >U .
In case an answer node with cost U has already been reached, then all live nodes with c(x) = U may be killed.
The starting value for U may be obtained by some heuristic or may be set to 8.
BOUNDING (Contd..) : 16 BOUNDING (Contd..) Each time a new answer node is found the value of U may be updated.
A small positive constant ? is introduced such that for any two feasible nodes X and Y with U (X) <U(Y), then U(X) < U(X) + ? < U (Y).
This ? is needed to distinguish between the case when a solution with cost U(X) has been found and the case when such a solution has not been found.
BOUNDING (Contd..) : 17 BOUNDING (Contd..) When such a solution is not found the upper bound U is updated to min { U, U(X) + ? } and the live nodes Y with c(y) = U may be killed.
This does not kill the node that promised to lead to a solution with value = U.
Application of Branch and Bound : 18 Application of Branch and Bound Branch and bound algorithms can be applied to optimization problems.
We only deal with minimization problems, because a maximization problem is easily converted into a minimization problem by changing the sign of the objective function.
Application of Branch and Bound contd.. : 19 Application of Branch and Bound contd.. Searching for an optimal solution is equivalent to searching for a least cost answer node.
The c(.) function will estimate the objective function value and not the cost of reaching an answer node.
Any node representing a feasible solution will be an answer node.
Answer nodes and solution nodes are indistinguishable.
Implementing FIFO Branch and bound (FIFOBB) and LC branch and bound (LCBB) : 20 Implementing FIFO Branch and bound (FIFOBB) and LC branch and bound (LCBB) In FIFOBB, live nodes are stored in a queue and deleted from a queue.
In LCBB live nodes are added to a min-heap and deleted from a min-heap.
ZERO-ONE KNAPSACK PROBLEM : 21 ZERO-ONE KNAPSACK PROBLEM The modified knapsack problem is
n
minimize -?pixi
i = 1
n
subject to ?wixi = m
i=1
xi = 0 or xi = 1 1=i=n
ZERO-ONE KNAPSACK PROBLEM (Contd..) : 22 ZERO-ONE KNAPSACK PROBLEM (Contd..) The cost function c(x) is defined as follows for every feasible node (answer node), we define c(x)= -?pixi 1=i=n
c(x)= 8 for infeasible leaf nodes
For non leaf nodes, c(x) is recursively defined to be
min{ c(LCHILD(X)), c(RCHILD(X))}
c(x) and u(x) are defined such that c(x) =c(x) =u(x) for every node x.
ZERO-ONE KNAPSACK PROBLEM Algorithm : 23 ZERO-ONE KNAPSACK PROBLEM Algorithm c(x)= -Bound (q, ?wixi, j-1, M) =c(X)
1=i=n
Procedure Bound(p,w,k,M)
// P current profit total, W current weight //
// k index of the last removed item //
// M is the knapsack size, the result is a new profit //
global n, P(1:n),W(1:n)
integer k, i, real b, c, p, w, M
b?p; c?w
ZERO-ONE KNAPSACK PROBLEM Algorithm(Contd..) : 24 ZERO-ONE KNAPSACK PROBLEM Algorithm(Contd..) for i?k+1 to n do
c?c+w(i).
if c < M then b?b+p(i)
else return (b+(1-((C-M)/W(i))) P(i)))
endif
repeat
return(b)
end BOUND
c(x) is the lower
bound for c(X)
procedure to find upper bound : 25 procedure to find upper bound U(x) = UBOUND (-?pixi , ?wixi , j-1, M)
1=i<j 1=i<j
X is the node where x1,…… xj-1 are known
procedure to find upper bound (Contd..) : 26 procedure to find upper bound (Contd..) Procedure UBOUND(p, w, k, m)
// p current total profit, W current weight total, K index of last //
// removed item, M the knapsack size. The result is a new profit //
global n, p(1: n), W(1:n)
integer k, I, real b, c, p, w, M
b? p ; c?w
for i?k+1 to n do
if c + w(i) =M then c? c + w(i) ; b? b + p(i) endif
repeat
return (b)
end UBOUND
procedure to find lower bound - Example : 27 procedure to find lower bound - Example Example : Let the knapsack instance be n=4 :
(p1, p2, p3, p4 ) = (10, 10 12, 18);
(w1, w2, w3, w4) = (2, 4, 6, 9), M = 15
For the root i.e. node 1 c(1) = -38 because Bound (0, 0, 0, 15) is called
Initially b? 0 ; c? 0
for I? 1 to 4 do
i ? 1
c? 0+2 = 2 ; 2 < 15 so b? 0+ 10 ; i?2 , c? 2+4 = 6 < 15 so b? 10 + 10 =20
i?3 ; c? 6+6 =12<15 so b? 20+12=32; I?4, c?12+9=21>15
so b? 32 + (1-(6/9))x18) = 38 as negative
procedure to find upper bound – Example : 28 procedure to find upper bound – Example Let us compute u(1) UBOUND (0,0,0,15) is called, Initially
b?0; c?0 for i? 1 to 4 do i?1; c?0+2<15 so b?0 +10; i ? 2
c?2+4<15 so b?10+10=20;
i?3 c?6+6=12<15 so b?20+12 = 32;
i?4 c?21>M so return b = 32with negative sign
?U(1) = -32
Solution of Knapsack problem : 29 Solution of Knapsack problem Since node 1 is not a solution node, ans = 0 and U =u(1) + ? (u =8 initially) U= -32 + ? Node 1 is expanded to give two children nodes 2 and 3.
Node 2 is corresponding to x1 =1 and node 3 is for x1=0 Let us compute c(2) , Û(2) and c(3), Û(3) values.
For c(2) BOUND(-10,2,1,15) is called and for Û(2) UBOUND (-10,2,1,15) is called.
Solution of Knapsack problem (contd..) : 30 Solution of Knapsack problem (contd..) We observe that c (2) =-38 and u(2) =-32.
For c(3) BOUND (0,0,1,15) Is called and for u(3), UBOUND (0,0,1,15) is called.
We observe that c(3)= -32 and u(3) = -22.
As min (-38, -32) = -38,node 2 is expanded next.
As min (-38, -36) = -38,node 4 is expanded next.
c(x) for nodes 6 & 7 is same.
Solution of Knapsack problem (contd..) : 31 Solution of Knapsack problem (contd..) c (X) = -38 U(X) = -32
xi=1 xi= 0
1
-38 -32
-32 2 3 -22
-38 -36
-32 4 5 -32
-38 7 -38
-32 6 -38
-38 -20
-38 8 9 -20
Solution of Knapsack problem (contd..) : 32 Solution of Knapsack problem (contd..) Let us assume node 7 is expanded.
As u(7) + ? = -38 + ? < U=-32+ ? ,so U is updated to u(7)+ ? = -38 + ?
Node 8 is a solution node,so u is updated to min{u(8), u(8)+ ? } = -38
c(9) = -20 >U so it is killed.
For nodes 6 and 8(which are live nodes
c (E) = U so search terminates with node 8 the answer node. Least cost is –38 and the path is 8, 7, 4, 2,1.
Solution of Knapsack problem (contd..) : 33 Solution of Knapsack problem (contd..) To find values of xi’s, a bit field, TAG is associated with each node.
TAG(2) = TAG(4) = TAG (6)= TAG(8)=1 and TAG(3)= TAG(5)= TAG(7)= TAG(9) = 0.
Hence xi =1, x2 =1, x3= 0, x4= 0.