Backtracking is to cut off a branch of the problemâ€˜s state-space tree as soon as we can deduce that it cannot lead to a solution.

**BRANCH-AND-BOUND**

Backtracking
is to cut off a branch of the problemâ€˜s state-space tree as soon as we can
deduce that it cannot lead to a solution.

This idea
can be strengthened further if we deal with an optimization problem, one that
seeks to minimize or maximize an objective function, usually subject to some
constraints. Note that in the standard terminology of optimization problems, a
feasible solution is a point in the problemâ€˜s search space that satisfies all
the problemâ€˜s constraints

(e.g. a
Hamiltonian circuit in the traveling salesman problem, a subset of items whose
total weight does not exceed the knapsackâ€˜s capacity), while an optimal
solution is a feasible solution with the best value of the objective function
(e.g., the shortest Hamiltonian circuit, the most valuable subset of items that
fit the knapsack).

**Compared to backtracking,
branch-and-bound requires two additional items.**

A way to provide, for every node of a state-space
tree, a bound on the best value of the objective functions on any solution that
can be obtained by adding further components to the partial solution
represented by the node

The value
of the best solution seen so far

**GENERAL METHOD**

If this information is available, we can compare a
nodeâ€˜s bound value with the value of the best solution seen so far:

if the bound value is not better than the best
solution seen so farâ€”i.e., not smaller for a minimization problem and not
larger for a maximization problemâ€”the node is nonpromising and can be
terminated (some people say the branch is pruned) because no solution obtained
from it can yield a better solution than the one already available.

**E.g. Termination of search path**

In
general, we terminate a search path at the current node in a state-space tree
of a branch-and-bound algorithm for any one of the following three reasons:

1. The value
of the nodeâ€˜s bound is not better than the value of the best solution seen so
far.

2. The node
represents no feasible solutions because the constraints of the problem are
already violated.

3. The
subset of feasible solutions represented by the node consists of a single point
(and hence no further choices can be made)â€”in this case we compare the value of
the objective function for this feasible solution with that of the best
solution seen so far and update the latter with the former if the new solution
is better.

** ASSIGNMENT PROBLEM**

Let us
illustrate the branch-and-bound approach by applying it to the problem of
assigning n people to n jobs. So that the total cost of the assignment is as
small as possible.

An
instance of the assignment problem is specified by an n-by-n cost matrix C so
that we can state the problem as follows:

Select
one element in each row of the matrix so that no two selected elements are in
the same column and their sum is the smallest possible.

**Demonstrate of solving this
problem using the branch-and-bound**

This is
done by considering the same small instance of the problem:

To find a
lower bound on the cost of an optimal selection without actually solving the
problem, we can do several methods.

For
example, it is clear that the cost of any solution, including an optimal one,
cannot be

smaller
than the sum of the smallest elements in each of the matrixâ€˜s rows. For the
instance here, this sum is 2 +3 + 1 + 4 = 10.

It is
important to stress that this is not the cost of any legitimate selection (3
and 1 came from the same column of the matrix); it is just a lower bound on the
cost of any legitimate selection.

We Can
and will apply the same thinking to partially constructed solutions. For
example, for any legitimate selection that selects 9 from the first row, the
lower bound will be 9 + 3 + 1 + 4 = 17.

**Fig: Levels 0 and 1 of the
State-space tree for the instance of the assignment problem**

(being
solved with the best-first branch-and- bound algorithm. The number above a node
shows the order in which the node was generated. A nodeâ€˜s fields indicate the
job number assigned to person *a,* and the
lower bound value, *lb* for this node.)

This
problem deals with the order in which the treeâ€˜s nodes will he generated.
Rather than generating a single child of the last promising node as we did in
backtracking, we wilt generate all the children of the most promising node
among non-terminated leaves in the current tree. (Non-terminated, je., still
promising, leaves are also called live.)

To find
which of the nodes is most promising, we are comparing the lower bounds of the
live node. It is sensible to consider a node with the best bound as most
promising, although this does not, of course, preclude the possibility that an
optimal solution will ultimately belong to a different branch of the
state-space tree.

