UNIT V: BRANCH AND BOUND

General method, applications - Travelling sales person problem,0/1 knapsack problem- LC Branch
and Bound solution, FIFO Branch and Bound solution.
NP-Hard and NP-Complete problems: Basic concepts, non-deterministic algorithms, NP-Hard and
NP-Complete classes, cook’s theorem.

General method:

Branch and Bound is another method to systematically search a solution space. Just like
backtracking, we will use bounding functions to avoid generating subtrees that do not
contain an answer node. However, Branch and Bound differs from backtracking in two
ways:
1) It has a branching function, which can be a depth first search, breadth first
search or based on bounding function.
2) It has a bounding function, which goes far beyond the feasibility test as a mean
to prune efficiently the search tree.

Branch and Bound refers to all state space search methods in which all children of the E-
node are generated before any other live node becomes the E-node

Branch and Bound is the generalization of both graph search strategies, BFS and D
search.
 A BFS like state space search is called as FIFO (First in first out) search as
the list of live nodes in a first in first out list (or queue).
 A D search like state space search is called as LIFO (Last in first out)
search as the list of live nodes in a last in first out (or stack).

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-an-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.

Travelling Sales Person Problem:

If there are n cities and cost of travelling from one city to another city is given. A sales person
must start from any one of the cities and must visit all the cities exactly once and must return to the
starting place with shortest distance or minimum cost.
State space Tree for the travelling salesperson problem with n=4 and i0 = i4 = 1 i.e. the
graph contains 4 nodes and start and end nodes are node 1.

Initially the sales person starts from node 1. Which is E-Node.

As there are 4 nodes the sales person starts at node 1 and reaches node 1 through nodes 2, 3
and 4.
From node1 there is a possibility of travelling to node 2 or node 3 or node 4. So it generates 3
live nodes namely node 2, node 3 and node 4.
Now one of nodes 2 or 3 or 4 becomes E-node depending on the cost. For each node a cost
value will be calculated. Depending on the cost the next E-node is selected. The process is
continued.
Let G=(V,E) be a directed graph defining an instance of the travelling sales person problem.
Let Cij be the cost of the edge (i,j) and cij=if (i,j)E(G) and let V n .
Assume that every tour starts and ends at vertex 1.

To use least cost branch and bound to search the travelling sales person state space tree, we
must define a cost function c(x) and two other functions cˆ(x) and uˆ(x) such that
cˆ(x)c(x) uˆ(x) .
LCBB Travelling Salesperson problem: The cost matrix of a graph
consisting of n vertices is given under. Each entry in the cost matrix is considered as the cost
to travel from one node to another node. We need to find the least cost path from node 1 to

node 1 through all other nodes such that the remaining nodes will be visited only once using
Least Cost Branch and Bound Method.

Example: Find the shortest tour for TSP for the given adjacent matrix of a graph using
Brach and Bound
Cost matrix is the given matrix.
Reduced cost matrix can be obtained as follows.

A row is said to be reduced iff it contains at least one 0 and all remaining entries are nonnegative.
A column is said to be reduced iff it contains at least one 0 and all remaining entries are
nonnegative.
A matrix is reduced iff every row and column are reduced.
LCBB Travelling Salesperson problem Algorithm:
Step 1: Write the initial cost matrix and reduce it
( Rules for Reduction: To reduce a matrix, perform the row reduction and column reduction of the
matrix separately and a row or a column is said to be reduced if it contains at least one entry ‘0’ in
it.)
Step 2: We consider all other vertices one by one.
We select the best vertex where we can land upon to minimize the tour cost.
After finding the minimum cost tour repeat the Step 1.
Step 3: Construct the state space tree and identify the minimum cost tour.

Complexity of this Algorithm is O(n2)

0/1 Knapsack problem: LCBB solution
The 0/1 knapsack problem states that, there are n objects given and capacity of knapsack is
m. Then select some objects to fill the knapsack in such a way that it should not exceed the
capacity of knapsack and maximum profit can be earned.
The 0/1 knapsack problem can be stated as

Max z = p1 x1 + p2 x2 +..... + pn xn
w1 x1 + w2 x2 +...... + wn xn <= m
Xi=0 or 1.
A branch and bound technique is used to find solution to the knapsack problem. But we
cannot directly apply the branch and bound technique to the knapsack problem. Because the
branch and bound deals with only minimization problems. We modify the knapsack problem
to the minimization problem. The modified problem is

