4.6. Estimation
of Computer
Time for First Feasible
Solution
127
print-out in Table 4.4 with Fig. 4.4. For example, the value of element (7, 2)
of matrix BOUND is equal to 152.60 million, and this corresponds exactly
to the value of the bound of node (7, 2), i.e., dam 7 in year 2, of Table 4.4.
Similarly, the value of element (0, 9) of the matrix, 150.44, corresponds
exactly to the value of the bound of node (0, 9).
The nodes of the tree to the right of line A-A of Fig. 4.4 correspond to
the nodes represented by the elements of the bound B it as it is constituted
after the first solution has been found. The algorithm then backtracks
until it finds a node with a bound higher than the current feasible solution
[node (0, 9) with a bound of 150.44 million]. Branching from node (0, 9)
gives a solution with a higher return (solution 2) than the first feasible
solution. The algorithm then backtracks to the node with the highest
bound (0, 3) greater than the solution at the time of scrutiny (solution 2)
and branches forward (in time) through the tree to discover whether the
return from the solution associated with node (0, 3) is in fact higher than
solution 2. The procedure of backtracking and tracking forward is repeated
until all the elements of matrix BOUND are zero.
4.6· Estimation of Computer Execution Time to Calculate
the First Feasible Solution
It would be highly desirable to be able to predict the total computation
time of the overall optimization algorithm for a water resources management problem, given the number of possible projects and the size of the
network configuration. Unfortunately, this is impossible because the total
number of solutions that must be examined cannot be predicted, a priori.
However, it is possible to forecast the calculation time needed to obtain
the first solution, because the number of computation steps is predictable.
The algorithm calls mainly on two subroutines (OLERSEN and BOUND)
to obtain the first solution, and knowing the total computing time for
these two subroutines gives a good estimate of the time to calculate first
feasible solution.
The main program (program DAMBLD) calls subroutine OLERSEN
(which in turns calls subroutine NETFLO) at least once for every year
and at the most twice. It calls OLERSEN twice in one year when the
possibility of a new dam being added in that year is under consideration
and once when no reservoir will be built in that year. The time needed for
running OLERSEN is very short because the initial conditions of the decision variables of the subroutine are close to the optimal values. Subroutine
of Computer
Time for First Feasible
Solution
127
print-out in Table 4.4 with Fig. 4.4. For example, the value of element (7, 2)
of matrix BOUND is equal to 152.60 million, and this corresponds exactly
to the value of the bound of node (7, 2), i.e., dam 7 in year 2, of Table 4.4.
Similarly, the value of element (0, 9) of the matrix, 150.44, corresponds
exactly to the value of the bound of node (0, 9).
The nodes of the tree to the right of line A-A of Fig. 4.4 correspond to
the nodes represented by the elements of the bound B it as it is constituted
after the first solution has been found. The algorithm then backtracks
until it finds a node with a bound higher than the current feasible solution
[node (0, 9) with a bound of 150.44 million]. Branching from node (0, 9)
gives a solution with a higher return (solution 2) than the first feasible
solution. The algorithm then backtracks to the node with the highest
bound (0, 3) greater than the solution at the time of scrutiny (solution 2)
and branches forward (in time) through the tree to discover whether the
return from the solution associated with node (0, 3) is in fact higher than
solution 2. The procedure of backtracking and tracking forward is repeated
until all the elements of matrix BOUND are zero.
4.6· Estimation of Computer Execution Time to Calculate
the First Feasible Solution
It would be highly desirable to be able to predict the total computation
time of the overall optimization algorithm for a water resources management problem, given the number of possible projects and the size of the
network configuration. Unfortunately, this is impossible because the total
number of solutions that must be examined cannot be predicted, a priori.
However, it is possible to forecast the calculation time needed to obtain
the first solution, because the number of computation steps is predictable.
The algorithm calls mainly on two subroutines (OLERSEN and BOUND)
to obtain the first solution, and knowing the total computing time for
these two subroutines gives a good estimate of the time to calculate first
feasible solution.
The main program (program DAMBLD) calls subroutine OLERSEN
(which in turns calls subroutine NETFLO) at least once for every year
and at the most twice. It calls OLERSEN twice in one year when the
possibility of a new dam being added in that year is under consideration
and once when no reservoir will be built in that year. The time needed for
running OLERSEN is very short because the initial conditions of the decision variables of the subroutine are close to the optimal values. Subroutine