78
3. A Procedure for Solving the Optimal Expansion
Problem
3
4
Matrix 3: 2
4
oo
14
0
0 oo
7
0 22 oo
A row and column reduction reduces the value of the elements of column
3 in matrix 3 by 14, thereby giving a bound for arc (3, 2) = 286 + 14 =
300 and the new matrix 4; see Fig. 3.5.
(d)
SECOND BRANCHING SEQUENCE
In matrix 4 there are four elements that could be considered for the second arc of the branching sequence. Table 3.2 gives the value of 0y for each
of the elements.
Matrix 4:
»
0
0
0 oo
7
0
8 oo
Fig. 3.5 The solution tree after branching sequence 1. Underlined numbers are
bounds. Ordered pairs indicate whether or not arc is included in a particular branch.
Arc (1,3) is one of the set of highest values of θ a and will be chosen as
the second arc in the branching sequence. The bound for (1,3) is 300 + 8 =
308. The bound for (1,3) is calculated (1) by removing row 1 and column 3
from matrix 4 to give matrix 5, (2) making element (2, 1) equal to oo to
avoid the sub-tour 1-3-2-1 and (3) carrying out a row and column reduction
of matrix 5.
1
4
2
Matrix 5:
4
oo
7
0 oo