WATER POLLUTION CONTROL RESEARCH SERIES 16110 FZE 09/70 Use of New Analytical Methods in Water Resource Development U.S. DEPARTMENT OF THE INTERIOR • FEDERAL WATER QUALITY ADMINISTRATION ------- WATER POLLUTION CONTROL RESEARCH SERIES The Water Pollution Control Research Reports describe the results and progress in the control and abatement of pollution in our Nation's waters. They provide a central source of information on the research, develop- ment, and demonstration activities in the Federal Water Quality Administration, in the U. S. Department of the Interior, through inhouse research and grants and con- tracts with Federal, State, and local agencies, research institutions, and industrial organizations. Inquires pertaining to Water Pollution Control Research Reports should be directed to the Head, Project Reports System Planning and Resources Office, Office of Research and Development, Department of the Interior, Federal Water Quality Administration, Room 1108, Washington, D. C, 202U2. ------- Use of New Analytical Methods in Water Resource Development by Department of Mechanical Engineering The University of Texas at Austin Austin, Texas 78712 for the FEDERAL WATER QUALITY ADMINISTRATION DEPARTMENT OF THE INTERIOR Program #16110 FZE Formerly WP-01186 September, 1970 ------- FWQA Review Notice This report has been reviewed by the Federal Water Quality Administration and approved for publication. Approval does not signify that the contents necessarily reflect the views and policies of the Federal Water Quality Adminis- tration, nor does mention of trade names or commerical products constitute endorsement or recommendation for use. ------- ABSTRACT Studies were made to determine the feasibility of applying recently developed analtyical techniques to the problem of planning for optimal water resource development. An optimal plan with regard to the size and location of proposed reservoirs was taken to be that physical configuration which provided the greatest net economic benefit to the people of the region while meeting future water needs. This research was aimed at providing an improvement over the sub- optimal planning techniques of the past which did not take into account the interacting effects which exist between each reservoir and all downstream reservoirs. These interacting effects are actually the predominant characteristics to be considered in the design of a system of reservoirs in any river basin, and cannot be ignored. For the purpose of formulating a mathematical model for this type of problem, a number of recently developed optimization techniques were studied. The best formulation was found to be that which treated the reservoir system design as a branched multistage decision process. In such processes, the decisions made at each stage (potential reservoir site) affect the circumstances under which all subsequent decisions in the sytem must be made. The intercoupled staging structure of this process was then exploited by means of the nonserial dynamic program- ming algorithms developed in the course of this research project. These algorithms are effectively decomposition techniques which break down the nonserial (i.e. branched) process into an equivalent serial process that is amenable to solution through ordinary dynamic programming methods. This report was submitted in fulfillment of Grant No. 16110 FZE, between the Federal Water Quality Administration and the University of Texas at Austin, directed by Dr. Charles S. Beightler. ------- CONTENTS Section Page I Conclusions 1 II Recommendations ia- III Introduction 1 IV Discussion and Results 4 V References H VI Publications and Patents 13 ------- SECTION I CONCLUSIONS 1. An accurate appraisal of the worth of any single water resource development project can no longer be made on an individual basis. Rather, each project for resource development can be planned and designed correctly only when it is considered as part of a larger system of projects in the region of development. When this is done, the expenditure of funds for project development can be made on the basis of how the individual project will contribute to the overall development of the entire region. 2. Sub-optimal planning in the determination of the size and location of reservoirs in a river basin system results when a reservoir design does not take into account the interacting effects between each reservoir and all downstream reservoirs. To avoid such sub-optimization, a mathematical model was developed which takes into account not only the staged structure of the problem, but also the effects of the non-serial (branched) inputs characteristic of a river basin system. 3. A new solution technique was developed for finding the optimal solution to the system as described by the mathematical model. This algorithm is based upon the branch compression method which was also developed during the course of this project. 4. This new method for finding the optimal reservoir system design has been coded for a digital computer, but owing to the early termination of this research project, the computer program has not been up-dated to include all the optimization techniques developed during the project. ------- SECTION II RECOMMENDATIONS This project was limited to the development of mathematical models and optimization techniques which could be applied to the design of river basin systems. Early and unexpected termination of the project did not permit the production of a computer program with the ability to handle the large number of converging and diverging branches which are typical of river basin systems. Development of such a computer program would permit the solution of large-scale systems met in practice. This would allow for the evaluation of existing systems as well as the optimal design of new systems. Further studies should be made of the Geometric Programming algorithm, which makes provision for the handling of non-linear inequality constraints that constrain the system. Another important advantage of this algorithm is that it gives the optimum system cost without necessarily finding the optimal values of the parameters. Thus, a planner can evaluate the economic desirability of a proposed project immediately without working out the complete design. 11 ------- SECTION III INTRODUCTION Water resource development projects in the past ten years have become rapidly more numerous and costly. It soon had become apparent that an accurate appraisal of the worth of a single project could no longer be made on an individual basis. Rather, each project for resource develop- ment can be planned and designed correctly only when it is considered as a part of a larger system of projects in the region of development. When this is done, the expenditure of funds for project development can be made on the basis of how the individual project will contribute to the overall develop- ment of the entire region. Because of the shortness of water supply, the inter- action between supplies, and the high cost of project development, it is necessary for planning decisions regarding the size and scope of reservoir development to be the best possible ones. Since water is a limited resource, and our populations and industries are expanding rapidly, this planning represents a vital problem of immense proportions; Texas alone will spend several billion dollars on reservoir construction in the next two decades. Development decisions of this type are made largely by subjective means at the present time, and there is little uniformity in reservoir planning. The inter- action analyses employed in this research provide methods of solution to water development problems which should allow for uniform and objective decisions. The earliest pioneering work in water resource systems and optimization work was carried out in the Harvard Water Program (Maass, 1962). Attempts have been made to use optimization techniques in water resources planning and system design; the greatest success was obtained using a simulation technique. Indications of reported research of the Harvard Water Program (Huffschnidt,(11)) imply that simulation still was being used in the detailed, final stage optimization of a given water resource system. Research also was being directed toward use of other techniques such as linear programming and "rough simulation" for preliminary planning studies and to provide starting points for simulation operations. Hall and Buras (9) were first to ------- propose the application of dynamic programming to the optimization of reservoir systems. Dynamic programming has the advantage of effecting the decomposition of a complex problem into a series of less complex problems. It has been applied by Hall and others (see for example Hall, 7, 8) to a number of water resource optimization problems. Particularly in preliminary planning studies involving the sizing of proposed reservoirs within a river system, dynamic programming would appear to be the most useful optimization technique. Unfortunately, it cannot be applied directly, and hence, important modifications of the original algorithm were necessary, as described later in this report. Most of the prior work attempted in the analysis of water resource systems had made use either of simulation or linear programming, although there are many drawbacks to gaming, and the system functions which occur are actually highly non-linear. Simulation complicates the problem by attempting to solve say a twenty variable problem, whereas the research described in this report employs newer techniques to decompose such a previous problem into ten 2-variable problems. Some attempts had been made to apply dynamic programming to this type of problem, using time as the sole state variable. This meant that no state variables were available for coupling the reservoirs into an interdependent system of interacting stages. No analysts had tried to handle more than one decision variable at each stage of the system, nor had anyone attempted the analysis of any branched river basin systems. However, any realistic problem will certainly require more than one decision variable at each stage, and will contain several branched inputs, so that serial optimization methods are not directly applicable. The rationale behind the approach made in this project was that of avoiding sub-optimization in the determination of the size and location of reservoirs in a river basin system. Such suboptimal planning results when a reservoir design does not take into account the interacting between each reservoir and all downstream reservoirs. These interacting effects are actually the predominant characteristics to be considered in the analysis of any river basin system. If all couplings are ignored, and each reservoir is treated as though it were isolated from all others in the system, a serious suboptimization will result. ------- The specific aims of this research were first, to develop further the nonserial multistage techniques which are now the mathematical optimization methods most applicable to the field of water resource planning. Secondly, it was proposed to investigate the potential application of two other new methods. These are the discrete maximum principle, and geometric programming, the latter being the most recent optimization technique yet developed. These appeared to offer the most powerful solution procedures available when the number of state variables exceeds the limit which can be handled by the recursive dynamic programming approach. Both methods, however, have certain important limitations which were not obvious at the onset of this project, and which have not been discussed in the literature. 407-496 0-70-2 ------- SECTION IV DISCUSSION AND RESULTS This research project was originally approved for the three year period, September 1, 1967 through August 31, 1970, and procedures for carrying out the proposed research were planned accordingly. Unfortunately, funding for the project was terminated on August 31, 1968, after only one year of work had been underway. At that time, the position of the work was reviewed in order to determine what might be done to salvage as much as possible out of the original proposed three-year research program. Although significant progress had been made along the lines suggested in the application for continuation support, the loss of funding prevented two graduate student assistants from continuing on the project. Fortunately, uncommitted funds from the initial year were used to support the project for one additional year. Although this unexpended balance was employed to minimize the dislocation resulting from the unexpected grant termination, the funds available were clearly insufficient to do more than tie up some loose ends. The work proceeded in the direction initially established by the research reported in the paper, "Superposition in Branching Allocation Problems", by C. S. Beightler, D. B. Johnson, and D. J. Wilde, published in the August 1965 issue of the Journal of Mathematical Analysis and Applications. This work was prompted in turn by an earlier paper, "Optimization of Multistage Cyclic and Branching Systems by Serial Procedures", by R. Aris, G. L. Nemhauser, and D. J. Wilde, (A. I. Ch. E. Journal. November, 1964), which presented the first practical computational method for optimizing branched multistage systems. Since all river basin systems are actually comprised of branched inputs, this paper had particular ------- importance for those who deal specifically with the real problem of determining the size and location of proposed reservoir sites in such systems. The algorithm had the unfortunate characteristic, however, of requiring that an optimization be carried out simultaneously over two variables at each junction point where a branch joins the system network. Most of the real problems in this field require that tabular data be used in original form when solving the problem, and this requirement usually makes the two-variable optimization steps totally infeasible. In general, multistage optimization problems arise from a study of systems which are composed of a sequence of interrelated stages, at each of which a decision must be made. The decision at each stage determines the return (usually a profit of cost) at that stage, as well as the input to the next stage, thus affecting the circumstances under which all subsequent systems decisions must be made. The multistage problem is to find the optimal sequence of decisions which extremizes (maximizes or minimizes) the sum of all the returns. This is a difficult problem because the decisions made at any stage, although they may optimize the return at that particular stage, may affect the inputs to all subsequent stages in a disadvantageous way, leading to a non-optimal return for the system as a whole. Thus the stages are coupled together by their dependence on one another, and the optimal policy (sequence of decisions) for an N stage system involves the solution of an N dimensional problem. For a system having a simple serial structure, in which the stages are linked in a straight line, the method of dynamic programming has been used to reduce the dimensionality of the problem and render it amenable to analysis. This method, developed by Bellman (4), is a decomposition technique which converts one N-dimensional problem into N one-dimensional problems that can then be solved sequentially. These N problems, taken together, are equivalent to the original problem, and their solution determines the optimal set of decisions for the more complex problem. Dynamic programming thus takes advantage of the structure of the problem and is an efficient solution algorithm whenever that structure involves simple units in series having no more than two decision variables associated with each unit. The discrete version of Pontryagin's maximum principle (14) is another method quite similar to dynamic programming, as are suitable adaptations of the calculus of variations. Modifications of these techniques can often be used to eliminate some of the difficulties associated with high dimensionality either in the number of ------- decision variables at each stage or in the number of parameters required to specify the input to the next stage. Powerful as these methods are, however, they generally apply only to serial systems; if any feedback or crosslinkage from one stage to another destroys the serial structure, these techniques cannot be applied without considerable care. As a result, some researchers had attempted to extend the partial optimization approach exemplified by dynamic programming and the maximum principle to systems with branches and loops, thus greatly widening the scope of application of optimization theory. Fan and Wang (6) had shown how to adapt the maximum principle to cyclic structures, and Jackson (12) had extended variational methods to both cyclic and branching systems. Aris, Nemhauser, and Wilde (1) introduced the concept of a cut state to make possible the decomposition of cyclic and branched systems into equivalent serial ones solvable by serial procedures. Under favorable circumstances, their cut states could be directed tab their optimum values by efficient optimum seeking methods, a^procedure that is not possible for ordinary state variables. Beightler, Johnson, and Wilde (2) developed a superposition principle which is valid for linear allocation problems. This principle permitted superposition of optimal policies for ordinary serial dynamic programming problems formed from the branches of the larger problem, but was applicable only to systems which could be represented by linear functions at every stage. Efforts to extend this superposition principle to more general functions have not met with success. In fact, our work here at The University of Texas, using convex return functions and linear transitions, has proved that superposition cannot be employed on even this weak an extension of the fully linear case. It was evident that an entirely new approach was needed to the solution of the general non-serial multistage problem. The research supported by this grant produced just such a new approach, in the form of an algorithm which replaces the non-serial system with an equivalent serial structure, which can then be solved by the standard dynamic programming algorithm. This method is called branch compression (see i), since it effectively compresses an entire branch, consisting of several stages, into one psuedo-stage. The importance of this result is that any number of converging branches can be compressed into psuedo-stages which are then combined to ------- form an equivalent serial system. Therefore, this method of decomposition permits an entire converging branch multi- stage river basin system to be solved as a sequence of one-state, one-decision problems, just as if the system were serial. Furthermore, these results hold for any return or transition functions whatsoever and, in particular, they permit these functions to be given in tabular form. The resulting reduction in dimensionality makes possible the solution of the complex problems of reservoir design which were previously not amenable to analysis. The fundamental problem in determining the size and location of reservoirs in a river basin system is that of taking into account the interacting effects between a given reservoir and all those downstream. In this system, each stage corresponds to a potential reservoir site, and the stage decision is the size (possibly zero) of the reservoir to be built at that site. Each decision affects not only the costs and economic benefits to be derived at the given site, but also the circumstances (flow rate, which is the state of the system at each stage) under which all decisions at downstream sites must be made. It is this latter effect that makes the dynamic programming approach so attractive, since it takes these stage couplings into account at each step of the optimization process. If all couplings are ignored, and each reservoir treated as though it were isolated from all others in the system, a serious suboptimization would result. With the development of the branch compression technique, dynamic programming can now be applied directly to all branched multistage systems. Publication (iv) reports the successful introduction of stochastic variables into a serial multistage system. This will allow the handling of flow data in probabilistic form, when combined with the branch compression method for serializing a river basin system. Previously, only deterministic inputs were used in the dynamic programming formulation, so that flow data had to be introduced in the form of average rates. Indeed, the algorithm described in this paper appears to be the correct technique to use for all stochastic flow problems, and should replace the numerous simulation methods which have been proposed. These methods unduly complicate the problem, and can produce answers which are in error by large, but unknown, amounts. It is hoped that this new technique will be widely adopted and will supplant much of the questionable simulation studies now appearing in the water resources literature. ------- The theoretical work developed in the above publications was extended and applied to an example problem in the paper, "Design of an Optimal Branched Allocation System", which appeared in the Journal of Industrial and Engineering Chemistry (see ii). Using non-linear functions and numerical data, an example problem was presented and solved analytically. Then, this same problem was solved using a direct-search optimization method at each stage of the non-serial dynamic programming example problem. This method was incorporated into a computer program which was detailed in the paper through a flow chart. This program can be used to solve any non-serial multistage decision problem and is currently being rewritten to take advantage of recent advances in computational efficiency provided by the CDC 6600 computer system at The University of Texas . The new program will also have the ability to handle a larger number of both converging and diverging branches, so as better to describe a typical river basin system. Hopefully, running times will be decreased using this new program, for it is our intention to apply this code to the solution of some rather large-scale systems. The older program did have the disadvantage of consuming large amounts of expensive computer time when a fine grid (search step size) was employed. If the new code lives up to expectations, it will provide the most practical and efficient solution technique available for analyzing large water resource systems. Finally, this project produced the research reported in the paper, "Dynamic Programming in Water Resources Development" (see iii) which was presented at the National Symposium on the Analysis of Water Resource Systems in Denver, July 1968. This work described the application of non-serial dynamic programming to the optimal selection of a system interconnected reservoirs in a river basin system. In particular, the branch compression method was described in detail, and shown to be the best optimization technique available for this type of problem. The "cut-state" method of Aris, Nemhauser and Wilde for solving this same problem was also presented, and the numerical efficiencies of the two methods were compared. The paper pointed out the necessity for a mathematical model to take into account the intercoupled staging structure of the system, in which the output from each reservoir provides an input to all downstream reservoirs. The result of this work has been the development of a quite realistic mathematical model of a 8 ------- fairly general river basin system, into which current and historical flow data can be introduced to check the optimality of a presently existing system, as well as the nature of any modifications which must be made to the . computer program. The ultimate purpose of the program is the prediction of optimal reservoir dimensions and locations needed to produce an overall optimum water resource system. For this purpose, projected flow data would be used in the model, for both average and stochastic flows. Due to the abrupt termination of this project, the computer program which carries out the computational work of the mathematical model was not finished, so that a test of the model was not made. Hopefully, this program can be completed in the near future as research support monies become available. Also uncompleted was the projected work of applying Geometric Programming to water resource systems. The operating or capital cost of a single component of a system is often proportional to powers of certain key design parameters. Although changing technology, economic conditions, and geographic factors may affect the proportionality constants as time passes, the exponents often are fixed by invariant physical laws. Suppose the total cost of a river basin system to be the sum of such cost terms. The conventional way to find the optimum design parameter values would be to solve the simultaneous non-linear equations obtained by setting the first partial derivatives of the cost function equal to zero? a long, complicated, and not always successful procedure. Duffin and Zener (5, 15, 16) discovered a faster, more elegant approach which requires the optimization only of a much simpler "dual function." In favorable cases the method (called Geometric Programming) gives the optimum by inspection. But more important even than this considerable computational advantage is the fact that Geometric Programming shows that at the optimum, the fractional contribution of each term to the total cost depends only on the exponents of the parameters— not at all on the cost coefficients. Thus, even in the face of changing conditions one can still develop rigorous invariant rules for the optimal fractions of total cost to be allocated to various system components. A final advantage of Geometric Programming is that it gives the optimum cost without necessarily finding the optimal values of the parameters. Thus, a planner can evaluate the economic desirability of a proposed project immediately without working out the complete design. The technique has recently been expanded so that polynomial ------- inequalities can be handled. It had been proposed to study this powerful theory to see where it could be applied to water resource system design. There are bound to be certain places where the model is not immediately applicable, and research is needed either to develop suitable approximations or to revise and extend the method. Where applications are possible, rigorous design rules would be assembled which would apply to all similar river basin systems. Work is still proceeding towards a further development of the basic theory of Geometric Programming, but at present, applications of the method to water resource systems have not been satisfactorily accomplished. The major disadvantage of Geometric Programming and the Discrete Maximum Principle, another modern optimization method studied in this project, is that the objective function and all system constraints must be expressed as analytic functions. Indeed, these functions must all be continuous and possess continuous first partial derivatives. Such functions are not normally available to the analyst, who must then attempt to fit such a function to the historical data that describe the system. The strongest recommendation for the use of the dynamic programming algorithms is that such data need not be approximated by fitted functions, but rather may be used directly in either graphical or tabular form. 10 ------- SECTION V REFERENCES 1. Aris, R., G. L. Nemhauser, and D. J. Wilde, "Optimization of Multistage Cyclic and Branching Systems by Serial Procedures," A.I.Ch. E.Journal, 10, pp. 913-919 (Nov. 1964) 2. Beightler, C.S., D.B. Johnson, and D. J. Wilde, "Superposition in Branching Allocation Problems," journal of Mathematical Analysis and Applications, 10, (May, 1965). 3. Beightler, C.S., and L. G. Mitten, "Design of an Optimal Sequence of Interrelated Sampling Plans," Journal of the American Statistical Association, 59, pp. 96-104, (March, 1964). 4. Bellman, R., and S. Dreyfus, "Applied Dynamic Programming," Princeton, N. J.; Princeton University Press, 1962. 5. R. Duffin, "Dual Programs and Minimum Cost," Soc. Ind. Appl. Math, journal 10, pp. 119-123. 6. Fan, L. T., and C. S. Wang, "Optimization of Multistage Processes with Product Recycle," Chemical Engineering Science, 19, pp. 86-87 (Jan. 1964) . 7. Hall, Warren A., "Aqueduct Capacity Under an Optimum Benefit Policy," Trans. Am. Soc. Civil Engrs., 128, part III, pp. 162-172 (1963). 8. Hall, Warren A., "Optimum Design of Multiple-Purpose Reservoirs," J. Hydraulics Div. Am. Soc. Civil Engr., 90 (HY4), pp. 141-149 (1964). 9. Hall, Warren A., and Nathan Buras, "The Dynamic Programming Approach to Water Resource Development," J. Geophys. Res., 66(2), pp. 517-5.20 (1961). 10. Howard, Ronald A., "Dynamic Programming," Man ag emen t Sci., 12 (5), pp. 317-348 (1966). 11. Huffschmidt, Maynard M., "Field Level Planning of Water Resource Systems," Water Resources Res., 1(2), pp. 147-163 (1965). 11 ------- 12. Jackson, R. "Some Algebraic Properties of Optimization Problems in Complex Chemical Plants", Chem. Eng. Sci., 9, pp. 19-31 (1964). 13. Maass, Arthur, et al, Design of Water Resource Systems, Harvard University Press, Cambridge (1962). 14. Pontryagin, L. S., V. G. Boltyanskii, R. v. Gamkrelidze, and E. F. Mischenko, "The Mathematical Theory of Optimal Processe," translated by K. N. Trirogoff, New York: Interscience,(1962). 15. C. Zener, "A Mathematical Aid in Optimizing Engineering Designs," Proc. Nat. Acad. Sci.47, pp. 537-539 (1961). 16. C. Zener, and R. Duffin, "Optimization of Engineering Problems," Westinghouse Engineer, pp. 154-160 (Sept. 1964) 12 ------- SECTION VI PUBLICATIONS AND PATENTS i. Meier, W. L., and C. S. Heightler, "Branch Compression and Absorption in Nonserial Multistage Systems," Journal of Mathematical Analysis and Applications,21, No. 2, pp. 426-430 (1968). ii. Beightler, C. S., and W. L. Meier, "Design of an Optimal Branched Allocation System," Industrial and Engineering Chemistry, 60, No. 2, pp. 44-49 (1968). iii. Beightler, C. S., and W. L. Meier, "Dynamic Programming in Water Resources Development," Proceedings of the National Symposium on the Analysis of Water-Resource Systems, held in Denver, Colorado, July 1-3, 1968; pp. 64-71. iv. Beebe, J. H., C. S. Beightler, and J. P. Stark, "Stochastic Optimization of Production Planning," Operations Research, 16, No. 4, pp. 799-818 (1968). 13 ------- .Accession Number Subject Field i Groi>r> 06 A SELECTED WATER RESOURCES ABSTRACTS INPUT TRANSACTION FORM c Organization* Federal Water Quality Administration .AT"; Use of New Analytical Methods for Water Resource Development 10 Authors) C. S. Beightler 22 , , Date 9/70 12 Pages 13 ix 1 Project Number 16110 FZE 21 i c Contract Number Note Citation The University of Texas at Austin 23 Descriptors (Starred First) *River Basin Development, *0ptimum Development Plans, ^Dynamic Programming Reservoir Design, Reservoir Sites 25 Identifiers (Starred First) 27 Abstract Studies were made to determine the feasibility of applying recently developed analtyical techniques to the problem of planning for optimal water resource development. An optimal plan with regard to the size and location of proposed reservoirs was taken to be that physical configuration which provided the greatest net economic benefit to the people of the region while meeting future water needs. This research was aimed at providing an improvement over the sub-optimal planning techniques of the past which did not take into account the interacting effects which exist between each reservoir and all downstream reservoirs. These interacting effects are actually the predominant characteristics to be considered in the design of a system of reservoirs in any river basin, and cannot be ignored. For the purpose of formulating a mathematical model for this type of problem, a number of recently developed optimization techniques were studied. The best formulation was found to be that which treated the reservoir system design as a branched multistage decision process. In such processes, the decisions made at each stage (potential reservoir site) affect the circumstances under which all subsequent decisions in the sytem must be made. The intercoupled staging structure of this process was then exploited by means of the nonserial dynamic programming algorithms developed in the course of this research project. These algorithms are effectively decomposition techniques which break down the nonserial (i.e. branched) process into an equivalent serial process that is amenable to solution through ordinary dynamic programming methods. Abstractor Dr. C. S. Beightler Institution The University of Texas at WRjt02 (REV. OCT. 1968) WRSIC SEND TO: WATER RESOURCES SCIENTIFIC INFORMATION CENTER U S. DEPARTMENT OF THE INTERIOR WASHINGTON, D.C. 20240 U. S. GOVERNMENT PRINTING OFFICE : 1970 O - 401-486 ------- |