74
3. A Procedure for Solving the Optimal Expansion
Problem
Problem j
/ω(χ)
?°?W >0
t = 1,2,...
This problem is similar to Problem 0 except that the specific constraints
and the total number of constraints included in each of the problems may
differ. The branches in the tree lead from Problem 0 to the subproblems
in the bounding sets. At any stage of the procedure the "leaves" on the tree
represent the current union of the sets of bounding problems.
If we let χ denote the best feasible solution that has been found at any
stage of the calculations, that is, /
(0) (x) is the largest value (for maximization) for any bounding problem j (with x
j
x), if/
(0) (x) > /
<Λ (χ
(Λ ), it is
clear that problem j can be removed from the set Ρ without affecting the
bounding condition B'. We say that there is associated with each node j of
the tree a bound f
(j) (x
U) )>
and that any leaf node of the tree whose bound
is greater than/
(0) (x) is active; if the bound is equal to or less than
f
m (x),
the leaf can be terminated^ that is, the bound need not be considered in
any further computations. The general procedure in branching and bounding is to develop the tree until every leaf can be terminated, and to work
out a suitable strategy so that not too many leaves will have to be decomposed into subproblems. Appropriate strategies include rules for deciding
which of the active bounding problems is to be selected for further branching, together with methods for deciding how to formulate the new bounding
problems.
3.2.2. Little's Branch and Bound
Algorithm
The previous section dealt with the general characteristics of the BBA.
This section describes Little's branch and bound algorithm (LBBA),
which was developed especially to solve the traveling salesman problem.
A legitimate initial lower bound (Li) for LBBA is the sum of the minimum
elements of the rows of the C matrix (whose elements are cy) plus the sum
of the minimum elements of the columns of the matrix after it has been
modified by subtracting from each element the value of the lowest element
of its own row. This process is called the row and column reduction of the
matrix. For the other nodes, the distance matrix C is modified to include
(or exclude) the arcs associated with the node, and the bounds are equal
to Li plus the value obtained by a row and column reduction.
Maximize
subject to
3. A Procedure for Solving the Optimal Expansion
Problem
Problem j
/ω(χ)
?°?W >0
t = 1,2,...
This problem is similar to Problem 0 except that the specific constraints
and the total number of constraints included in each of the problems may
differ. The branches in the tree lead from Problem 0 to the subproblems
in the bounding sets. At any stage of the procedure the "leaves" on the tree
represent the current union of the sets of bounding problems.
If we let χ denote the best feasible solution that has been found at any
stage of the calculations, that is, /
(0) (x) is the largest value (for maximization) for any bounding problem j (with x
j
x), if/
(0) (x) > /
<Λ (χ
(Λ ), it is
clear that problem j can be removed from the set Ρ without affecting the
bounding condition B'. We say that there is associated with each node j of
the tree a bound f
(j) (x
U) )>
and that any leaf node of the tree whose bound
is greater than/
(0) (x) is active; if the bound is equal to or less than
f
m (x),
the leaf can be terminated^ that is, the bound need not be considered in
any further computations. The general procedure in branching and bounding is to develop the tree until every leaf can be terminated, and to work
out a suitable strategy so that not too many leaves will have to be decomposed into subproblems. Appropriate strategies include rules for deciding
which of the active bounding problems is to be selected for further branching, together with methods for deciding how to formulate the new bounding
problems.
3.2.2. Little's Branch and Bound
Algorithm
The previous section dealt with the general characteristics of the BBA.
This section describes Little's branch and bound algorithm (LBBA),
which was developed especially to solve the traveling salesman problem.
A legitimate initial lower bound (Li) for LBBA is the sum of the minimum
elements of the rows of the C matrix (whose elements are cy) plus the sum
of the minimum elements of the columns of the matrix after it has been
modified by subtracting from each element the value of the lowest element
of its own row. This process is called the row and column reduction of the
matrix. For the other nodes, the distance matrix C is modified to include
(or exclude) the arcs associated with the node, and the bounds are equal
to Li plus the value obtained by a row and column reduction.
Maximize
subject to