# 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)