Min z p1 x1 p2 x2 pn xn

w1 x1 + w2 x2 +...... + wn xn <= m
Xi=0 or 1.

Let cˆ(x) and uˆ(x) are the two cost functions such that cˆ(x)c(x)uˆ(x) satisfying the
requirements where
n
c(x) = - Ʃ pi xi
i=n

The c(x) is the cost function for answer node x, which lies between two functions called lower and
upper bounds for the cost function c(x).

The search begins at the root node. Initially we compute the lower and upper bound at root node
called cˆ(1) and uˆ(1) . Consider the first variable x1 to take a decision. The x1 takes values either
0 or 1.
Compute the lower and upper bounds in each case of variable. These are the nodes at the first
level. Select the node whose cost is minimum i.e.
c(x) min{c(lchild(x)),c(rchild(x))}
c(x) min{cˆ(2)),cˆ(3))}
The problem can be solved by making a sequence of decisions on the variables x1,x2,…,xn
level wise. A decision on the variable xi involves determining which of the values 0 or 1 is to
be assigned, to it by defining c(x) recursively.

The path from root to the leaf node whose height is maximum is selected and is the solution
space for the knapsack problem.
Example: Consider the knapsack instance n=4, (p1,p2,p3,p4)=(10,10,12,18),
(W1,W2,W3,W4)=(2,4,6,9), m=15. Let us trace the working of an LCBB search

Solution:
[ Hint: Lower Bound can be calculated by considering fractional values, where as Upper Bound
does not consider fractional values and initially consider the profits be negative. If Lower Bounds
are same, then compare Upper Bounds ]

LC Branch and Bound state space tree

Node 8 is a solution node (solution vector)

X1=1
X2=1
X3=0
X4=1
p1x1+p2x2+p3x3+p4x4
10x1+10=1+12x0+18x1
=38
We need to consider all n items.
The tuple size is n
0/1 Knapsack problem using LCBB Algorithm:
Step 1: Calculate Lower Bound and Upper Bound,
Compare Lower Bounds and expand the node which is having least Lower Bound value
Step 2: Repeat the step 1 till all the items are considered
Step 3: By considering the state space tree calculate the maximum profit by considering the given
size of the knapsack.

Function UpperBound ( ) for Knapsack problem

cp - current profit
cw- current weight
k – k number of decisions
m - Capacity of knapsack

Algorithm Ubound(cp,cw,k,m)
{
b := cp;
c := cw;
for i:= k+1 to n do
{
if ( c + w[i] <= m ) then
{
c := c + w[i];
b := b - p[i];
}
}
return b;
}

Complexity of this Algorithm is O(n)

0/1 Knapsack problem using FIFO Branch and Bound:

Example: Consider the knapsack instance n=4, (p1,p2,p3,p4)=(10,10,12,18),
(W1,W2,W3,W4)=(2,4,6,9), m=15. Let us trace the working of an LCBB search

Solution:
[ Hint: Lower Bound can be calculated by considering fractional values, where as Upper Bound
does not consider fractional values and initially consider the profits be negative. Make the initial
Upper Bounds as Global Upper Bound. Compare the each node Upper Bound value with Global
Upper Bound value, if find minimum value than the Global Upper Bound value, then update the
Global Upper Bound. Similarly compare Lower Bound value of each node with Global Upper Bound
value, if it is less than Global Upper Bound then kill that node. ]

Initially the root node i.e., node 1 be the E-Node. The Queue of Live nodes is empty.
Since this is not the solution Upper is initialized to u(1) = -32.
We assume the children are generated from left to right. Nodes 2 and 3 are generated and are
added to the queue.

2 3

Node 2 becomes the next E Node. Its children nodes are generated. Node 4 and 5 and are
added to Queue.

3 4 5

Node 3 the next e-Node, is expanded. Its Children nodes are generated. Node 6 and 7 gets
added to Queue.

4 5 6
Node 7 is immediately killed as cˆ(7) > Upper.
Node 4 is expanded next. Nodes 8 and 9 are generated and are added to queue.

5 6 8 9
Then upper is updated to U(9)= -38.
Nodes 5 and 6 are the next two nodes to become E-Nodes. Neither is expanded as for each
cˆ() > upper.
Node 8 is the next E-Node. Nodes 10 and 11 are generated.

9
Node 10 is infeasible and so killed.
Node 11 has cˆ() > upper and so is also killed.
Node 9 is expanded Next. When node 12 is generated, upper and answer are updated to -38
and 12 respectively. Node 12 joins the queue of live nodes.

