Abstract
Optimization of multi-reservoir systems operations is typically a very large scale optimization problem. The following are the three types of optimization problems solved using linear programming (LP): (i) deterministic optimization for multiple periods involving fine stage intervals, for example, from an hour to a week (ii) implicit stochastic optimization using multiple years of inflow data, and (iii) explicit stochastic optimization using probability distributions of inflow data. Until recently, the revised simplex method has been the most efficient solution method available for solving large scale LP problems. In this paper, we show that an implementation of the Karmarkar's interior-point LP algorithm with a newly developed stopping criterion solves optimization problems of large multi-reservoir operations more efficiently than the simplex method. For example, using a Micro VAX II minicomputer, a 40 year, monthly stage, two-reservoir system optimization problem is solved 7.8 times faster than the advanced simplex code in MINOS 5.0. The advantage of this method is expected to be greater as the size of the problem grows from two reservoirs to multiples of reservoirs. This paper presents the details of the implementation and testing and in addition, some other features of the Karmarkar's algorithm which makes it a valuable optimization tool are illuminated.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adler, I.; Karmarkar, N; Resende, M.G.C.; Veiga, G. 1986/1987a: An implementation of Karmarkar's algorithm for linear programming. Working Paper, Operations Research Center, University of California, Berkely, CA. (Under review in Mathematical Programming).
Adler, I; Karmarkar, N; Resende, M.G.C.; Veiga, G. 1987b: Data structures and programming techniques for efficient implementation of Karmarkar's algorithm, Working Paper, Operations Research Center, University of California, Berkely, CA.
Aronson, J.E; Chen, B.D. 1986: A forward network simplex algorithm for solving multiperiod network flow problems. Naval Research Logistics Quarterly, 33, 445–467.
Bazaraa, M.S.; Jarvis, J.J. 1977: Linear Programming and Network Flows, John Wiley & sons Inc., Toronto.
Bernard, B. 1980: Some numerical methods in stochastic LP under risk and uncertainty, in Stochastic Programming, Ed. Dempster, M.A.H., Academic Press, 169–205.
Best, M.J.; Ritter, K. 1985: Linear Programming: Active Set Analysis and Computer Programs, Prentice Hall Inc., NJ.
Corbu, I; Nix, G.A.; Rassam, J.C. 1988: Utilization of the Ottawa river regulation modelling system (MORRO), Proceedings of Hydropower Conference, Colorado.
Ferris M.C.; Philpott, A.B. 1988: On the performance of Karmarkar's algorithm. J. Opl. Res. Soc., 39(3), 257–270.
George, A.; Ng, E. 1984: A new release of SPARSPAK-The Waterloo sparse matrix package, ACM SIGNUM Newsletter 19(4), 9–13.
Gill, P.E.; Murray, W.; Saunders, M.A. 1986: On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method, Math. Programming, 36, 183–209.
Golub, G.H.; Van Loan, C.F. 1983: Matrix Computations, The John Hopkins Press, Baltimore.
Gottfried, B.S.; Weisman, J. 1973: Introduction to Optimization Theory, Prentice-Hall Inc., NJ.
Karmarkar, N. 1984: A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373–395.
Klee, V; Minty, G.L. 1972: How good is the simplex algorithm? in Inequalities III, Ed. O.Shisha, Academic Press, New York, 159–179.
Kozlov, A. 1985: The Karmarkar algorithm: Is it for real?, SIAM News, 18(6), 1–4.
Loucks, D.P.; Stedinger, J.R.; Haith, D. 1981: Water Resources Systems Planning and Analysis, Prentice Hall, NJ.
Lustig, I.J. 1985: A practical approach to Karmarkar's algorithm, Technical Report SOL 85-5, Dept. of Op. Res., Stanford University, CA.
Monma, C.L.; Morton, A.J. 1987: Computational experience with a dual affine variant of Karmarkar's method for linear programming, Oper. Res. Letters, 6(6), 261–267.
Murtaugh, B.A., Saunders, M.A. 1983: MINOS 5.0 User's Guide, Tech. Rep. SOL 83-20, Stanford University, CA.
Ponnambalam, K.; Vannelli, A. 1988: New starting and stopping steps for the dual affine variant of Karmarkar's method, Working Paper, Dept. of Electrical Engg., University of Waterloo, Canada.
Strazicky, B. 1980: Some results concerning an algorithm for the discrete recourse problem, in Stochastic Programming, Ed. Dempster, M.A.H., Academic Press, 263–274.
Syslo, M.M.; Deo, N.; Kowalik, J.S. 1983: Discrete Optimization Algorithms: With Pascal Programs, Prentice-Hall, NJ.
Tomlin, J. A. 1987: An experimental approach to Karmarkar's projective method for linear programming, Math. Programming, 31, 175–191.
Vannelli, A. 1988: An interior point method for solving the global routing problem, Submitted to IEEE Custom Integrated Circuits Conference, San Diego, CA, May 15–19.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ponnambalam, K., Vannelli, A. & Unny, T.E. An application of Karmarkar's interior-point linear programming algorithm for multi-reservoir operations optimization. Stochastic Hydrol Hydraul 3, 17–29 (1989). https://doi.org/10.1007/BF01543425
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01543425