Citation
Optimal water supply capacity expansion using objective-space dynamic programming

Material Information

Title:
Optimal water supply capacity expansion using objective-space dynamic programming
Creator:
Sullivan, Gregory Kevin
Publication Date:
Language:
English
Physical Description:
viii, 77 leaves : illustrations ; 29 cm

Subjects

Subjects / Keywords:
Water-supply engineering ( lcsh )
Water-supply engineering -- Colorado -- Denver Metropolitan Area ( lcsh )
Dynamic programming ( lcsh )
Dynamic programming ( fast )
Water-supply engineering ( fast )
Colorado -- Denver Metropolitan Area ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 74-77).
General Note:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Department of Civil Engineering.
Statement of Responsibility:
Gregory Kevin Sullivan.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
22839394 ( OCLC )
ocm22839394
Classification:
LD1190.E53 1990m .S83 ( lcc )

Full Text
OPTIMAL WATER SUPPLY CAPACITY EXPANSION
USING OBJECTIVE-SPACE DYNAMIC PROGRAMMING
by
Gregory Kevin Sullivan
B.S., Colorado State University, 1985
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado in partial fulfillment
of the requirements for the degree of
Master of Science
Department of Civil Engineering
1990


This thesis for the Master of Science
degree by
Gregory Kevin Sullivan
has been approved for the
Department of
Civil Engineering
by
Date