12
Node 13 is killed before it can get onto the queue of live nodes as cˆ(13) > upper.
The only remaining live node is node 12. It has no children and the search terminates.

The value of upper and the path from node 12 to the root is the output additional information
is needed to determine the xi values on this path.
The solution is : x1=1, x2=1, x3=0,x4=1

0/1 Knapsack problem using FIFOBB Algorithm:

Step 1: Calculate Lower Bound and Upper Bound, Make the Upper Bound as Global Upper
Bound.
Compare Upper Bounds with Global Upper Bound value if it is less then update Global Upper
Bound value. Compare Lower Bound with Global Upper Bound, if it is less than Global Upper
Bound value, then kill that node.
Step 2: Repeat the step 1 till all the items are considered
Step 3: By considering the state space tree calculate the maximum profit by considering the given
size of the knapsack.
Function UpperBound ( ) for Knapsack problem
cp - current profit
cw- current weight
k – k number of decisions
m - Capacity of knapsack

Algorithm Ubound(cp,cw,k,m)
{
b := cp;
c := cw;
for i:= k+1 to n do
{
if ( c + w[i] <= m ) then
{
c := c + w[i];
b := b - p[i];
}
}
return b;
}

Complexity of this Algorithm is O(n)

NP Hard and NP-Complete:

Basic concepts:

NP Nondeterministic Polynomial time

The problems have best algorithms for their solutions have “Computing times”, that
cluster into two groups

Group 1 Group 2

 Problems with solution time boundby a  Problems with solution times not bound by
polynomial of a small degree. polynomial (simply non-polynomial)

 It also called “Tractable Algorithms”

 These are hard or
intractable problems
 Most Searching & Sortingalgorithms are
polynomial timealgorithms
 None of the problems in this group has been
 Ex: Ordered Search (O (log n)), solved by anypolynomial time algorithm

Polynomial evaluation O(n) Sorting  Ex: Traveling Sales Person O(n2

O(n.log n) 2n) Knapsack O(2n/2)
 No one has been able to develop a polynomial time algorithm for any problem in the
2nd group (i.e., group 2)

So, it is compulsory and finding algorithms whose computing times are greater than
polynomial very quickly because such vast amounts of time to execute that even moderate
size problems cannot be solved.

Theory of NP-Completeness:

Show that may of the problems with no polynomial time algorithms are computational
time algorithms are computationally related.

There are two classes of non-polynomial time problems

1. NP-Hard
2. NP-Complete
NP Complete Problem: A problem that is NP-Complete can solved in polynomial time
if and only if (iff) all other NP-Complete problems can also be solved in polynomial time.

NP-Hard: Problem can be solved in polynomial time then all NP-Complete problems can
be solved in polynomial time.

All NP-Complete problems are NP-Hard but some NP-Hard problems are not known to be
NP-Complete.

Nondeterministic Algorithms:

Algorithms with the property that the result of every operation is uniquely defined are termed
as deterministic algorithms. Such algorithms agree with the way programs are executed on a
computer.

Algorithms which contain operations whose outcomes are not uniquely defined but are
limited to specified set of possibilities. Such algorithms are called nondeterministic
algorithms.

The machine executing such operations is allowed to choose any one of theseoutcomes
subject to a termination condition to be defined later.

To specify nondeterministic algorithms, there are 3 new functions

Choice(S) Arbitrarily chooses one of the elements of sets S

Failure() Signals an unsuccessful completion
Success() Signals a successful completion
 Example for Non-Deterministic algorithms:

