3.2. The Capital Budgeting Problem {Problem
II)
75
Two subproblems are created at each branching step corresponding to
Xij = 0 and Xij = 1. At each branching step the arc (i, j) is chosen in such
a way that the problem corresponding to Xij = 0 will yield as large a bound
as possible. Since the algorithm will always first branch to a node having a
lower bound, this heuristic rule plus the rules mentioned in the following
paragraph will tend to make the first feasible solution the optimal one.
The branching technique is as follows:
1. At any stage of computation, the distance matrix will contain one or
more zeros. All the arcs corresponding to the zero values are candidate
arcs in the optimal solution.
2. Define a variable (0»y) that measures the change in the value of the
bound for not including arc (i 9 j) (whose c l7 = 0) in the final solution:
Bij = *i + fij
where a; is the second lowest element of row i, and jSy the second lowest
element of column j. Calculate θ„ .
3. For the next branching stage pick the arc (t, j) that corresponds to
the maximum value of 0y.
All the concepts of this section are illustrated in the following section,
where the LBBA is used to solve a simple traveling salesman problem.
3.2.3 Example of Application
of Little
9 s
Branch
and
Bound
Algorithm
(a)
PROBLEM STATEMENT
A traveling salesman must visit four cities designated 1, 2, 3, and 4 (see
Fig. 3.3). The 4X4 symmetric matrix C = [ci.. . c«]
T whose elements
are dj with the leading diagonal elements equal to infinity gives the distances (in miles) to be traveled between each pair of cites. What route
should the salesman choose to minimize the total distance traveled in visiting the four cities and returning to his original starting point?
To prohibit travel in any arc (i f j), the symbol cy = <*> is used. In
matrix 1 all the leading diagonal elements have been made equal to infinity
to avoid trips in the (i 9 i) arcs.
(b)
FIRST ROW AND COLUMN REDUCTION
A row and column reduction of matrix 1 gives a lower bound for node Pi
and yields matrix 2, as shown in Fig. 3.4. The lower bound for node Pi is
Li = 286.
II)
75
Two subproblems are created at each branching step corresponding to
Xij = 0 and Xij = 1. At each branching step the arc (i, j) is chosen in such
a way that the problem corresponding to Xij = 0 will yield as large a bound
as possible. Since the algorithm will always first branch to a node having a
lower bound, this heuristic rule plus the rules mentioned in the following
paragraph will tend to make the first feasible solution the optimal one.
The branching technique is as follows:
1. At any stage of computation, the distance matrix will contain one or
more zeros. All the arcs corresponding to the zero values are candidate
arcs in the optimal solution.
2. Define a variable (0»y) that measures the change in the value of the
bound for not including arc (i 9 j) (whose c l7 = 0) in the final solution:
Bij = *i + fij
where a; is the second lowest element of row i, and jSy the second lowest
element of column j. Calculate θ„ .
3. For the next branching stage pick the arc (t, j) that corresponds to
the maximum value of 0y.
All the concepts of this section are illustrated in the following section,
where the LBBA is used to solve a simple traveling salesman problem.
3.2.3 Example of Application
of Little
9 s
Branch
and
Bound
Algorithm
(a)
PROBLEM STATEMENT
A traveling salesman must visit four cities designated 1, 2, 3, and 4 (see
Fig. 3.3). The 4X4 symmetric matrix C = [ci.. . c«]
T whose elements
are dj with the leading diagonal elements equal to infinity gives the distances (in miles) to be traveled between each pair of cites. What route
should the salesman choose to minimize the total distance traveled in visiting the four cities and returning to his original starting point?
To prohibit travel in any arc (i f j), the symbol cy = <*> is used. In
matrix 1 all the leading diagonal elements have been made equal to infinity
to avoid trips in the (i 9 i) arcs.
(b)
FIRST ROW AND COLUMN REDUCTION
A row and column reduction of matrix 1 gives a lower bound for node Pi
and yields matrix 2, as shown in Fig. 3.4. The lower bound for node Pi is
Li = 286.