OPTIMAL WATER SUPPLY CAPACITY EXPANSION
USING OBJECTIVESPACE 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
ObjectiveSpace 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 objectivespace. Application of
traditional statespace 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 50year 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
ObjectiveSpace 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
ObjectiveSpace Discretization ............ 39
Results.........................................40
5. DISCUSSION.......................................49
Scheduling Trends ............................. 49
Potential Difficulties ........................ 50
Discretization Interval Effects ........... 50
Solution NonUniqueness ................... 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 objectivespace discretization
intervals.................................42
4.3. Investment cost trajectories computed
for various objectivespace
discretization intervals..................43
4.4. Water system yield trajectories
computed for various objectivespace
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 objectivespace 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 longterm 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_, (nr) !
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 realworld planning situations in which more than
ten possible projects might be considered.
Integer Programming
Branchandbound techniques of integer programming
have been utilized to reduce the computational
magnitude of the direct enumeration approach. Branch
andbound 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 mixedinteger linear
programming using a branchandbound algorithm to
select and size disposal sites for a dredgedmaterial
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 shortestpath 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 nonlinear 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 multistage
problem to a sequence of singlestage problems.
Dynamic programming is capable of explicitly
considering nonlinear 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 statespace, 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 statespace, 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
statespace approach. This strategy restricts the
statespace to permutations of the project capacities.
In other words, instead of defining the statespace as
some equally discretized grid of project capacities,
the authors structured the statespace 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 statespace 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 statespace 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 multireservoir 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 statespace 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
forwardlooking dynamic program. The procedure was
applied to a proposed sixreservoir 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 statespace 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 statespace 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 10year stages. The model
considered six possible reservoir projects of fixed
size, six variablecapacity pipelines and one
groundwater project.
Rubinstein and Ortolano (1984) applied dynamic
programming to the solution of a dualobjective
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 noninferior set of solutions was generated
by varying the weights given to each objective using a
NonInferior 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
statespace 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
statespace to identify an initial solution. The
solution is then refined by repeated execution of the
model over an increasingly finer statespace
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
ObjectiveSpace Dynamic Programming
Fontane and Labadie (1981) introduced a new
procedure identified as objectivespace dynamic
programming (OSDP) in which the optimal solution to a
sequential decision process is determined by dynamic
programming in the onedimensional objectivespace
rather than the multidimensional statespace. 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 objectivespace and statespace 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 22year 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 twentyfour.
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. Noneconomic 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, ) >
Qi
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
objectivespace 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 Fortranbased 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 objectivespace mode
requires preparation of an additional subroutine which
performs statespace operations (project selection) to
meet objectivespace 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 objectivespace 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
mid1990'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 systemwide
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 50year 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) objectivespace 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 acrefeet in 1985 to over 600,000
acrefeet 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 acrefeet at the
beginning of the study period in 1985 as shown in
Figure 4.1.
Projects
Twentyfive 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 EaglePiney/EagleColorado 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 EaglePiney/EagleColorado 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 mid1950'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 5999 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 2999 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.
ObjectiveSpace 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 objectivespace were
39
established to provide the greatest possible latitude
for identification of the optimal cost trajectory while
remaining within a 101 targetsperstage 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 objectivespace boundaries to effectively
contain the optimal cost trajectory. For example a
discretization interval of $1 million is limited to an
objectivespace 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 statespace 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
objectivespace 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 ectivespace Discretization Interval ($ million) Final Discounted Cost ($ million)
20 933
10 586
5 540
2 453
1 401
Cost trajectories over the 50year 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 objectivespace
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
objectivespace 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 objectivespace 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 nonuniqueness 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
objectivespace 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 nonuniqueness 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 objectivespace
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 statespace
problems by dynamic programming. Discretization of a
continuous statespace problem forces the solution
trajectory to take a stairstep 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
statespace 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 statespace for
computational purposes. As a result, the decision
51
space or objectivespace is no longer binary. In the
capacity expansion application, the objectivespace 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 statespace 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 objectivespace
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 objectivespace
discretization while maintaining a large objective
space corridor to consider all possible solutions. It
is necessary to constrain the objectivespace for a
relatively fine discretization to some corridor through
52
the objectivespace to stay within the 101 decision
statesperstage limit imposed by CSUDP. One way to
define the objectivespace 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
objectivespace 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 objectivespace 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 NonUniqueness
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 objectivespace 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 tiebreaking 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 tieproducing 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 coprocessor and 640 kilobytes of
random access memory (RAM), Model execution times
ranged from one to sixteen hours depending on the
discretization of the objectivespace. 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
objectivespace 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 singleobjective 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 twodimensional 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 objectivespace dimensions is probably
computationally manageable using the OSDP approach for
multiobjective 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 objectivespace 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 objectivespace 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
,   ..... i1 1111
1990  2000 I 2010  2020 I 2030 
1995 2005 2015 2025 2035
Figure A.3. Investment cost and system yield trajectories
for S5 million objectivespace 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 objectivespace discretization interval.
69
GLOSSARY
analytical techniques. Optimization procedure which
makes use of functional relationships between
variables.
binary statespace dynamic programming. Dynamic
programming technique in which optimization occurs
in the multidimensional state space,
branchandbound. 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 statespace values which
cause the objective function to equal or minimally
exceed objectivespace 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,
objectivespace dynamic programming (OSDP). Dynamic
programming technique in which optimization occurs
in the onedimensional 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
objectivespace trajectory may be achieved by only
one path statespace path,
vector. Multidimensional variable,
virtual disk. Simulated hard disk created in a
Computer random access memory (RAM) which reduces
execution times for computer programs with
substantial inputoutput 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 FloodControl Planning," Water
Resources Research, 14(1), 6266.
Becker, L., and Yeh, W. WG., (1974a), "Optimal Timing,
Sequencing and Sizing of Multiple Reservoir
Surface Water Supply Facilities," Water Resources
Research, 10(1), 5762.
Becker, L., and Yeh, W. WG., (1974b), "Timing and
Sizing of Complex Water Resources Systems," J.
Hydraulics Division, ASCE, 100(10), 14571470.
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. WG., (1985), "Capacity Expansion of Sao
Paulo Water Supply," J. Water Resources Planning &
Mgmt, ASCE, 111(2), 238252.
Brill, E. D., and Nakamura, M., (1978), "Branchand
Bound Method for Use in Planning Regional
Wastewater Treatment Systems," Water Resources
Research, 14(1), 109118.
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), 11961204.
Cohon, J. L., (1978), "MultiObjective 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
andBound Algorithm for Plant Location,"
Operations Research, 14(3), 361368.
Erlenkotter, D., (1973a), "Sequencing of Interdependent
Hydroelectric Projects," Water Resources Research,
9(1), 2127.
Erlenkotter, D., (1973b), "Sequencing Expansion
Projects," Operations Research, 21(2), 542553.
Erlenkotter, D., (1975), "Comment on 'Optimal Timing,
Sequencing and Sizing of Multiple Reservoir
Surface Water Supply Facilities' by L. Becker and
W. WG. Yeh," Water Resources Research, 11(2),
380381.
Fontane, D. G., Labadie, J. W., and Loftis, B., (1981),
"Optimal Control of Reservoir Discharge Quality
Through Selective Withdrawal," Water Resources
Research, 17(6), 15941604.
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), 671683.
Ford, D. T., (1986), "DredgedMaterial Disposal System
Capacity," J. Water Resources Planning & Mgmt,
ASCE, 112(2), 277291.
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. WG., (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
WaterResource Systems," J. Hydrology, ASCE, 32,
363381.
Labadie, J.W., (1990), "Dynamic Programming with the
Microcomputer," Encyclopedia of Microcomputers,
Volume 5, Marcel Dekker, New York, NY, 275337.
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, PrenticeHall, Englewood Cliffs,
NJ, 88115.
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), 677695.
Moore, N. Y., and Yeh, W. WG., (1980), "Economic Model
for Reservoir Planning," J. Water Resources
Planning & Mgmt, ASCE, 106(2), 383400.
Morin, T. L., (1973), "Pathology of a Dynamic
Programming Sequencing Algorithm," Water Resources
Research, 9(5), 11781185.
Morin, T. L., (1975), "Solution of Some Combination
Optimization Problems Encountered in Water
Resources Development," Engineering Optimization,
1(2), 155157.
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), 4956.
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), 750756.
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), 653668.
Rubinstein, J., and Ortolano, L., (1984), "Water
Conservation and Capacity Expansion," J. Water
Resources Planning & Mgmt, ASCE, 110(2), 220237.
Scarato, R. F., (1969), "TimeCapacity Expansion of
Urban Water Systems," Water Resources Research,
5(5), 929936.
77
