×

A mixed-integer simulation-based optimization approach with surrogate functions in water resources management. (English) Zbl 1419.90007

Summary: Efficient and powerful methods are needed to overcome the inherent difficulties in the numerical solution of many simulation-based engineering design problems. Typically, expensive simulation codes are included as black-box function generators; therefore, gradient information that is required by mathematical optimization methods is entirely unavailable. Furthermore, the simulation code may contain iterative or heuristic methods, low-order approximations of tabular data, or other numerical methods which contribute noise to the objective function. This further rules out the application of Newton-type or other gradient-based methods that use traditional finite difference approximations. In addition, if the optimization formulation includes integer variables the complexity grows even further. In this paper we consider three different modeling approaches for a mixed-integer nonlinear optimization problem taken from a set of water resources benchmarking problems. Within this context, we compare the performance of a genetic algorithm, the implicit filtering algorithm, and a branch-and-bound approach that uses sequential surrogate functions. We show that the surrogate approach can greatly improve computational efficiency while locating a comparable, sometimes better, design point than the other approaches.

MSC:

90B05 Inventory, storage, reservoirs
90C11 Mixed integer programming

Software:

KanGAL; DACE; MINLP; SNOPT; FEFLOW
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahlfeld DP, Mulligan AE (2000) Optimal design of flow in groundwater systems. Academic Press, San Diego
[2] Audet C, Dennis J (2001) Pattern search algorithms for mixed variable programming. SIAM J Optim 11:573–594 · Zbl 1035.90048 · doi:10.1137/S1052623499352024
[3] Battermann A, Gablonsky J, Patrick A, Kelley CT, Kavanagh KR (2002) Solution of a groundwater control problem with implicit filtering. Optim Eng 3:189–199 · Zbl 1042.76012 · doi:10.1023/A:1020967403960
[4] Bussieck M, Pruessner A (2003) Mixed-integer nonlinear programming. SIAG/OPT Newsl Views News 14(1):19–22
[5] Carter RG, Gablonski JM, Pattrick A, Kelley CT, Eslinger OJ (2001) Algorithms for noisy problems in gas transmission pipeline optimization. Optim Eng 2:139–157 · Zbl 1079.90624 · doi:10.1023/A:1013123110266
[6] Choi T, Gilmore P, Eslinger OJ, Patrick A, Kelley C, Gablonsky J (1999) IFFCO: Implicit Filtering for Constrained Optimization, Version 2, Technical Report CRSC-TR99-23, Center for Research in Scientific Computation
[7] Cieniawski SE, Eheart JW, Ranjithan S (1995) Using genetic algorithms to solve a multiobjective groundwater monitoring problem. Water Resour Res 31(2):399–409 · doi:10.1029/94WR02039
[8] Cuncha M (1999) On solving aquifer management problems with simulated annealing algorithms. Water Resour Managem 13:153–169 · doi:10.1023/A:1008149626428
[9] Deb K (2000) An efficient constraint handling method for genetic algorithms. Comput Methods Appl Mech Eng 186(2–4):311–338 · Zbl 1028.90533 · doi:10.1016/S0045-7825(99)00389-8
[10] Deb K (2003) KanGal Homepage, Indian Institute of Technology Kanpur. http://www.iitk.ac.in/kangal
[11] Deb K, Agrawal RB (1995) Simulated binary crossover for continuous search space. Complex Syst 9:115–148 · Zbl 0843.68023
[12] Deb K, Goel T (2001) Controlled Elitist Non-dominated sorting genetic algorithms for better convergence. In: Zitler E, Deb K, Thiele L, Coello-Coello C, Corne D (eds.) Proceedings of the first international conference on evolutionary multi-criterion optimization EMO 2001, pp 67–81
[13] Deb K, Pratap A, Agarwal S, Meyarivan T (2000) A fast and elitist multi-objective genetic algorithm: NSGA-II, KanGal Report 200001, Indian Institute of Technology Kanpur, Kanpur, India
[14] Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197 · Zbl 05451853 · doi:10.1109/4235.996017
[15] Diersch H-J (1998) Interactive, graphics-based finite-element simulation system FEFLOW for modeling groundwater flow contaminant mass and heat transport, Users Manual, WASY GmbH, Berlin
[16] Espinoza F, Minsker BS, Goldberg DE (2005) Adaptive hybrid genetic algorithm for groundwater remediation design. Water Resour Plan Manage 131(1):14–24 · doi:10.1061/(ASCE)0733-9496(2005)131:1(14)
[17] Floudas CA (1999) Deterministic global optimization theory, methods and applications. Kluwer Academic, Dordrecht
[18] Fowler KR, Kelley CT, Kees CE, Miller CT (2004a) A hydraulic capture application for optimal remediation design. In: Miller, Farthing, Gray, and Pinder (eds.) Proceedings of the 15th international conference on computational methods in water resources (CMWR XV), 13–17 June 2004, Chapel Hill, North Carolina. Computational methods in water resources, vol 2. Developments in water science, vol 55, pp 1149–1157
[19] Fowler KR, Kelley CT, Miller CT, Kees CE, Darwin RM, Reese JP, Farthing MW, Reed MSC (2004b) Solution of a well-field design problem with implicit filtering. Optim Eng 5:207–233 · Zbl 1093.90541 · doi:10.1023/B:OPTE.0000033375.33183.e7
[20] Fowler K, Reese J, Kees C, Dennis JE Jr, Kelley C, Miller C, Audet C, Booker A, Couture G, Darwin R, Farthing M, Finkel D, Gablonsky J, Gray G, Kolda T (2008) A comparison of derivative-free optimization methods for water supply and hydraulic capture community problems. Adv Water Resour 31(5):743–757 · doi:10.1016/j.advwatres.2008.01.010
[21] Gill PE, Murray W, Saunders MA (2006) User’s guide for SNOPT 7.1: a Fortran package for large-scale nonlinear programming. Report NA 05-2, Department of Mathematics, University of California, San Diego
[22] Gilmore P, Kelley CT (1995) An implicit filtering algorithm for optimization of functions with many local minima. SIAM J Optim 5:269–285 · Zbl 0828.65064 · doi:10.1137/0805015
[23] Grossmann IE (2002) Review of nonlinear mixed-integer and disjunctive programming techniques. Optim Eng 3:227–252 · Zbl 1035.90050 · doi:10.1023/A:1021039126272
[24] Hemker T, Fowler KR, von Stryk O (2006a) Derivative-free optimization methods for handling fixed costs in optimal groundwater remediation design. In: Proc of the CMWR XVI–Computational Methods in Water Resources
[25] Hemker T, Glocker M, De Gersem H, von Stryk O, Weiland T (2006b) Mixed-integer simulation-based optimization for a superconductive magnet design. In: Proceedings of the sixth international conference on computation in electromagnetics. Aachen, Germany
[26] Hsiao C, Chang L (2002) Dynamic optimal groundwater management with inclusion of fixed costs. J Water Resour Plan Manage 128:57–64 · doi:10.1061/(ASCE)0733-9496(2002)128:1(57)
[27] Huang C, Mayer AS (1997) Pump-and-treat optimization using well locations and pumping rates as decision variables. Water Resour Res 33(5):1001–1012 · doi:10.1029/97WR00366
[28] Koehler JR, Owen A (1996) Computer experiments. Handb Stat 13:261–308 · Zbl 0919.62089 · doi:10.1016/S0169-7161(96)13011-X
[29] Lall U, Santini MD (1989) An optimization model for unconfined stratified aquifer systems. J Hydrol 111:145–162 · doi:10.1016/0022-1694(89)90257-6
[30] Lophaven N, Nielsen HB, Sondergaard J (2002) DACE, a Matlab Kriging toolbox. Technical Report IMM-TR-2002-12, IMM
[31] Maskey S, Jonoski A, Solomatine DP (2002) Groundwater remediation strategy using global optimization algorithms. J Water Resour Plan Manage 128(6):431–440 · doi:10.1061/(ASCE)0733-9496(2002)128:6(431)
[32] Mattot SL, Bartelt-Hunt SL, Rabideau AJ, Fowler KR (2006) Application of heuristic optimization techniques and algorithm tuning to multi-layered sorptive barrier design. Environ Sci Technol (to appear)
[33] Mayer AS, Kelley CT, Miller CT (2002a) Optimal design for problems involving flow and transport in saturated porous media. Adv Water Resour 12:1233–1256 · doi:10.1016/S0309-1708(02)00054-4
[34] Mayer AS, Kelley CT, Miller CT (2002b) Optimal design for problems involving flow and transport in saturated porous media. Electronic Supplement. Adv Water Resour 12:1233–1256 · doi:10.1016/S0309-1708(02)00054-4
[35] Mays LW (1997) Optimal control of hydrosystems. Dekker, New York
[36] McDonald M, Harbaugh A (1988) A modular three dimensional finite difference groundwater flow model. In: U.S. geological survey techniques of water resources investigations
[37] McKinney DC, Lin M-D (1995) Approximate mixed-integer nonlinear programming methods for optimal aquifer remediation design. Water Resour 31:731–740 · doi:10.1029/94WR02851
[38] Nicklow JW (2000) Discret-time optimal control for water resources engineering and management. Int Water Resour Assoc 25(1):89–95
[39] Papadopoulou MP, Pinder GF, Karatzas G (2003) Enhancement of the outer approximation method for the solution of concentration constrained optimal-design groundwater-remediation problems. Water Resour Res 39(7):1185 · doi:10.1029/2002WR001541
[40] Reed P, Minsker B, Goldberg DE (2000) Designing a competent simple genetic algorithm for search and optimization. Water Resour Res 36(12):3757–3761 · doi:10.1029/2000WR900231
[41] Ritzel BJ, Eheart JW, Ranjithan S (1994) Using genetic algorithms to solve a multiple objective groundwater pollution containment problem. Water Resour Res 30(5):1589–1604 · doi:10.1029/93WR03511
[42] Sacks J, Schiller SB, Welch WJ (1989) Design for computer experiments. Technometrics 31:41–47 · doi:10.2307/1270363
[43] Sasena MJ (2002) Flexibility and efficiency enhancements for constrained global design optimization with Kriging approximations. Ph.D. thesis, University of Michigan
[44] Sayeed M, Mahinthakumar G (2005) Efficient parallel implementation of hybrid optimization approaches for solving groundwater inverse problems. J Comput Civ Eng 19(4):329–340 · doi:10.1061/(ASCE)0887-3801(2005)19:4(329)
[45] Shieh H, Peralta R (2005) Optimal in situ bioremediation design by hybrid genetic algorithm and simulated annealing. Water Resour Plan Manag 131(1):67–78 · doi:10.1061/(ASCE)0733-9496(2005)131:1(67)
[46] Talbi E (2002) A taxonomy of hybrid metaheuristics. J Heuristics 8:541–563 · doi:10.1023/A:1016540724870
[47] Watkins D Jr, McKinney DC (1998) Decomposition methods for water resources optimization models with fixed costs. Adv Water Resour 21(4):261–324 · doi:10.1016/S0309-1708(96)00063-2
[48] Zitzler E, Deb K, Thiele L (2000) Comparison of multiobjective evolutionary algorithms: empirical results. Evol Comput J 8(2):173–195 · Zbl 05412936 · doi:10.1162/106365600568202
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.