This
variation of the strategy is called the **best-first
branch-and-bound**. Returning to the instance of the assignment problem given
earlier, we start with the root that corresponds to no elements selected from
the cost matrix. As the lower bound value for the root, denoted *lb *is 10.

The nodes
on the first level of the free correspond to four elements (jobs) in the first
row of the matrix since they are each a potential selection for the first
component of the solution. So we have four live leaves (nodes 1 through 4) that
may contain an optimal solution. The most promising of them is node 2 because
it has the smallest lower bound value.

Following
our best-first search strategy, we branch out from that node first by
considering the three different ways of selecting an element from the second
row and not in the second columnâ€”the three different jobs that can be assigned
to person b.

**Figure:
Levels 0, 1. and 2 of the state-space tree for the instance of the assignment
problem**

(being
solved with the best-first branch-and- bound algorithm)

Of the
six live leaves (nodes 1, 3, 4, 5, 6, and 7) that may contain an optimal
solution, we again choose the one with the smallest lower bound, node 5.

First, we
consider selecting the third columnâ€˜s element from câ€˜s row (i.e., assigning
person c to job 3); this leaves us with no choice but to select the element
from the fourth column of dâ€˜s row (assigning person d to job 4).

This
yields leafs that corresponds to the feasible solution (a â†’2, bâ†’1, câ†’3, d â†’4)
with (he total cost of 13. Its sibling, node 9, corresponds to the feasible
solution {a â†’ 2, b â†’1, c

â†’ 4, d â†’
3) with the total cost of 25, Since its cost is larger than the cost of the
solution represented by leafs, node 9 is simply terminated.

Note that
if its cost were smaller than 13. we would have to replace the information
about the best solution seen so far with the data provided by this node.

Now, as
we inspect each of the live leaves of the last state-space tree (nodes 1, 3, 4,
6, and

7 in the
following figure), we discover that their lower bound values are not smaller
than 13 the value of the best selection seen so far (leaf 8).

Hence we
terminate all of them and recognize the solution represented by leaf 8 as the
optima) solution to the problem.

**Figure: Complete state-space tree
for the instance of the assignment problem**

(Solved
with the best-first branch-and-bound algorithm)

**KNAPSACK PROBLEM**

**Illustration**

Given n
items of known weights w_{i} and values v_{i}, i = 1,2,..., n,
and a knapsack of capacity W, find the most valuable subset of the items that
fit in the knapsack. It is convenient to order the items of a given instance in
descending order by their value-to-weight ratios. Then the first item gives the
best payoff per weight unit and the last one gives the worst payoff per weight
unit, with ties resolved arbitrarily:

It is
natural to structure the state-space tree for this problem as a binary tree
constructed as follows (following figure).

Each node
on the *i*th level of this tree, 0 â‰¤ i
â‰¤ n, represents all the subsets of *n*
items that include a particular selection made from the first *i* ordered items. This particular
selection is uniquely determined by a path from the root to the node: a branch
going to the left indicates the inclusion of the next item while the branch
going to the right indicates its exclusion.

We record
the total weight *w* and the total
value *v* of this selection in the
node, along with some upper bound *ub*
on the value of any subset that can be obtained by adding zero or more items to
this selection.

A simple
way to compute the upper bound *ub* is
to add to *v*, the total value of the
items already selected, the product of the remaining capacity of the knapsack ** W - w**
and the best per unit payoff among the remaining items, which is v

As a
specific example, let us apply the branch-and-bound algorithm to die same
instance of

the
knapsack problem , At the root of the state-space tree (in the following
figure), no items have been selected as yet. Hence, both the total weight of
the items already selected w and their total value v are equal to 0.

