Home | | **Operations Research An Introduction** | | **Resource Management Techniques** | B&B Solution Algorithm - Traveling Salesperson Problem (TSP)

The idea of the B&B algorithm is to start with the optimum solution of the associated assignment problem.

**B&B Solution Algorithm**

The idea of the B&B algorithm is to start with the optimum solution
of the associated assignment problem. If the
solution is a tour, the process ends. Otherwise, restrictions are imposed to
remove the subtours. This can be achieved by creating as many branch-es as the
number of x_{ij} variables associated with one of the subtours. Each
branch will correspond to setting one of the variables of the subtour equal to
zero (recall that all the variables associated with a subtour equal 1). The
solution of the resulting assign-ment problem mayor may not produce a tour. If it does, we use its objective value as an upper bound on the true
minimum tour length. If it does not, further branching
is necessary, again creating as many branches as the number of variables in one
of the subtours. The process continues until all unexplored subproblems have
been fathomed, either by producing a better (smaller) *upper bound* or because there is evidence that the subproblem cannot
produce a better solution. The optimum tour is the one associ-ated with the
best upper bound.

The following example provides the details of the TSP B&B algorithm.

**Example 9.3-4**

Consider
the following 5-city TSP problem:

We start
by solving the associated assignment, which yields the following solution:

*z *=* *15,* *(x_{13}* *=* x _{31} *=

This
solution yields two subtours: (1-3-1) and (2-5-4-2), as shown at node 1 in
Figure 9.13. The associated total distance is *z* = 15, which provides a lower bound on the optimal length of the
5-city tour.

A
straightforward way to determine an upper bound is to select any tour and use
its length as an upper bound estimate. For example, the tour 1-2-3-4-5-1
(selected totally arbitrarily) has a total length of 10 + 5 + 7 + 4 + 3 = 29.
Alternatively, a better upper bound can be found by applying the heuristic of
Section 9.3.1. For the moment, we will use the upper bound of length 29 to
apply the B&B algorithm. Later, we use the "improved" upper bound
obtained by the heuristic to demonstrate its impact on the search tree.

The
computed lower and upper bounds indicate that the optimum tour length lies in
range (15, 29). A solution that yields a tour length larger than (or equal to)
29 is discarded as nonpromising.

To
eliminate the subtours at node **1,** we need to "disrupt"
its loop by forcing its member variables, *x _{ij},*
to be zero. Subtour 1-3-1 is disrupted if we impose the restriction x

Targeting
subtour (1-3-1), two branches x_{13} = 0 and *x _{31}* = 0 are created at node 1. The associated
assignment problems are constructed by removing the row and column associated
with the zero variable, which makes the assignment problem smaller. Another way
to achieve the same result is to leave the size of the assignment problem
unchanged and simply assign an infinite distance to the branching variable. For
example, the assignment problem associated with x

In Figure
9.13, we arbitrarily start by solving the subproblem associated with x_{13}
= 0 by setting d_{l3} = ¥, Node 2
gives the solution *z* = 17 but
continues to produce the subtours (2-5-2) and (1-4-3-1). Repeating the
procedure we applied at node 1 gives rise to two branches: *x _{25}* = 0 and x

We now
have three unexplored subproblems, one from node 1 and two from node 2, and we
are free to investigate any of them at this point. Arbitrarily exploring the
subproblem associated with *x _{25}* = 0 from
node 2, we set d

We now
have two unexplored subproblems. Selecting the subproblem 4 for exploration, we
set d_{l3} = ¥ and *d _{52}* = ¥ in the

Only
subproblem 5 remains unexplored. Substituting *d** _{31}* = ¥ in the

There are
no remaining unfathomed nodes, which completes the search tree. The optimal
tour is the one associated with the current upper bound: 1-3-4-2-5-1 with length
16 miles.

**Remarks. **The solution of the example
reveals two points:

1.
Although the search sequence 1 -> 2 -> 3 -> 4 -> 5 was selected
deliberately to demonstrate the mechanics of the B&B algorithm and the
updating of its upper bound, we generally have no way of predicting which
sequence should be adopted to improve the efficiency of the search. Some rules
of thumb can be of help. For example, at a given node we can start with the
branch associated with the *largest d** _{ij}* among all
the created branches. By canceling the tour leg with the largest

2. The
B&B should be applied in conjunction with the heuristic in Section 9.3.1.
The heuristic provides a "good" upper bound which can be used to
fathom nodes in the search tree. In the present example, the heuristic yields
the tour 1-3-4-2-5-1 with a length of 16 distance units.

**AMPl
Moment**

Interactive
AMPL commands are ideal for the implementation of the TSP B&B algorithm
using the general assignment model (file ampIAssignment.txt). The following
table summarizes the AMPL commands needed to create the B&B tree in Figure
9.13 (Example 9.3-4):

**PROBLEM SET 9.3C**

1. Solve Example 9.3-3 using subtour 2-5-4-2 to start the branching
process at node 1, using the following sequences for exploring the nodes.

a) Explore all the
subproblems horizontally from left to right in each tier before preceeding to
the next tier.

b) Follow each path vertically from node 1 until it
ends with a fathomed node.

*2. Solve Problem 1, Set 9.3a using B&B.

3. Solve Problem 2, Set 9.3a using B&B.

4. Solve Problem 3, Set 9.3a using B&B.

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

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.