civil Engineering)
Sullivan, Gregory Kevin (M.S.,
Optimal Water Supply Capacity Expansion Using
Objective-Space Dynamic Programming
Thesis directed by Associate Professor Lynn E. Johnson
Optimal water supply capacity expansion is the
sequencing and scheduling of water supply projects over
a finite planning period in a manner which meets
forecast water demand and other constraints at minimum
cost. This thesis describes application of a recently
developed optimization technique known as objective-
space dynamic programming (OSDP) to the water supply
capacity expansion problem. OSDP is an alternative
formulation of dynamic programming which facilitates
computationally manageable solutions of highly
dimensional problems by optimizing in the one-
dimensional objective-space. Application of
traditional state-space dynamic programming methods to
highly dimensional problems has proven difficult due to
the "curse of dimensionality." The OSDP procedure was
implemented on a microcomputer using a generalized
dynamic programming software package known as CSUDP. A
case study of the water supply capacity expansion
problem faced by water providers for the metropolitan
area of Denver, Colorado, is presented to demonstrate


application of the OSDP method. The study considered
implementation of 25 potential water supply projects
over a 50-year planning horizon. A discussion of the
results of the application is provided including
cautions and recommendations for use of the OSDP
method.
The form and content of this abstract are approved. I
recommend its publication.
Signed___________________________
Lynn E. Johnson
iv


CONTENTS
Figures........................................ vii
Tables.........................................viii
CHAPTER
1. INTRODUCTION .................................... 1
2. REVIEW OF THE LITERATURE......................... 2
Analytical Techniques .......................... 2
Direct Enumeration ............................. 3
Integer Programming ............................ 4
Dynamic Programming ............................ 5
Objective-Space Dynamic Programming ........... 16
3. PROBLEM DEFINITION ............................. 18
Mathematical Problem Statement ............... 20
Model Implementation..........................2 6
4. MODEL APPLICATION TO DENVER
WATER SUPPLY CAPACITY EXPANSION ................ 31
Input Data......................................32
Forecast Water Demand ..................... 32
Projects....................................34
Interest Rate...............................39
Objective-Space Discretization ............ 39
Results.........................................40
5. DISCUSSION.......................................49
Scheduling Trends ............................. 49
Potential Difficulties ........................ 50
Discretization Interval Effects ........... 50


Solution Non-Uniqueness ................... 56
Project Linkages .......................... 57
Model Execution Times...........................59
Model Limitations...............................60
Conservation Measures ..................... 60
Multiple Objectives ....................... 61
6. CONCLUSION..............................63
APPENDIX
A. COST AND YIELD TRAJECTORIES FOR $20
MILLION, $10 MILLION,$5 MILLION AND
$2 MILLION DISCRETIZATION INTERVALS ... 65
GLOSSARY...........................................70
BIBLIOGRAPHY ........................................ 74
Vi


FIGURES
Figure
3.1. Example capacity expansion cost and
yield trajectories........................23
3.2. Model execution flowchart ................ 30
4.1. Forecast Denver metropolitan area
water demand..............................33
4.2. Final discounted investment costs for
various objective-space discretization
intervals.................................42
4.3. Investment cost trajectories computed
for various objective-space
discretization intervals..................43
4.4. Water system yield trajectories
computed for various objective-space
discretization intervals..................44
4.5. Investment cost and system yield
trajectories for $1 million objective-
space discretization interval ........... 45
4.6. Project implementation schedule for $1
million objective-space discretization
interval............................... 48
5.1. Investment cost trajectories for
splicing example..........................54
A.1. Investment cost and system yield
trajectories for $20 million objective-
space discretization interval ........... 66
A.2. Investment cost and system yield
trajectories for $10 million objective-
space discretization interval ........... 67
A.3. Investment cost and system yield
trajectories for $5 million objective-
space discretization interval ........... 68
A.4. Investment cost and system yield
trajectories for $2 million objective-
space discretization interval ........... 69
vii


TABLES
Table
4.1. Potential Water Projects Grouped by
Project Type. ;..........................35
4.2. Potential Water Projects Listed In
Order of Capital Cost......................36
4.3. Project Linkage Matrix.....................38
4.4. Projects Resulting in Optimal
Discounted Investment Cost............... 47
viii


CHAPTER 1
INTRODUCTION
Water supply expansion is becoming increasingly
difficult for growing municipalities as inexpensive and
readily developed sources become scarcer. Cities are
forced to look toward alternative water sources as
nearby surface and underground sources become over-
appropriated or otherwise unusable as a result of water
quality problems. Alternative water sources are
typically more expensive due to increased construction
costs, greater distances water must be transported
and/or greater depths from which water must be pumped.
Added to this are costs associated with conforming to
complex governmental permitting processes and the
relatively new expenses associated with environmental
impact mitigation. Finally, reduced monetary support
from the federal government has placed additional
financial burden on local public and private water
suppliers. These factors have increased the "stakes"
of water supply planning and have broadened interest in
optimizing the expansion of water supply systems.


CHAPTER 2
REVIEW OF THE LITERATURE
The capacity expansion problem addressed herein
concerns the optimal scheduling of water supply
projects with fixed capacity over a long-term planning
horizon in order to meet forecast water demand while
minimizing costs. This is known as the "capacitated"
expansion problem. The "uncapacitated" problem
requires selecting project size as well as schedule.
Several techniques have been described in the
literature to deal with the capacitated and
uncapacitated water supply expansion problems including
analytical techniques, direct enumeration, integer
programming and heuristic techniques, and most often,
dynamic programming.
Analytical Techniques
Analytical solution techniques exploit functional
relationships between cost, demand and supply
variables. If these relationships are continuous and
can be expressed in relatively simplistic mathematical
terms, it may be possible to derive analytical
expressions for optimal capacity expansion. Scarato


(1969) utilized differential calculus to develop
expansion schedules for water supply system components.
The authors approach depended on the assumption of
linearly increasing water demand and is applicable only
to incremental capacity expansion and timing of a
particular project or process. It is not capable of
choosing between alternative projects.
Direct Enumeration
Direct enumeration is a "brute force" procedure
which examines all permutations of the set of project
alternatives based on some objective criteria such as
minimizing costs. Assuming a situation in which all
projects under consideration need not be constructed to
meet demand over some finite planning period, the
number of possible project sequences which would have
to be examined by direct enumeration may be computed as
follows:
n
NS = V1 nl
Z_, (n-r) !
r=l
where NS = number of possible project
sequences
n = total number of projects considered
Thus for a seemingly modest number of ten
projects, almost 10 million sequences would have to be
3


analyzed. This technique becomes clearly unmanageable
for real-world planning situations in which more than
ten possible projects might be considered.
Integer Programming
Branch-and-bound techniques of integer programming
have been utilized to reduce the computational
magnitude of the direct enumeration approach. Branch-
and-bound techniques divide (branch) the permutation
set of project sequences into subsets on the basis of
specified heuristics, or rules of thumb. By
establishing lower or upper limits (bounds) on the
subsets it is possible to eliminate entire project
subsets without specifically analyzing their contents.
For example, in a minimization problem, if Set 1 has an
upper bound which is less than the lower bound of Set
2, then all of Set 2 may be eliminated.
Ford (1986) employed mixed-integer linear
programming using a branch-and-bound algorithm to
select and size disposal sites for a dredged-material
disposal system on the Delaware River. This problem
parallels the selection and sizing of water supply
projects. The branching heuristic involved computing
the disposal volume per unit cost available at each
site.
4


Kim and Yeh (1986) solved the uncapacitated
expansion problem using a univariate direct search
procedure to proceed through the permutation tree of
possible solutions. A shortest-path dynamic
programming algorithm based on minimizing cost was used
as the return function to perform the branching and
bounding operations. Following identification of the
best project scheduling sequence, project capacities
were refined with a non-linear programing technique.
The method was demonstrated by solving a hypothetical
problem and comparing the results to those obtained by
other solution techniques.
Other relevant applications of integer programming
techniques were described by Akileswaran, Morin and
Meier (1979); Ball, Bialas and Loucks (1978); Bickel
(1978); Brill and Nakamura (1978); Efroymson and Ray
(1966); Marks and Liebman (1970); Morin (1975);
Nakamura and Brill (1979); and O'Laoghaire and
Himmelblau (1972).
Dynamic Programming
The solution algorithm used most often in the
literature to solve the water supply capacity expansion
problem has been dynamic programming. This technique
is well suited to solution of sequential decision
5


problems, such as capacity expansion scheduling, due to
its inherent capability of reducing a multi-stage
problem to a sequence of single-stage problems.
Dynamic programming is capable of explicitly
considering non-linear objective functions and
constraints such as those associated with water demand
forecasts, unlike other solution algorithms which may
require linearization of such functions. Increasing
the number of stages in a dynamic programming
application results in an approximately linear increase
in computational effort required to solve the problem
as opposed to the geometric increase which occurs with
most other procedures. Constraints on the decision-
space or state-space, such as contingencies and mutual
exclusivity of water projects, actually enhance the
efficiency of a dynamic programming algorithm by
reducing the number of system states which must be
examined. On the other hand, large numbers of
constraints tend to increase the computational burden
associated with other optimization techniques.
The principal drawback to dynamic programming is
the large computer memory requirement for problems
having multiple state variables. This difficulty has
been termed the "curse of dimensionality" (Bellman
1957). Fortunately, techniques such as the one applied
6


in this paper have been developed to reduce the impact
of this obstacle. A complete description of procedures
and characteristics of dynamic programming may be found
in Cooper and Cooper (1981) and Gluss (1972).
The first application of dynamic programming to
the capacity expansion problem was by Butcher, Haimes
and Hall (1969) who presented a solution to the
sequencing problem in which the water requirement at
the end of the study period is equal to the sum of the
individual project capacities. The authors specified
the capacity of the water supply system as the dynamic
programming state-space, with the decision variable
being the amount of capacity added to the system. The
number of projects considered defined the dynamic
programming stage (i.e., stage 1 considered building
only one project, stage 2 considered two projects,
etc.). The objective function consisted of minimizing
discounted capital construction costs. This dynamic
programming formulation is considered in the literature
as the "classical" or "conventional" approach (Braga et
al. 1985 and Morin 1973). The procedure was
demonstrated by a simple example involving four water
supply projects of fixed capacity.
Morin and Esogbue (1971) provided two improvements
to the Butcher, Haimes and Hall (1969) method. The
7


first improvement entailed extending the original
classical dynamic programming formulation to the more
general scheduling problem in which the sum of the
project capacities exceeds the final water demand. The
other addition involved application of an imbedded
state-space approach. This strategy restricts the
state-space to permutations of the project capacities.
In other words, instead of defining the state-space as
some equally discretized grid of project capacities,
the authors structured the state-space to include only
possible cumulative project capacities. The result is
a more computationally efficient algorithm which was
demonstrated by simple example.
Morin (1973) pointed out the classical dynamic
programming approach described by Butcher, Haimes and
Hall (1969) could fail to reach the optimal solution in
situations when the discretization interval is not
small enough, or certain yield levels ai'e attainable by
more than one combination of projects. This was
reasoned to be additional motivation to use the
imbedded state-space approach.
Morin and Esogbue (1974) offered a theorem and
proof concerning the optimal sequencing of projects
having like capacities or costs as an aid to reducing,
8


in some circumstances, the number of possible system
states which must be evaluated.
Erlenkotter (1973b) presented an alternative to
the classical dynamic programming approach. The new
formulation defined the state-space by means of a
binary state vector in which the vector dimensionality
corresponds to the number of projects considered. The
binary nature of the variable indicates it may take on
values of only 0 or 1 where 1 indicates a project has
been constructed and 0 indicates it has not. Dynamic
programming stages are specified as time increments
over the planning horizon. System capacity is handled
as a constraint which requires capacity to exceed water
demand. The procedure was presented as a backward
dynamic programming formulation. The binary state-
space approach was adopted by most subsequent
applications of dynamic programming to the capacity
expansion problem.
Erlenkotter (1973a) extended the binary state-
space approach to scheduling hydroelectric projects
with interdependent power yields. The
interdependencies were assumed to be a function of only
the number of upstream projects.
Recognizing project interdependencies also exist
in most multi-reservoir water supply systems, Becker
9


and Yeh (1974a) elaborated an integrated dynamic
programming and simulation model for selection and
sizing of reservoir projects. The authors used a
binary state-space dynamic programming algorithm to
schedule and select the optimal firm yield of each
reservoir project. The inner problem of the technique
consisted of simulating the operation of the reservoir
projects selected at each stage in conjunction with the
rest of the system. The capacity of each reservoir
selected was varied in repeated application of the
simulation routine until its firm yield, based on a
historical low flow sequence and rational operating
rules, approximated the desired reservoir firm yield.
The integrated solution procedure explicitly recognized
that it is reservoir capacity, not firm yield, which is
actually sized and built. Because the simulated yield
of the system was dependent on previously constructed
projects, the problem was necessarily constructed as
forward-looking dynamic program. The procedure was
applied to a proposed six-reservoir system in the Eel
River Basin in northern California.
Becker and Yeh (1974b) later modified their
original model to consider dual objectives of water
supply and hydropower. In addition, the simulation
10


model used to select reservoir size was replaced with a
more efficient linear programming model.
Braga et al. (1985) applied a methodology similar
to Becker and Yeh (1974a) for optimal capacity
expansion of the water supply system of Sao Paulo,
Brazil. The authors allowed resizing of reservoirs
selected at earlier stages in the analysis on the basis
of the geography and implied logical construction
sequence of portions of the system.
Erlenkotter (1975) pointed out the methodology
espoused by Becker and Yeh (1974a) for interdependent
projects may not result in optimal project capacities
and schedule due to implicit omission at later stages
of portions of the capacity state-space considered and
eliminated in earlier stages. This omission is
apparently the result of incorporating both project
scale decisions and project interdependencies in the
same model.
Moore and Yeh (1980) adapted the original Becker
and Yeh (1974a) model for improved analysis of the
economics of reservoir water supply capacity expansion.
This was accomplished by modifying the objective
function to maximize net economic benefits, defined as
customer willingness to pay less capital project costs.
The model also allowed water demand to vary with time
11


as a function of changing water prices. The procedure
was demonstrated on the proposed Eel River reservoir
system described by Becker and Yeh (1974a)
Martin (1987) described another integrated
optimization model for water supply capacity expansion.
His model used a binary state-space dynamic programming
model to select and size various water projects to
minimize given construction and fixed operating costs,
and assumed variable operating costs. Following
selection of the original project implementation
schedule, a network optimization model was executed to
compute true variable operating costs resulting from
the particular set of projects implemented. The
dynamic programming model was then executed again using
the computed variable operating costs to improve
project scheduling and sizing. This procedure was
repeated in an iterative fashion until the variable
operating costs converged. The method was applied to
schedule expansion of the San Antonio, Texas, water
supply system over four 10-year stages. The model
considered six possible reservoir projects of fixed
size, six variable-capacity pipelines and one
groundwater project.
Rubinstein and Ortolano (1984) applied dynamic
programming to the solution of a dual-objective
12


capacity expansion problem. The two objectives
included minimization of project construction costs and
minimization of the "cost of coping" with water supply
shortages (i.e., cost of implementing emergency
projects and monetary losses associated with water
shortages). The cost of coping was incorporated in the
model using an expected value (stochastic) procedure
involving (1) the probability of having various
supplies available at the beginning of a stage, (2)
conditional probabilities relating water supplies
available at the beginning and end of the current
stage, and (3) the assumed cost of coping at the end of
the period given various water supplies. In addition
to constructing water supply projects, the model also
allowed implementation of water conservation schemes as
a means of keeping demand below available supply. The
dual objectives were combined into a single objective
by a weighting procedure which eased the computational
difficulties associated with a multiple objective
problem. A non-inferior set of solutions was generated
by varying the weights given to each objective using a
Non-Inferior Set Estimation (NISE) procedure described
by Cohon (1978). The procedure enables decision-
makers to evaluate the resulting solution set to better
13


understand tradeoffs between the two competing
objectives.
Bogle and O'Sullivan (1979) described an
application of stochastic dynamic programming to the
particular situation of minimizing the cost of
sequencing expansion of a supplemental water source to
augment a primary reservoir water supply. The
probability distribution associated with various
reservoir storage states was derived using a simulation
model assuming rational reservoir operating rules. The
expected value of the reservoir storage at the
beginning of each stage was incorporated in a forward
dynamic programming algorithm which computed the
optimal system expansion. The traditional binary
state-space algorithm was modified to reflect the
persistence or lasting effects of previous reservoir
states on future stages. The authors acknowledged this
linking of dynamic programming stages may not achieve
the optimal solution. A hypothetical example was used
to demonstrate the procedure.
An incremental dynamic programming approach was
use by Kolo and Haimes (1977) to schedule water supply
projects to meet water demands for fresh water supply,
irrigation and power generation. The incremental
approach is characterized by application of a dynamic
14


programing model over a coarse discretization of the
state-space to identify an initial solution. The
solution is then refined by repeated execution of the
model over an increasingly finer state-space
discretization in the vicinity of the initial solution
path until the optimal solution is found. The
objective function considered capital construction, and
fixed and variable operating costs to maximize net
economic returns. The model was executed for various
levels of assumed water and power prices. The results
of the optimization procedure were used as input to a
regression model to derive a relationship between net
returns and prices. This relationship was subsequently
solved to determine optimum water and power prices.
The applications of integer programming and
dynamic programming discussed thus far have been shown
to be effective in dealing with a capacity expansion
problem involving a modest number of potential
projects; usually less than ten. However,
computational difficulties involving primarily computer
storage limitations and excessive execution times
discourage their application to scheduling problems
involving greater numbers of projects.
15


Objective-Space Dynamic Programming
Fontane and Labadie (1981) introduced a new
procedure identified as objective-space dynamic
programming (OSDP) in which the optimal solution to a
sequential decision process is determined by dynamic
programming in the one-dimensional objective-space
rather than the multi-dimensional state-space. The
authors applied OSDP to determine optimal release
strategies to minimize temperature deviations of water
released from various reservoir depths.
Labadie and Fontane (1989) presented a
mathematical proof demonstrating global optimality of
solutions obtained by OSDP provided certain uniqueness
requirements of the objective-space and state-space are
obeyed. The authors reported the technique has been
successfully applied to a problem involving a state-
space with as many as 30 dimensions.
Fontane et al. (1989) described use of OSDP to
optimize implementation of salinity control projects on
the Colorado River with the objective of minimizing
costs. The problem consisted of scheduling salinity
control projects to meet salinity control targets over
a 22-year planning period. Seventeen possible projects
were available for implementation with each project
16


having a fixed independent salinity reduction effect.
The model has been successfully implemented by the
U. s. Bureau of Reclamation as part of its annual
evaluation of the Colorado River salinity control
program. Reportedly, the number of projects considered
by the model now numbers twenty-four.
The successful implementation of OSDP for solution
of problems having high dimensionality prompted
application of the technique to the water supply
capacity expansion problem. This paper describes such
application and presents of the results of the
technique applied to optimize proposed expansion of the
water supply system of the Denver metropolitan area.
17


CHAPTER 3
PROBLEM DEFINITION
The OSDP model described in this paper is capable
of selecting and scheduling water supply projects by
making several simplifying assumptions regarding model
objectives, project attributes and interrelationships,
and water demand forecasts. These assumptions are
discussed as follows.
The optimization criteria, or objective function,
is based solely on minimizing discounted project
construction and operating costs incurred over a finite
planning period. Other costs, such as those associated
with expanding the water distribution system, are not
considered. Non-economic objectives commonly
associated with water projects including recreation,
power generation and environmental impacts, are also
not considered in the model.
Project water yields are considered in terms of
the estimated annual water supply provided during an
extreme drought period, or firm yield. Project firm
yields must be estimated using a simulation model or
some other procedure prior to applying the OSDP model
to schedule the projects. Project yield


interdependencies are included assuming a simple
conditional relationship exists between the yield of a
project and projects constructed at previous stages.
The model allows the user to specify the
planning/construction time which must elapse after
selecting a project before it will yield water.
Construction costs are assumed spread equally over the
project implementation period. Upon completion of a
project, operating costs are incurred for the remainder
of the study period. Mutual exclusivity between
projects and project contingencies may also be
incorporated into the analysis.
Water demands are handled as a constraint by
requiring the firm yield of the water supply system to
equal or exceed forecast water requirements during each
year of the planning period with no water shortages
allowed. Projects must be completed prior to yielding
any water. Forecast water demand must be monotonically
increasing with time.
Finally, all project variables are assumed
deterministic. Variations in water demand forecasts,
project yields, costs, interest rates, etc., can only
be evaluated by multiple model runs.
19


Mathematical Problem Statement
The OSDP approach requires solution of an outer
and an inner problem. The outer problem consists of
optimizing over a set of discretized target annual
expenditures to identify a cost trajectory which
minimizes total discounted project construction and
operating costs over a finite planning period. The
inner problem identifies the set of projects to be
implemented which collectively, in conjunction with
projects previously constructed, results in
expenditures closest to the target cost while
delivering a firm annual yield greater than the
forecast water demand, and meeting other constraints.
The problem may be expressed in mathematical terms
by considering the following definitions: uA = new
project vector describing projects initiated in the
current stage, i; x* = project status vector with value
between zero and one indicating which projects have
been selected through the current stage, and their
degree of completion; Ci = the target investment cost
for the current stage, i, with lower bound, Bhl, and
upper bound, BUi,- f^uj = the costs incurred during
the current stage resulting from selection of new
projects; Vj [ x^, (Q.j ) ] = continued construction
costs or operating costs for projects previously
20


selected; F1(C1) = total costs through the current
stage resulting from optimal project selection which
minimally exceeds the cost target; y = net project
water yield comprised of the base yield in the absence
of other projects, and yield modifications
(additions or subtractions), m* [ x 1_l (C^J ], arising
from project interdependencies; Yt (C, ) = total optimal
system yield resulting from projects constructed to
meet a particular cost target; [ x^ (Q^ ) ] = the
set of feasible projects available for selection during
the current stage.
The general recursion relationship for the OSDP
algorithm assuming a forward dynamic programming
approach may be stated as follows:
F, (Q) = min { Vi [ xJQ.J ] + Fw (Q., ) + f .(u, ) >
Q-i
subject to the following constraints applied at each
stage:
1. The sum of all construction and operating costs
through the current stage must exceed the specified
cost target.
VA [ Xi.jCi.J ] + Fi.^Ci.,) + min f4 (Ui) > Ci
2. Cost targets remain within user specified bounds.
BLt < Q < BUi
21


Solution of the inner problem requires selection
of projects which meet the cost target and obey other
monetary and physical system constraints. The inner
problem objective function is stated as follows:
min f j(Ui)
subject to the following:
1. Cost target constraint (same as outer problem).
V, [ Xu(Q_! ) ] + F i.i (Ch) + min f4 U ) > > Q
2. Project status is a function solely of its status
at the previous stage and decisions made at the current
stage.
x, = g [ (Ci.j u4 ]
3. Total system yield must equal or exceed demand.
Yi (Ui ) + ym(Cm) > D '
4. Project yields are a function of the project base
yield and projects previously implemented.
y, (u ) = zt + m, [ xt., (Cl, ) ]
5. Projects may not be repeated.
Ui X M (Cm) = 0
6. Selected projects must be feasible with respect to
mutual exclusivity and contingency constraints.
u, e S [ xm(Q., ) ]
A description of the underlying premise for the
model is provided with reference to Figure 3.1. Assume
selection of a particular sequence of projects results
22


Discounted Project Costs (million $)
OPTIMAL DISCOUNTED COST TRAJECTORY
OSDP Exomple
OPTIMAL SYSTEM YIELD TRAJECTORY
OSOP exomple
Figure 3.1. Example capacity expansion cost and yield
trajectories.
23


in the system yield increasing with time as shown at
the bottom of Figure 3.1. Assume further this
particular project sequence results in the optimal or
minimum final discounted cost for all possible
combinations of project schedules. If this is the
case, the cost trajectory displayed at the top of
Figure 3.1 which results in the optimal final cost is
also optimal. Assuming an exclusive relationship
between the optimal cost trajectory and its
corresponding project implementation schedule
(uniqueness requirement described by Labadie and
Fontane [1989]), the OSDP model need only identify the
optimal cost trajectory to simultaneously identify the
optimal project implementation schedule. A description
of how the OSDP model identifies the optimal cost
trajectory follows.
The OSDP model utilized herein is similar to that
described by Fontane et al. (1989) for selecting
salinity reduction projects on the Colorado River.
Initial project states and costs are zero (x0 = 0 and
C0 = 0). During the first stage, and each stage
thereafter, the outer problem model systematically
considers a range of target investment levels. The
investment targets are defined by upper and lower
cumulative cost boundaries and by a user specified
24


objective-space discretization interval. The inner
model identifies the project or combination of projects
with total costs which, when added to costs incurred at
previous stages, equal or minimally exceed the cost
target. The optimal actual total accumulated system
costs through the current stage become the base for
which projects are added to meet cost targets in the
next stage.
The project selection (inner) model component is
formulated to choose projects to meet the cost target
using a simple direct search procedure. The procedure
first tabulates (1) continued construction costs for
projects previously selected but not completed, and (2)
operational costs for all completed projects. If those
costs are sufficient to meet the cost target, then no
additional projects are selected during that stage.
Otherwise, feasible projects are examined singly, and
in combinations of two, to identify the projects whose
costs come closest to meeting the cost target. In the
event one or two projects cannot meet the cost target,
projects are added in order of increasing cost until
the target is met.
After determining which projects, if any, need be
implemented to meet the cost target, the model
evaluates the water demand constraint. Investment
25


policies which do not satisfy water demand during the
current stage are assigned a penalty cost. This allows
infeasible solutions to be carried through the
computational procedure but not be selected as optimal.
Upon completing the final stage, the model has
computed total actual system costs for a range of final
system cost targets. Each of these final costs was
achieved by a particular cost trajectory. The
trajectory which produces the minimum final cost must
be the optimal investment policy. The optimal project
implementation schedule is determined by a traceback
procedure through the stored optimal investment policy.
Model Implementation
The OSDP procedure was implemented on a
microcomputer using a previously developed generalized
dynamic programming code identified as CSUDP (Labadie
1990). CSUDP consists of a Fortran-based computational
core which is adapted to a particular problem through
inclusion of problem specific subroutines which define
the dynamic programming objective function, state
transformation, and problem data. The program was
modified slightly by its author to facilitate
application of the OSDP approach.
26


Execution of CSUDP in the objective-space mode
requires preparation of an additional subroutine which
performs state-space operations (project selection) to
meet objective-space targets (cost targets) identified
by the CSUDP core. Each subroutine is compiled and
linked to the CSUDP core to form a single executable
program. Problem data including project costs, yields
and construction periods; forecast water demands and
the discount rate are input to the program via ASCII
data files. This structure allows modification of the
problem without recompiling the subroutines for each
program run.
Due to program variable storage limitations, CSUDP
stores only the optimal paths to each cost target
between adjacent stages during the initial progression
through the problem stages. After identifying the
optimal value of the objective function at the final
stage, CSUDP must trace backward through the problem
stages to identify the optimal path.
In a conventional dynamic programming application,
CSUDP evaluates the objective function during the
traceback procedure to provide objective function
values at each stage by solving the problem in reverse
(i.e. last stage to first stage).
27


Evaluation of the objective function in a backward
mode is extremely cumbersome in an OSDP application due
to the presence of an additional subroutine for the
inner problem. The capacity expansion application
requires determination of objective function "values
at each stage on the optimal trajectory to provide
output regarding actual costs, system yield and project
status.
Rather than perform extensive modifications to the
OSDP subroutines to correctly evaluate the objective
function during traceback, a simple Fortran program was
created to extract the optimal cost target for each
stage from the CSUDP output file. The EXTRACT program
creates an input file identical to the original input
file with the exception the upper and lower bounds on
the objective-space for each stage are set equal to the
optimal cost target for that stage identified in the
initial run. The OSDP program is executed again with
the new input file which forces the program to evaluate
only the optimal cost trajectory. During the second
run, the optimal project implementation schedule and
resulting investment costs and system yield are written
to a final output file. This file is then imported to
a spreadsheet program where the output may be
graphically displayed or printed. A flowchart
28


summarizing the model execution procedures is shown in
Figure 3.2.
29


Figure 3.2. Model execution flowchart.
30


CHAPTER 4
MODEL APPLICATION TO DENVER
WATER SUPPLY CAPACITY EXPANSION
The Denver metropolitan area has experienced
generally rapid growth over the past several decades.
In order to meet the municipal water demand generated
by this growth, numerous water suppliers have developed
supply sources ranging from appropriations of nearby
streams, rivers and underground aquifers, to western
slope sources which are delivered under the continental
divide. Current projections indicate without
additional sources, the metropolitan area water supply
will be insufficient to meet projected demand past the
mid-1990's. Supplemental water supplies must be
developed to meet projected demand into the 21st
century.
In the early 1980's metropolitan area water
suppliers, led by the Denver Water Board, began the
process of quantifying additional water needs and
identifying alternative water sources. A system-wide
Environmental Impact Statement (EIS) was prepared in
accordance with the National Environmental Policy Act
(NEPA) of 1969 which mandates such a document as a


condition to obtaining permits to construct water
projects falling under federal jurisdiction.
The EIS evaluated over 100 potential projects to
meet Denver water requirements over a 50-year planning
period from 1985 through 2035. Due to the ready
availability of information regarding project costs and
yields from the EIS, the Denver situation was ideal for
analysis by the OSDP procedure.
Input Data
As discussed previously, input data required for
the OSDP procedure include (1) the projected water
demand, (2) project characteristics, (3) the effective
interest rate, and (4) objective-space discretization
and bounds. These items are discussed as follows as
they relate to the Denver study.
Forecast Water Demand
Annual water demand is projected by the EIS to
increase from 370,000 acre-feet in 1985 to over 600,000
acre-feet by 2035 as shown in Figure 4.1. This
forecast assumes the low growth rate and poor economic
conditions which prevailed through the middle and late
1980's will reverse causing the city to grow more
rapidly. In addition, it is assumed per capita water
32


620
600
580
560
540
520
500
480
460
440
420
400
380
360
; 4.
Denver Metropolitan 4rea
1985 1990 1995 2000 2005 2010 2015 2020 2025 2030 2035
. Forecast Denver metropolitan area water demand.


demand will edge upward without implementation of
water conservation measures.
Water supply, defined as the firm yield of the
system, was approximately 420,000 acre-feet at the
beginning of the study period in 1985 as shown in
Figure 4.1.
Projects
Twenty-five water projects were selected for
analysis by the OSDP model. They consist of water
exchanges, east slope storage, west slope storage and
collection, groundwater and other projects as shown in
Table 4.1. The projects are listed in order of
increasing construction cost, as required for the
model, in Table ,4.2. The projects included in the
analysis are not comprehensive of all possible
alternatives, but rather are intended to be
representative of various project types and locations
being considered by area planners. The project
attributes shown in Tables 4.1 and 4.2 were obtained
primarily from the EIS and are discussed as follows:
Project Costs. Capital costs indicate the overall
planning, engineering, legal and construction costs
required to complete a project exclusive of costs for
environmental impact mitigation. Operation and
34


Table 4.1. Potential Water Projects Grouped by Project Type.
* ESTIMATED PROJECT COSTS IMPLEMEN-
ESTIMATED - TATION
PROJECT SAFE YIELD IMPLEMENTATION 0 & M TIME
PROJECT TYPE NO. PROJECT (1000 af/yr) ($ mil) ($ mil/yr) (years)
Exchanges 3 Transmountain Effluent Exchange 14 3.5 0.01 2
4 Blue River Exchange 10 11.0 0.01 2
East Slope 20 Small Two Forks Reservoir 77 395.0 0.20 7
Storage 13 Two Forks 2nd Stage 36 81.0 0.03 4
22 Large Two Forks Reservoir 113 429.0 0.23 7
16 Small Estabrook Reservoir 61 200.0 0.18 5
19 Large Estabrook Reservoir 73 272.0 0.20 6
23 New Cheesman Reservoir 68 600.0 0.20 6
West Slope 15 Gross Reservoir Enlargement 21 122.1 0.03 4
Storage and 8 Wolford Mountain Reservoir 0 40.0 0.05 6
Collection 2 Straight Creek Collection 0 3.2 0.02 3
11 Williams Fork Gravity Collectio 12 71.3 0.11 15
12 Williams Fork Pumping Collectio 13 78.6 0.58 6
21 East Gore Collection 0 420.5 0.13 8
24 Green Mountain Pumping Collecti 120 994.0 22.00 10
17 Rock Creek Reservoir 0 200.0 0.09 6
25 Eagle-Piney/Eagle-Colorado 35 1763.9 11.53 20
Groundwater 18 Municipal Ground Water 53 228.4 8.54 6
14 Satellite Well Field 23 111.2 4.05 6
1 Cherry Creek Wells 2 0.2 0.02 1
Other 6 Windy Gap Water 9 27.0 0.07 2
Projects 5 Existing Ditch & Well Rights 10 15.0 0.01 2
10 Purchase of Agricultural Water 15 60.0 0.01 3
9 Nonpotable Reuse 10 58.0 1.35 4
7 Projects of Others 7 35.0 0.10 10
* Safe yield if constructed independently. Projects with zero yield require
construction of interdependent projects to dependably yield water.


Table 4.2. Potential Water Projects Listed in Order of Implementation Cost
* ESTIMATED PROJECT COSTS IMPLEMEN-
ESTIMATED--------------------------- TATION
PROJECT NO. SAFE PROJECT (1000 YIELD af/yr) IMPLEMENTATION ($ mil) 0 & M ($ mil/yr) TIME (years)
1 Cherry Creek Wells 2 0.2 0.02 1
2 Straight Creek Collection 0 3.2 0.02 3
3 Transmountain Effluent Exch. 14 3.5 0.01 2
4 Blue River Exchange 10 11.0 0.01 2
5 Existing Ditch & Well Rights 10 15.0 0.01 2
6 Windy Gap Water 9 27.0 0.07 2
7 Projects of Others 7 35.0 0.10 10
8 Wolford Mountain Reservoir 0 40.0 0.05 6
9 Nonpotable Reuse 10 58.0 1.35 4
10 Purchase of Agricultural Water 15 60.0 0.01 3
11 Williams Fork Gravity Collect. 12 71.3 0.11 15
12 Williams Fork Pumping Collect. 13 78.6 0.58 6
13 Two Forks 2nd Stage 36 81.0 0.03 4
14 Satellite Well Field 23 111.2 4.05 6
15 Gross Reservoir Enlargement 21 122.1 0.03 4
16 Small Estabrook Reservoir 61 200.0 0.18 5
17 Rock Creek Reservoir 0 200.0 0.09 6
18 Municipal Ground Water 53 228.4 8.54 6
19 Large Estabrook Reservoir 73 272.0 0.20 6
20 Small Two Forks Reservoir 77 395.0 0.20 7
21 East Gore Collection 0 420.5 0.13 8
22 Large Two Forks Reservoir 113 429.0 0.23 7
23 New Cheesman Reservoir 68 600.0 0.20 6
24 Green Mountain Pumping Collect. 120 994.0 22.00 10
25 Eagle-Piney/Eagle-Colorado 35 1763.9 11.53 20
* Safe yield if constructed independently. Projects with zero yield require
construction of interdependent projects to dependably yield water.


maintenance (O&M) costs include annual manpower and
equipment expenses required to operate the project.
Safe Yield. The safe yield refers to the
estimated annual project water yield which would occur
during a severe drought as represented by the Colorado
drought of the mid-1950's. The safe yield values
indicated in Tables 4.1 and 4.2 are valid for the
projects constructed in the absence of possible
interdependent projects. For example, project 8 has no
yield if constructed alone. It must be constructed
with certain other projects to dependably yield any
water.
Project Linkages. Project "linkages describing
yield interrelationships and incompatibilities are
input to the model via a linkage matrix as shown in
Table 4.3 for the 25 projects selected for analysis.
The linkage between two projects is located at the
intersection of the row and column corresponding to the
two project numbers. A linkage value of -999 indicates
project incompatibility. For example project numbers
16, 19, 20, 22 and 23 are mutually incompatible as they
correspond to east slope storage projects of which only
one can efficiently be constructed due to water
availability limitations. Linkage values other than
37


table 4.3. Project Linkage Hatrix.
Positive ntmber indicates yield increase,
Negative lumber indicates yield decrease,
(-999) Indicates project inconpatibility PROJECT NUKBER
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
1 | -999 1
2 1 -999 3.5 3.5 3.5 3.5 3.5 3.5
3 ! -999 1
4 1 -999 20 20
5 1 -999 .
P 6 1 -999
R 7 1 -999
0 8 1 3.5 20 -999 -999 32 1 109 |
J 9 1 -999
E 10 1 -999 1
C 11 1 -999 -999 1 1 1 2 2 3
T 12 1 -999 -999 1 1 5 2 2 3
13 1 1 1 -999 -4 -999 -999 -999 -999
N 14 1 -999 1
D 15 1 1 1 -4 -999 -12 -15 -15 *19
H 16 | 3.5 1 5-999 -12 -999 -999 -999 27 -999 -999 5 1
B 17 1 3.5 20 -999 -999 32 1 109 |
E 18 1 -999 1
R 19 | 3.5 2 2-999 -15 -999 *999 -999 27 -999 -999 14 25 |
20 | 3.5 2 2 -15 -999 -999 -999 27 -999 -999 14 25 |
21 1 32 27 32 27 27 -999 27
22 | 3.5 3 s 3 -999 -19 -999 -999 -999 27 -999 -999 14 25 |
23 | -999 -999 -999 -999 -999 -999
24 | 1 5 1 14 14 14 -999 1
25 | 109 109 25 25 25 -999 |
1 2 3 4 5 6 1 8 9 10 11 12 13 14 15 16 11 18 19 20 21 22 23 24 25
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


-999 indicate yield increases or decreases which occur
as result of constructing certain project combinations.
Project Contingencies. Only one project
contingency is required of the projects selected for
analysis. The Two Forks Reservoir project, if
constructed in stages, requires the first stage be
constructed prior to the second stage. In as much as
this was the only such requirement, it was incorporated
explicitly in the program code rather than via the
input data.
Implementation Time. The project implementation
time reflects the estimated time required to design and
construct a project. Delays resulting from legal,
financial and institutional difficulties are not
included in these estimates.
Interest Rate
An interest rate of 3 percent was chosen for all
model runs. This rate is used by the Denver Water
Department for long term infrastructure planning.
Objective-Space Discretization
The program was executed for several
discretization intervals of the cost target objective-
space ranging from $20 million to $1 million. Upper
and lower bounds on the objective-space were
39


established to provide the greatest possible latitude
for identification of the optimal cost trajectory while
remaining within a 101 targets-per-stage limit imposed
by the CSUDP program. As an example, for a
discretization interval of $10 million, the upper and
lower limits were set at zero and $1 billion ( [$1
billion $0] -r $10 million = 100 target intervals or
101 targets ).
For fine discretization intervals (less than $5
million), it is necessary to define increasing upper
and lower objective-space boundaries to effectively
contain the optimal cost trajectory. For example a
discretization interval of $1 million is limited to an
objective-space corridor width not greater than $100
million to remain within the maximum targets per stage
limitation. If the final optimal cost is $500 million,
then the optimal state-space corridor must slope upward
to contain the optimal trajectory.
Results
The optimal water supply capacity expansion
schedule for the city of Denver was computed for
objective-space discretization intervals of $20
million, $10 million, $5 million, $2 million and $1
million. The resulting minimum final discounted
40


investment costs for the five discretization intervals
are listed as follows and displayed graphically in
Figure 4.2.
Obj ective-space Discretization Interval ($ million) Final Discounted Cost ($ million)
20 933
10 586
5 540
2 453
1 401
Cost trajectories over the 50-year study period
which result in the optimal final discounted costs are
shown in Figure 4.3. System water yield trajectories
corresponding to the cost trajectories are shown in
Figure 4.4.
The results of the analysis indicate the minimum
discounted final investment cost to meet forecast water
demand for the Denver area through 2035 is $401
million, computed using a $1 million discretization
interval. Cost and yield trajectories resulting in the
minimum cost are shown in Figure 4.5 without the
trajectories for the other discretization intervals.
Project numbers are shown adjacent to the cost and
yield curves in Figure 4.5 to indicate the time the
projects were completed. Appendix A contains separate
41


1
Interest Rate 3 percent
M
c
o
4-*
W
C>
o
*o
CI
c
D
o
U
<0
h
a
c
E
$933 mil
Figure 4.2. Final discounted investment costs for various objective-space
discretization intervals.


Oo
4*
C
o
2
cn
4-'
10
o
o
u
o
w.
a.
a
a*
c
i
o
<0
5
OPTIMAL DISCOUNTED COST TRAJECTORIES
Figure 4.3. Investment cost trajectories computed for various objective-
space discretization intervals.


lOOO acrefeet
OPTIMAL SYSTEM YIELD TRAJECTORIES
1995 2005 2015 2025 2035
Figure 4.4. Water system yield trajectories computed for various
objective-space discretization intervals..


1000 acrefeet Discounted Project Costs (billion $)
OPTIMAL DISCOUNTED COST TRAJECTORY
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
1995 2005 2015 2025 2035
OPTIMAL SYSTEM YIELD TRAJECTORY
Interest Rate 3 percent
750
700
650
600
550
500
450
400
350
Figure 4.5. Investment cost and system yield trajectories
for SI million objective-space discretization interval.
1590 | 2000 | 2010 | 2020 ' I 2030 |
1995 2005 2015 2025 2035
Interest Rate 3 percent
45


cost and yield trajectories for the other
discretization intervals.
The projects which result in the minimum final
cost are listed in Table 4.4 along with their
corresponding firm annual yield and the year they were
selected. A graphical display of the project
implementation schedule is shown in Figure 4.6.
Due to possible non-uniqueness of the project
trajectories resulting in the minimum final costs, it
is not possible to claim global optimality of the
solutions obtained for the various discretization
intervals. This item is discussed more fully in
Chapter 5.
46


Table 4.4. Projects Resulting in Optimal Discounted
investment Cost.
Project Year
No. Project Selected
1 Cherry Creek Wells 1990
2 straight Creek Collection 1993
3 Transraountain Effluent Exch. 1992
4 Blue River Exchange 1989
5 Existing Ditch & Well Rights 1996
6 Windy Gap Water 1994
7 Projects of others 1991
8 Wolford Mountain Reservoir 1999
9 Nonpotable Reuse 1995
10 Purchase of Agricultural Water 2012
11 Williams Fork Gravity Collect. 1997
15 Gross Reservoir Enlargement 1999
16 small Estabrook Reservoir 2015
47


PROJECT YEAR
NO. 1990 1995 2000 2005 2010 2015 2025 2025 2030 2035
Figure 4.6. Project implementation schedule for SI million
objective-space discretization interval.
48


CHAPTER 5
DISCUSSION
Several items worthy of discussion were observed
during research, preparation and execution of the OSDP
model including (1) project scheduling trends, (2)
potential difficulties with the OSDP method, (3) model
execution times, and (4) model limitations.
\
Scheduling Trends
The OSDP model was successful in identifying
project implementation schedules to meet projected
water demand at minimum cost. Although runs for
different cost target discretizations provided
different results, a project scheduling trend was
apparent. The model generally selected lower cost
projects earlier in the study period. This is due in
part to the effect of discounting which encourages
postponement of more expensive projects until later
stages.
Another explanation for this scheduling trend is
the lower cost projects combinatorially provide more
opportunity to achieve particular cost targets. As the
number of low cost projects is exhausted, the model


must increasingly choose higher cost projects which may
not as closely meet the cost targets.
Finally, the lower cost projects with their lower
yields provide a means to more closely follow the water
demand curve as it increases with time. Larger water
projects by their nature result in substantial excess
yield at the time those projects come on line. In
reality, such excess yield provides additional
insurance against water shortages and provides more
opportunity for additional growth in a municipality.
However, these benefits are not rewarded in the model
as it is currently formulated.
Potential Difficulties
Three potential difficulties concerning the OSDP
algorithm, and its relationship to the capacity
expansion problem as formulated herein, were
identified. These difficulties relate to (1) the
discretization interval of the project cost objective-
space, (2) possible non-uniqueness of the optimal cost
trajectory and (3) the incorporation of project
linkages.
Discretization Interval Effects
As shown in Figures 4.3 and 4.4, the model is
obviously sensitive to the objective-space
50


discretization interval. It is apparent as the
interval is made smaller, the model is able to find a
more optimal path through the objective space while
still meeting water demands. The reason for this is
fundamental to solution of continuous state-space
problems by dynamic programming. Discretization of a
continuous state-space problem forces the solution
trajectory to take a stair-step path through the
decision space. As the discretization interval is made
smaller, the optimal solution trajectory identified by
the dynamic programming algorithm can more closely
approximate the true global optimum solution.
The capacity expansion problem examined herein is,
in reality, a discrete decision problem in the state-
space defining whether or not a project is constructed.
The decision to construct a particular project is a
yes/no (discrete) proposition made during each year
(stage) of the study period. If solution of the
problem were computationally feasible by a traditional
state-space dynamic programming approach, the state-
space would not have to be discretized as it is already
binary.
However, the OSDP approach requires the objective-
space to take the place of the project state-space for
computational purposes. As a result, the decision-
51


space or objective-space is no longer binary. In the
capacity expansion application, the objective-space is
technically still discrete due to the finite number of
projects involved in the analysis. However, due to the
multitude of possible project combinations, the
tremendous number of discrete cost states potentially
available at each stage precludes their explicit
consideration in a model. Consequently, the objective-
space must be discretized for computational purposes.
Although the OSDP approach provides a means to
solve a highly dimensional state-space problem, the
necessary discretization introduces concerns with
respect to the capability of the OSDP model to achieve
a true global optimal solution. The Labadie and
Fontane (1989) proof of the global optimality of
solutions obtained by the OSDP approach states as the
discretization interval of the objective-space
approaches zero in the limit, the solution identified
by the OSDP model will be a global optimal solution.
Computational considerations affect the ability of
the OSDP model to employ a minimal objective-space
discretization while maintaining a large objective-
space corridor to consider all possible solutions. It
is necessary to constrain the objective-space for a
relatively fine discretization to some corridor through
52


the objective-space to stay within the 101 decision-
states-per-stage limit imposed by CSUDP. One way to
define the objective-space corridor utilizes the
optimal cost trajectory identified during a previous
run with a coarser discretization interval. The
corridor is simply constructed as some amount greater
than and less than the cost targets defining the
previous optimal path. This procedure, which was used
in the current model, has been labeled by Labadie
(1990) as "splicing."
The difficulty in using the splicing approach in
the capacity expansion OSDP model is the optimal
solution identified for a coarse discretization
interval may deviate substantially from the optimal
trajectory for a finer discretization interval. As the
objective-space decision corridor is narrowed to permit
use of finer discretization intervals, it is possible
the global optimal solution may be missed. An example
of this possibility is described as follows with
reference to Figure 5.1.
Assume an optimal cost trajectory is identified by
the OSDP model for a discretization interval of $10
million as shown. Also assume the model, if not
restricted by a maximum number of decision states at a
particular stage (i.e., less than 101), would compute
53


Discounted Project Costs ($ billion)
700
Figure 5.1. Investment cost trajectories for splicing example.


the optimal trajectory shown for a discretization
interval of $1 million. If a splicing procedure were
utilized to establish a corridor around the solution
for the $10 million interval, it is possible the
corridor might exclude the true optimal solution for
the $1 million interval. Thus extreme care must be
taken when performing splicing operations in order to
avoid missing the optimal solution. This applies to
all dynamic programming applications involving a
discretized decision space.
One check for ensuring the optimal solution is not
missed is to verify the optimal cost trajectory
computed by the model does not encounter the upper or
lower objective-space corridor boundaries. If a
boundary is encountered, it should be relaxed in the
vicinity of the encounter and the model executed again.
However, an overly constrained decision space may
simply produce a solution entirely within the bounds of
the corridor, thus providing no indication the global
optimum solution for the particular discretization
interval was missed. In this case the solution would
be a local optimum.
It should be noted CSUDP has an option whereby
splicing is performed automatically. The splicing
option employs boundary relaxation and gradient search
55


techniques to ensure the solution identified by the
program is at least a local optimum solution. Use of
the automatic splicing option for the OSDP method would
require additional modification of the csudp program.
solution Non-Uniqueness
As noted in Chapter 3, the conceptual basis for
the OSDP approach relies on the assumption of
uniqueness of objective function values computed for
the optimal objective-space trajectory. If the same
optimal objective function value at a particular stage
may be achieved by different cost trajectories, then
the model cannot evaluate which trajectory to choose.
The model would have to carry both solutions forward to
subsequent stages in order to ensure global optimality
of the final result. Each additional tie would result
in a geometric increase in computer memory requirements
and execution time which would quickly preclude
practical solution of the problem.
As a means of dealing with ties, CSUDP requires
selection of a tie-breaking option in which either the
first tie or last tie is stored as the optimal state.
Therefore, if any ties occur during execution of the
modeL, global optimality Of the solution for the
particular discretization interval cannot be guaranteed
56


as the model is not capable of evaluating all paths
resulting in the tie.
One way to detect the presence of a tie is to
execute the model twice with a particular data set,
using a different tie breaking option for each run. If
different results are obtained from the two runs, it is
likely one or more ties occurred.
The detection procedure was performed on the
Denver water project data and unfortunately revealed
the occurrence of possible ties. This does not
invalidate the results obtained for the Denver capacity
expansion problem as they appear reasonable; however,
it precludes guaranteeing their optimality.
In order to restore a guarantee of global
optimality it would be necessary to break the ties on
the basis of some other constraint or objective. For
example, environmental constraints could be introduced
which cause the model to select the tie-producing path
which does not violate a certain environmental
standard.
Project Linkages
Incorporation of project linkages in the OSDP
approach represents an extension of the method not
utilized in previous applications. Although not
evident in runs made during the current application, it
57


is possible inclusion of project linkages could prevent
the model from obtaining a global optimum solution due
to the model being unable to consider all feasible
project combinations at all stages. This possible
difficulty relates to the incompatibility component of
the project linkages and is illustrated by the
following example.
Assume the model identifies a particular optimal
actual cost for cost target, Ci; through stage, i. To
achieve that cost requires selection of certain
projects, Ui, through that stage. At stage, i+1, and
all subsequent stages, any cost trajectory which goes
through cost target, C, necessarily must also include
projects, Uj Consequently, this precludes selection
of projects which are incompatible with projects, Uj ,
at later stages. This implicit omission of certain
projects at later stages could result in the optimal
cost trajectory being missed. This is due to the model
dismissing a suboptimal path to an early stage cost
target, Cir involving different projects which might
permit construction of projects at later stages
resulting in a lower overall cost.
If the global optimum solution were initially
missed due to the project linkage problem, continued
reduction of the discretization interval would probably
58


ultimately result in the model identifying the correct
solution. This is consistent with the proof of global
optimality of solutions identified by OSDP as the
discretization interval approaches zero in the limit.
Model Execution Times
The OSDP model was executed on an IBM PC
compatible microcomputer equipped with an 80286
processor, a math co-processor and 640 kilobytes of
random access memory (RAM), Model execution times
ranged from one to sixteen hours depending on the
discretization of the objective-space. These lengthy
execution times might restrict the opportunity of a
user to comprehensively evaluate the effects of various
discretization intervals, interest rates and other
variables, given the budgetary constraints associated
with most engineering studies.
Use of a more powerful microcomputer equipped with
an 80386 processor and additional RAM (i.e. 1 megabyte
or more) would likely reduce execution times to a more
reasonable level. The additional memory would allow
the user to create a virtual disk in RAM on which the.
model could be loaded and executed. This would reduce
execution time as the computer could perform the large
number of read and write operations required by the
59


model in RAM rather than to and from the hard drive.
It is estimated these improvements could reduce the
model execution time to no more than two or three
hours.
Model Limitations
The OSDP model described herein, like most models
of a decision process, is not able to fully incorporate
all aspects of the decision process. Two noteworthy
items of the water supply capacity expansion decision
process omitted from the model are consideration of
water conservation measures and other possible
objectives associated with water supply planning.
Conservation Measures
The model as currently configured is capable of
only considering projects which increase the supply of
the system. Water conservation measures, which provide
alternative means to keep demand below available
supply, are not considered. If conservation measures
were handled simply as a project which increases yield,
they could probably be incorporated in the model with
little difficulty. If instead, conservation measures
were incorporated as they actually operate by reducing
demand, they would add another dynamic programming
60


dimension resulting in more difficult adaptation of the
model to consider their effect.
Multiple objectives
There are limitations associated with the
objective-space approach, or any other approach which
considers only one objective. Most complex problems
typically include multiple objectives. This is
certainly the case for water resource planning problems
which, in addition to cost, may also include
environmental objectives, and institutional objectives
or constraints. Use of the single-objective OSDP model
as a screening tool should be followed by additional
investigation and analysis concerning the impacts on
other objectives resulting from construction of certain
projects.
As an alternative to separate analysis of other
objectives, it appears the OSDP method could be adapted
to consider more than one objective. For example, if
water quality were a concern to those involved in
decisions regarding expansion of a water supply system,
each water project could be evaluated in terms of its
impact on water quality. The OSDP procedure could then
be applied in the water quality dimension. Analysis of
the water quality component would occur similarly to
61


that demonstrated for the cost objective. A range of
target water quality impacts would be identified for
each stage. The model would select the optimal water
quality targets which result in meeting the forecast
water demand at minimum total water quality degradation
at the end of the study period. Using some weighting
procedure, the cost and water quality models could be
coupled and executed as a two-dimensional OSDP model to
minimize both cost and water quality impact.
As previously mentioned, the curse of
dimensionality becomes a problem for dynamic
programming applications with highly dimensional
decision spaces. However inclusion of only one or two
additional objective-space dimensions is probably
computationally manageable using the OSDP approach for
multi-objective analysis of the capacity expansion
problem.
62


CHAPTER 6
CONCLUSION
Most previous applications of optimization
techniques to analyze the water supply capacity
expansion problem have been limited in their ability to
consider large numbers of potential projects. A few
applications have attempted to broaden the number of
projects considered by incorporating various heuristic
techniques. Unfortunately, these techniques can limit
general applicability of these models due to their
reliance on particular aspects of the physical system
being analyzed.
The OSDP method of analysis provides a means to
optimally schedule water supply projects to meet
increasing demand in a manner not limited by the number
of potential projects. This can allow the model to be
used more effectively as a screening tool for water
supply planners and decision makers as they need not
limit the scope of potential solutions due to the
limits of their analytical procedures.
In addition, any optimizing technique which
incorporates dynamic programming, such as OSDP,
benefits by the introduction of additional constraints.


Such constraints serve to lessen the breadth of the
decision space which results in reduction of execution
times. This encourages the user to increase the
complexity of the model rather than the opposite as may
be necessary for other procedures. Such action
increases the likelihood the model will be able to
capture the essence of the physical system, and should
increase the reliability of the results.
Finally, the OSDP procedure shows promise in being
adapted to more than one objective. This could aid in
its application to more complex and controversial
problems involving multiple objectives.
64


APPENDIX A
COST AND YIELD TRAJECTORIES FOR $20 MILLION,
$10 MILLION, $5 MILLION AND $2 MILLION
DISCRETIZATION INTERVALS


1000 acrerest Dlscountsd Project Casta (billion t)
OPTIMAL DISCOUNTED COST TRAJECTORY
Interest Rate 3 percent
OPTIMAL SYSTEM YIELD TRAJECTORY
Interest Rate 3 percent
Figure A.l. Investment cost and system yield trajectories
for S20 million objective-space discretization interval.
66


1000 ocrefeet Discounted Project Costs (billion $)
OPTIMAL DISCOUNTED COST TRAJECTORY
1995 2005 2015 2025 2035
OPTIMAL SYSTEM YIELD TRAJECTORY
Interest Role 3 percent
Figure A.2. Investment cost and system yield trajectories
for S10 million objective-space discretization interval.
67


Discounted Project Costs (billion S)
OPTIMAL DISCOUNTED COST TRAJECTORY
i
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
750
700
650
600
550
500
450
400
350
OPTIMAL SYSTEM YIELD TRAJECTORY
Interest Rate 3 percent
, | | ..... -i----------1 |-------1-------1--------1-------1
1990 | 2000 I 2010 | 2020 I 2030 |
1995 2005 2015 2025 2035
Figure A.3. Investment cost and system yield trajectories
for S5 million objective-space discretization interval.
68


1000 ocrefeet Discounted Project Coats (billion S)
OPTIMAL DISCOUNTED COST TRAJECTORY
Interest Rate 3 percent
OPTIMAL SYSTEM YIELD TRAJECTORY
Interest Rate 3 percent
Figure A.4. Investment cost and system yield trajectories
for $2 million objective-space discretization interval.
69


GLOSSARY
analytical techniques. Optimization procedure which
makes use of functional relationships between
variables.
binary state-space dynamic programming. Dynamic
programming technique in which optimization occurs
in the multi-dimensional state space,
branch-and-bound. Solution procedure for integer
programming which divides and eliminates portions
of the possible solution set without explicitly
evaluating their contents.
capacitated expansion. Water supply capacity expansion
in which potential projects are of fixed size,
constraint. Limit or bound on a decision or state
variable.
contingencies. Condition in which construction of a
project is contingent on previous construction of
another project.
direct enumeration. Optimization technique which
examines all possible solutions,
discretization. Procedure in which a continuous
function, objective or variable is divided into
equal increments for analytical purposes.


dynamic programming. Optimization technique in which a
sequential decision problem is reduced to a
sequence of single stage problems,
global optimum. Best solution possible to an
optimization problem.
inner model. Component of an OSDP model which
identifies the optimal state-space values which
cause the objective function to equal or minimally
exceed objective-space targets at each problem
stage.
integer programming. Optimization technique in which
equations defining objectives and constraints are
solved simultaneously with decision variables
restricted to integer values,
interdependency. Condition in which the yield of a
project is affected by the existence of one or
more other projects.
linkages. Vector defining project incompatibilities
and yield interrelationships,
local optimum. Solution to an optimization problem
which is better than all neighborhood solutions
but which is not a global optimum solution,
objective space. Solution space defining possible
objective function targets, states or values.
71


objective function. Mathematical relationship defining
the objective of an optimization problem,
objective-space dynamic programming (OSDP). Dynamic
programming technique in which optimization occurs
in the one-dimensional objective space,
optimal water supply capacity expansion. Sequencing
water supply projects over a finite planning
period to meet forecast water demand and other
constraints at minimum cost,
outer model. Component of an OSDP model which
systematically considers a range of objective-
space targets.
safe yield. Dependable water supply available from a
project in an extreme drought year,
state space. Solution space which defines possible
state of a decision variable in a dynamic
programming application,
traceback. Dynamic programming procedure which
identifies the optimal path after evaluating all
problem stages.
trajectory. Path defining objective or problem
variable values over time,
uncapacitated expansion. Water supply capacity
expansion in which potential projects are of
variable size.
72


uniqueness. Requirement for global optimality of OSDP
solutions in which targets on the optimal
objective-space trajectory may be achieved by only
one path state-space path,
vector. Multi-dimensional variable,
virtual disk. Simulated hard disk created in a
Computer random access memory (RAM) which reduces
execution times for computer programs with
substantial input-output operations.

73


BIBLIOGRAPHY
Akileswaran, V., Morin, T. L., and Meier, W. L.,
(1979), "Heuristic Decision Rules for Water
Resources Planning," Technical Report 119, Purdue
University Water Resources Research Center, West
Lafayette, IN.
Ball, M. 0., Bialas, W. F., and Loucks, D. P., (1978),
"Structural Flood-Control Planning," Water
Resources Research, 14(1), 62-66.
Becker, L., and Yeh, W. W-G., (1974a), "Optimal Timing,
Sequencing and Sizing of Multiple Reservoir
Surface Water Supply Facilities," Water Resources
Research, 10(1), 57-62.
Becker, L., and Yeh, W. W-G., (1974b), "Timing and
Sizing of Complex Water Resources Systems," J.
Hydraulics Division, ASCE, 100(10), 1457-1470.
Bellman, R. E., (1957), Dynamic Programming, Princeton
University Press, Princeton, NJ.
Bickel, T. C., (1978), "The Optimal Capacity Expansion
of a Chemical Processing Plant via Nonlinear
Integer Programming," thesis presented to The
University of Texas at Austin, TX, in partial
fulfillment of the requirements of the degree of
Doctor of philosophy.
Bogle, M. G. V., and O'Sullivan, M. J., (1979),
"Stochastic Optimization of Water Supply
Expansion," Water Resources Research, 15(2), 1229-
1237.
Braga, B. P. F., Jr., Conejo, J. G. L., Becker, L., and
Yeh, W. W-G., (1985), "Capacity Expansion of Sao
Paulo Water Supply," J. Water Resources Planning &
Mgmt, ASCE, 111(2), 238-252.
Brill, E. D., and Nakamura, M., (1978), "Branch-and-
Bound Method for Use in Planning Regional
Wastewater Treatment Systems," Water Resources
Research, 14(1), 109-118.


Butcher, W. S., Haimes, Y. Y., and Hall, W. A., (1969),
"Dynamic Programming of the Optimal sequencing of
Water Supply Projects," Water Resources Research,
5(6), 1196-1204.
Cohon, J. L., (1978), "Multi-Objective Programming and
Planning," Mathematics in Science and Engineering,
140, Academic Press, New York.
Cooper, L., and Cooper, M. W., (1981), Introduction to
Dynamic Programming, Pergamon Press, Oxford, Eng.
Efroymson, M. A., and Ray, T. L., (1966), "A Branch-
and-Bound Algorithm for Plant Location,"
Operations Research, 14(3), 361-368.
Erlenkotter, D., (1973a), "Sequencing of Interdependent
Hydroelectric Projects," Water Resources Research,
9(1), 21-27.
Erlenkotter, D., (1973b), "Sequencing Expansion
Projects," Operations Research, 21(2), 542-553.
Erlenkotter, D., (1975), "Comment on 'Optimal Timing,
Sequencing and Sizing of Multiple Reservoir
Surface Water Supply Facilities' by L. Becker and
W. W-G. Yeh," Water Resources Research, 11(2),
380-381.
Fontane, D. G., Labadie, J. W., and Loftis, B., (1981),
"Optimal Control of Reservoir Discharge Quality
Through Selective Withdrawal," Water Resources
Research, 17(6), 1594-1604.
Fontane, D. G., Labadie, J. W., Loftis, B., and
Merritt, D. H., (1989), "Implementation Strategies
for Salinity Projects," J. Water Resources
Planning & Mgmt, ASCE, 115(5), 671-683.
Ford, D. T., (1986), "Dredged-Material Disposal System
Capacity," J. Water Resources Planning & Mgmt,
ASCE, 112(2), 277-291.
Gluss B., (1972), An Elementary Introduction to Dynamic
Programming, A State Equation Approach, Allyn and
Bacon, Boston, MA.
75


Kim, S. K., and Yeh, W. W-G., (1986), "A Heuristic
Solution Procedure for Expansion Sequencing
Problems, Water Resources Research, 22(8), 1197-
1206.
Kolo, D. E., and Haimes, Y. Y., (1977) "Capital
Expansion and Operational Planning for Regional
Water-Resource Systems," J. Hydrology, ASCE, 32,
363-381.
Labadie, J.W., (1990), "Dynamic Programming with the
Microcomputer," Encyclopedia of Microcomputers,
Volume 5, Marcel Dekker, New York, NY, 275-337.
Labadie, J. W. and Fontane, D. G., (1989), "Objective-
Space Dynamic Programming Approach to
Multidimensional Problems in Water Resources,"
Dynamic Programming for Optimal Water Resources
Systems Analysis, Prentice-Hall, Englewood Cliffs,
NJ, 88-115.
Marks, D. H., and Liebman, J. C., (1970), "Mathematical
Analysis of Solid Waste Collection," U. S. Dept,
of Health, Education and Welfare, Bureau of Solid
Waste Management, Washington, DC.
Martin, Q. W., (1987), "Hierarchical Algorithm for
Water Supply Expansion," J. Water Resources
Planning & Mgmt, ASCE, 113(5), 677-695.
Moore, N. Y., and Yeh, W. W-G., (1980), "Economic Model
for Reservoir Planning," J. Water Resources
Planning & Mgmt, ASCE, 106(2), 383-400.
Morin, T. L., (1973), "Pathology of a Dynamic
Programming Sequencing Algorithm," Water Resources
Research, 9(5), 1178-1185.
Morin, T. L., (1975), "Solution of Some Combination
Optimization Problems Encountered in Water
Resources Development," Engineering Optimization,
1(2), 155-157.
Morin, T. L., and Esogbue, A. M. O., (1971), "Some
Efficient Dynamic Programming Algorithms for the
Optimal Sequencing and Scheduling of Water
Problems Occurring in Capital Expenditure
Planning," Water Resources Research, 7(3), 479-
484 .
76


Morin, T. L., and Esogbue, A. M. O., (1974), "A useful
Theorem in the Dynamic Programming Solution of
Sequencing and Scheduling Problems Occurring in
Capital Expenditure Planning, Water Resources
Research, 7(3), 49-56.
Nakumura, M., and Brill, E. D., (1979), "Generation and
Evaluation of Alternative Plans for Regional
Wastewater Systems: An Imputed Value Method,"
Water Resources Research, 15(4), 750-756.
O'Laoghaire, D. T., and Himmelblau, D. M., (1972),
"Optimal Capital Investment in the Expansion of an
Existing Water Resources System," Water Resources
Research, 8(4), 653-668.
Rubinstein, J., and Ortolano, L., (1984), "Water
Conservation and Capacity Expansion," J. Water
Resources Planning & Mgmt, ASCE, 110(2), 220-237.
Scarato, R. F., (1969), "Time-Capacity Expansion of
Urban Water Systems," Water Resources Research,
5(5), 929-936.
77