Algorithm Search(x){ Whenever there is a set of choices

that leads to a successful
//Problem is to search an element x
completion then one such set of
//output J, such that A[J]=x; or J=0 if x is not choices are always made and the
in A J:=Choice(1,n); algorithm terminates.
if( A[J]:=x) then { A Nondeterministic algorithm
Write(J); terminates unsuccessfully if and
Success() only if (iff) there exists no set of
choices leading to a successful
; signal.
}
else{
write(0)
;
failure()
;
}

Deterministic Knapsack algorithm

Algorithm DKP(p, w, n, m, r, x){ pgiven profits

W:=0; w given weights
P:=0; nNumber of elements
for i:=1 to n do{
x[i]:=choice(0, 1);
m weight of bag limit
W:=W+x[i]*w[i]; P Final Profit
P:=P+x[i]*p[i]; W Final Weight
}
if( (W>m) or (P<r) ) then Failure();
else Success();
}
 The Classes NP-Hard & NP-Complete:
For measuring the complexity of an algorithm, we use the input length as the parameter.
For example, An algorithm A is of polynomial complexity p() such that the computing time
of A is O(p(n)) for every input of size n.
Decision problem/ Decision algorithm: Any problem for which the answer is eitherzero
or one is decision problem. Any algorithm for a decision problem is termed a decision
algorithm.
Optimization problem/ Optimization algorithm: Any problem that involves the
identification of an optimal (either minimum or maximum) value of a given costfunction
is known as an optimization problem. An optimization algorithm is used tosolve an
optimization problem.

P is the set of all decision problems solvable by deterministic algorithms in polynomial time.
NP is the set of all decision problems solvable by nondeterministic algorithms in polynomial
time.

Since deterministic algorithms are just a special case of nondeterministic, by thiswe

concluded that P ⊆ NP

Commonly believed relationship between P & NP

The most famous unsolvable problems in Computer Science is Whether P=NP or
P≠NP In considering this problem, s.cook formulated the following question.

If there any single problem in NP, such that if we showed it to be in ‘P’ then that
would imply that P=NP.
Cook answered this question with

Theorem: Satisfiability is in P if and only if (iff) P=NP

Notation of reducibility:
Let L1 and L2 be problems, Problem L1 reduces to L2 (written L1 α L2) iff there is a way
to solve L1 by a deterministic polynomial time algorithm using a deterministic algorithm
that solves L2 in polynomial time

This implies that, if we have a polynomial time algorithm for L2, Then we can solve L1 in
polynomial time.
Here o is a transitive relation i.e. L1 o L2 and L2 o L3 then L1 o L3

A problem L is NP-Hard if and only if (iff) satisfiability reduces to L ie., Satisfiability α L

A problem L is NP-Complete if and only if (iff) L is NP-Hard and L Є NP

Commonly believed relationship among P, NP, NP-Complete and NP-Hard

Most natural problems in NP are either in P or NP-complete.

Examples of NP-complete problems:

 Packing problems: SET-PACKING, INDEPENDENT-SET.
 Covering problems: SET-COVER, VERTEX-COVER.
 Sequencing problems: HAMILTONIAN-CYCLE, TSP.
 Partitioning problems: 3-COLOR, CLIQUE.
 Constraint satisfaction problems: SAT, 3-SAT.
 Numerical problems: SUBSET-SUM, PARTITION, KNAPSACK.
Cook’s Theorem: States that satisfiability is in P if and only if
P=NP If P=NP then satisfiability is in P
If satisfiability is in P, then
P=NP To do this
A Any polynomial time nondeterministic decision algorithm.
I Inpit of that algorithm

Then formula Q(A, I), Such that Q is satisfiable iff ‘A’ has a successfultermination with
Input I.
 If the length of ‘I’ is ‘n’ and the time complexity of A is p(n) for some polynomial p() then
length of Q is O(p3(n) log n)=O(p4(n))
The time needed to construct Q is also O(p3(n) log n).

 A deterministic algorithm ‘Z’ to determine the outcome of ‘A’ on any input ‘I’
Algorithm Z computes ‘Q’ and then uses a deterministic algorithm for the
satisfiability problem to determine whether ‘Q’ is satisfiable.
 If O(q(m)) is the time needed to determine whether a formula of length ‘m’ is satisfiable
 then the complexity of ‘Z’ is O(p3(n) log n + q(p3(n)log n)).
 If satisfiability is ‘p’, then ‘q(m)’ is a polynomial function of ‘m’ and the complexity of
‘Z’ becomes ‘O(r(n))’ for some polynomial ‘r()’.

 Hence, if satisfiability is in p, then for every nondeterministic algorithm A

in NP, we can obtain a deterministic Z in p.
By this we shows that satisfiability is in p then P=NP

IMPORTANT QUESTIONS

1) Write a non-deterministic algorithm of sorting a list of elements in an array. 8M

2) Explain the applications of branch and bound. 7M
3) Explain with respect to branch and bound 0/1 knapsack problem. 7M
4) Discuss in detail about the classes of NP-hard and NP-complete. 8M
5) Explain Cook’s theorem with an example. 8M
6) Discuss the FIFO branch and bound. 7M
7) Explain Nondeterministic knapsack algorithm 5M