The value
of the upper bound computed by formula **( ub=v+(W-w)(v_{i+1}/w_{i+1})**
is $100. Node 1, the left child of the root, represents the subsets that include
item, 1.

The total
weight and value of the items already included are 4 and $40, respectively; the
value of the upper bound is 40 + (10-4)*6 = $76.

**Fig:
State-space tree of the branch-and-bound algorithm for the instance of the
knapsack problem**

Node 2
represents the subsets that do not include item 1. Accordingly, w = 0, v= $0,
and ub=0+(10-0)*6=$60.

Since
node 1 has a larger upper bound than the upper bound of node 2, it is more
promising for this maximization problem, and we branch from node 1 first. Its
childrenâ€”nodes 3 and 4â€”represent subsets with item 1 and with and without item
2, respectively.

Since the
total weight *w* of every subset
represented by node 3 exceeds the knapsackâ€˜s capacity, node 3 can be terminated
immediately. Node 4 has the same values of *w*
and *u* as its parent; the upper bound *ub* is equal to 40 + (10-4)*5 = $70.

Selecting
node 4 over node 2 for the next branching, we get nodes 5 and 6 by respectively
including and excluding item 3. The total weights and values as well as the
upper bounds for these nodes are computed in the same way as for the preceding
nodes.

Branching
from node 5 yields node 7, represents no feasible solutions and node 8 that
represents just a single subset {1, 3}.

The
remaining live nodes 2 and 6 have smaller upper-bound values than the value of
the solution represented by node 8. Hence, both can be terminated making the
subset {1, 3} of node 8 the optimal solution to the problem.

Solving
the knapsack problem by a branch-and-bound algorithm has a rather unusual
characteristic.

Typically,
internal nodes of a state-space tree do not define a point of the problemâ€˜s
search space, because some of the solutionâ€˜s components remain undefined. For
the knapsack problem, however, every node of the tree represents a subset of
the items given.

We can
use this fact to update the information about the best subset seen so far after
generating each new node in the tree. If we did this for the instance
investigated above, we could have terminated nodes 2 & 6 before node 8 was
generated because they both are inferior to the subset of value $65 of node 5.

**INTRODUCTION TO NP-HARD AND
NP-COMPLETENESS**

* P*: the
class of decision problems that are solvable in O(

Examples:

b searching

b element
uniqueness b graph connectivity b graph acyclicity

primality
testing (finally proved in 2002)

__NP__* *(* nondeterministic polynomial*): class of decision problems
whose proposed solutions

A * nondeterministic
polynomial algorithm* is an abstract two-stage procedure that: b
generates a random string purported to solve the problem

b checks
whether this solution is correct in polynomial time

E.g.
Problem: Is a boolean expression in its conjunctive normal form (CNF)
satisfiable, i.e., are there values of its variables that makes it true?

This problem is in *NP*. Nondeterministic algorithm: b Guess truth assignment

b Substitute the values into the CNF formula to see
if it evaluates to true Example: (A | Â¬B | Â¬C) & (A | B) & (Â¬B | Â¬D |
E) & (Â¬D | Â¬E)

Truth
assignments:

__A B C D E
__0 0 0 0 0

. . .

1 1 1 1 1

Checking
phase: O(*n*)

**1. PROBLEMS ARE IN NP?**

b Hamiltonian
circuit existence

b Partition
problem: Is it possible to partition a set of *n* integers into two disjoint subsets with the same sum?

b Decision
versions of TSP, knapsack problem, graph coloring, and many other combinatorial
optimization problems. (Few exceptions include: MST, shortest paths)

b All the
problems in *P* can also be solved in
this manner (but no guessing is necessary), so we have:

* P inculde* *NP*

b Big
question: *P* = *NP* ?

*NP
*problems

**NP Hard problem:**

â€“ Most problems discussed are efficient (poly
time)

â€“ An interesting set of hard problems:
NP-complete.

â€¢
A decision problem *D* is __NP____-complete__
if itâ€˜s as hard as any problem in *NP*,
i.e., * D *is in*
NP*

*NP* is polynomial-time reducible to *D*

**Cookâ€™s theorem ****(1971):
CNF-sat is**** ***NP***-complete**

Other
NP-complete problems obtained through polynomial-time reductions from a known
NP-complete problem

Fig: NP
Problems

Examples:

TSP,
knapsack, partition, graph-coloring and hundreds of other problems of
combinatorial nature

v P = NP would imply that every problem in NP,
including all NP-complete problems, could be solved in polynomial time

v If a polynomial-time algorithm for just one
NP-complete problem is discovered,

then
every problem in NP can be solved in polynomial time, i.e., P = NP

v Most but not all researchers believe
that P NP , i.e. P is a proper subset of NP

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Analysis and Design of Algorithm : Traversals, Branch and Bound : Algorithm: Branch and Bound |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.