Branch and bound
Branch and bound is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization.
As a solution Branch and bound algorithm was developed by Narendra and Fukunaga in 1977
As Generally, the Branch and bound method is applied for optimized problem, any problem that we using for maximization or minimization for that kind of problem we use this Branch and bound Method.
In this method a state space tree of all possible solutions is generated. Then partitioning or branching is done at each of the tree. Then we compare node’s bound value with the value of the best solution obtained up to now. if the bond value of some node is better than the best solutions then that corresponding node is not expanded. it is also called branch is pruned there. After computation of bounding value at each node, we compare it with best solution and then expanding the node further can lead to a final solution node.
The branching procedure replaces an original problem by a set of new problem that are
- Mutually exclusive and exhaustive sub-problem of the original problem.
- Partially solved version of the original problem
- Smaller problems than original problem.
There are various reason for terminating search path in state space tree of branch and bound
- The value of the node’s bound is not better than the best solutions .
- There is no feasible solutions.
- A new better solution can be obtained rather than continuing further.
State Space Tree :
if we represent solution space in the form of a tree then the tree is referred as the state space tree.
Example : 4-Queen Problem:
Initially x1=1, 2, 3 or 4
it means we can place the 1st queen in Either 1st , 2nd , 3rd or 4th column.
If x1= 1 i.e., the 1st queen in 1st column.
then x2 = 2, 3 or 4
it means we can place the 2nd queen in Either 2nd , 3rd or 4th column
similarly the 3rd queen can place 3rd or 4th column
if x2 = 2., the 2nd queen in 2nd column . then x3 =3 or 4
It Means we can place the 3rd queen in Either 3rd column or 4th column.
If x3 =4 i.e., the 3rd queen in 4th column.
then x4=3
it means we can place the 4th queen in 3rd column
If we expand all the nodes the state space tree of 4 — Queen problem will look this.
In this state-space tree, no 2 nodes are unit equal or similar.
Answer Node:
Those solutions states S for which path from root to S defines a tuple which is a member of the set of solutions(i.e., if satisfies the implicit constraints) of the problem.
If 4 and 6 are the answer states .
(1 ,2 ,3 ,4) and (1 ,6) are solution states
Live Node:
A node which has been generated and all of those children have not yet been generated is live live node
Here 1 is a live node since the children of 1 not yet been generated
Here 2 and 3 are live node.
But 1 is not a live node since all the children of 1 are generated
Dead Node:
It is a generated node that is either not to be expanded further or one for which all of its children have been generated
Here 1 is already expanded.
Assume that 2 and 3 are not expanded . then 1, 2 ,3 are dead node
Here 1 is already expanded
And 2’s children are currently being expanded.so it is E-node. Assume that 3 and 4 are not expanded. then 1,3 and 4 are dead node
Generally Three types of searching strategies used in Branch and Bound
- FIFO(First-In-First-Out) Search
- LIFO(Last-In-Last-Out) Search
- LC(Least Cost Search)
The 0/1 Knapsack Problem
Positive integer P1 , P2 , …, Pn (profit)
W1 , W2 , …, Wn (weight)
M (capacity)
maximize i=1 ∑Pi Xi
subject to W X Mi i i n ≤ = ∑ 1Xi = 0 or 1 , i =1, …, n.
the problem is modified:
minimize − = ∑P Xi i i n 1
HOW TO FIND THE UPPER BOUND?
Ans: by quickly finding a possible solution: ranging from the smallest available i , scanning towards the biggest i’s till M is exceeded. The upper bound is calculated.
E.g. n = 6, M = 34
(Pi/Wi≥ Pi+1/ Wi+1)
A feasible solution: X1 = 1, X2 = 1, X3 = 0, X4 = 0, X5 = 0, X6 = 0
-(P1 +P2 ) = -16 (upper bound)
Any answer more than -16 can’t be associate optimal solution.
HOW TO FIND THE LOWER BOUND?
Ans: By quiet our restriction from Xi = 0 or 1to 0≤ Xi ≤ 1(knapsack Problem) Let − = ∑P Xi i i be an optimal solution for 0/1 knapsack problem and − ′ = ∑P Xi i n i 1 be an optimal solution for knapsack problem. Let Y=− = ∑P Xi i i n 1 , Y’ = − ′ = ∑P Xi i n i 1 . ⇒Y’ ≤Y
THE KNAPSACK PROBLEM
we are able to use the greedy methodology to seek out associate degree optimum answer for Knapsack problem.
as an example, for the state of X1=1 and X2=1, we’ve got
X1 = 1, X2 =1, X3 = (34–6–10)/8=5/8, X4 = 0, X5 = 0, X6 =0
-(P1 +P2 +5/8P3 ) = -18.5 (lower bound)
-18 is our lower bound. (only take consider integers)
HOW TO EXPAND THE TREE?
By the best-first search scheme
that is, by increasing the node with the simplest edge. If 2 nodes have a similar lower bounds, expand the node with the lower bound.
Node 2 is terminated as a result of its edge is up to the edge of node 14.
Nodes 16, 18 and others are terminated because the local lower bound is equal to the local upper bound.
(lower bound ≤ optical solution ≤ upper bound)