×

Approximating a linear multiplicative objective in watershed management optimization. (English) Zbl 07619270

Summary: Implementing management practices in a cost-efficient manner is critical for regional efforts to reduce the amount of pollutants entering the Chesapeake Bay. We study the problem of selecting a subset of practices that minimizes pollutant load – subject to budgetary and environmental constraints – as simulated in a widely used regulatory watershed model. Mimicking the computation of pollutant load in the regulatory model, we formulate this problem as a continuous optimization model with a linear multiplicative objective function and linear constraints. To lay the groundwork for incorporating additional stakeholder requirements in the future, especially those that would require integer variables, we present and study a continuous linear optimization model that approximates the nonlinear model. The linear model, which requires an exponential number of variables, arises naturally as an alternative model for the same underlying physical process. We examine the theoretical behavior of these optimization models and investigate restrictions of the linear model to handle its large number of variables. Through extensive computational tests on real and randomly generated instances, we demonstrate that the linear model and its restrictions provide optimal solutions close to those of the nonlinear model in practice, despite poor approximation properties in the worst case. We conclude that the linear model – together with our approach to handling its large number of variables – provides a viable framework from which to extend the optimization model to better meet the needs of the Chesapeake Bay watershed management stakeholders.

MSC:

90Bxx Operations research and management science

Software:

CAST; GitHub; GLPK; Ipopt
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arabi, M.; Govindaraju, R. S.; Hantush, M. M., Cost-effective allocation of watershed management practices using a genetic algorithm, Water Resources Research, 42, 10, 1-14 (2006)
[2] Bennett, K. P.; Mangasarian, O. L., Bilinear separation of two sets in n-space, Computational Optimization and Applications, 2, 3, 207-227 (1993) · Zbl 0795.90060
[3] Benson, H.; Boger, G., Outcome-space cutting-plane algorithm for linear multiplicative programming, Journal of Optimization Theory and Applications, 104, 2, 301-322 (2000) · Zbl 0962.90024
[4] Bertsimas, D.; Tsitsiklis, J., Introduction to linear optimization (1997), Athena Scientific
[5] Bever, A. J.; Friedrichs, M. A.M.; Friedrichs, C. T.; Scully, M. E.; Lanerolle, L. W.J., Combining observations and numerical model results to improve estimates of hypoxic volume within the Chesapeake Bay, USA, Journal of Geophysical Research: Oceans, 118, 10, 4924-4944 (2013)
[6] Boesch, D. F., Barriers and bridges in abating coastal eutrophication, Frontiers in Marine Science, 6, 123 (2019)
[7] RR-83-19
[8] Bosch, D. J.; Wagena, M. B.; Ross, A. C.; Collick, A. S.; Easton, Z. M., Meeting water quality goals under climate change in Chesapeake Bay watershed, USA, JAWRA Journal of the American Water Resources Association, 54, 6, 1239-1257 (2018)
[9] Burn, D. H.; McBean, E. A., Optimization modeling of water quality in an uncertain environment, Water Resources Research, 21, 7, 934-940 (1985)
[10] Cai, X.; Vogel, R.; Ranjithan, R., Special issue on the role of systems analysis in watershed management, Journal of Water Resources Planning and Management, 139, 5, 461-463 (2013)
[11] Cardwell, H.; Ellis, H., Model uncertainty and model aggregation in environmental management, Applied Mathematical Modelling, 20, 2, 121-134 (1996) · Zbl 0848.90028
[12] Chesapeake Bay Program (2020). Chesapeake assessment and scenario tool (CAST) version 2019. https://cast.chesapeakebay.net/. Accessed November 2020.
[13] Cloern, J., Our evolving conceptual model of the coastal eutrophication problem, Marine Ecology Progress Series, 210, 223-253 (2001)
[14] Depetrini, D.; Locatelli, M., A FPTAS for a class of linear multiplicative problems, Computational Optimization and Applications, 44, 2, 275 (2009) · Zbl 1184.90165
[15] Devereux, O. H.; Rigelman, J. R., CAST: An online tool for facilitating local involvement in watershed implementation plans for the chesapeake bay total maximum daily load, Journal of Water Management Modeling, 22, 1-8 (2014)
[16] Dorneich, M. C.; Sahinidis, N. V., Global optimization algorithms for chip layout and compaction, Engineering Optimization, 25, 2, 131-154 (1995)
[17] https://books.google.com/books?id=WQ5SAAAAMAAJ
[18] http://nbn-resolving.de/urn:nbn:de:0297-zib-78023
[19] Gao, Y.; Xu, C.; Yang, Y., An outcome-space finite algorithm for solving linear multiplicative programming, Applied Mathematics and Computation, 179, 2, 494-505 (2006) · Zbl 1103.65065
[20] Geng, R.; Yin, P.; Sharpley, A. N., A coupled model system to optimize the best management practices for nonpoint source pollution control, Journal of Cleaner Production, 220, 581-592 (2019)
[21] Geoffrion, A. M., Solving bicriterion mathematical programs, Operations Research, 15, 1, 39-54 (1967) · Zbl 0173.21602
[22] Gitau, M. W.; Veith, T. L.; Gburek, W. J.; Jarrett, A. R., Watershed level best management practice selection and placement in the Town Brook watershed, New York, JAWRA Journal of the American Water Resources Association, 42, 6, 1565-1581 (2006)
[23] Giuffria, J. M.; Bosch, D. J.; Taylor, D. B.; Alamdari, N., Costs of water quality goals under climate change in urbanizing watersheds: Difficult Run, Virginia, Journal of Water Resources Planning and Management, 143, 9, 04017055 (2017)
[24] Hood, R. R.; Shenk, G. W.; Dixon, R. L.; Smith, S. M.; Ball, W. P.; Bash, J. O.; Zhang, Y. J., The Chesapeake Bay program modeling system: Overview and recommendations for future development, Ecological Modelling, 456, 109635 (2021)
[25] Hung, F.; Hobbs, B. F., How can learning-by-doing improve decisions in stormwater management? A Bayesian-based optimization model for planning urban green infrastructure investments, Environmental Modelling and Software, 113, 59-72 (2019)
[26] Jacobi, S. K.; Hobbs, B. F.; Wilcock, P. R., Bayesian optimization framework for cost-effective control and research of non-point-source sediment, Journal of Water Resources Planning and Management, 139, 5, 534-543 (2013)
[27] Jacoby, H. D.; Loucks, D. P., Combined use of optimization and simulation models in river basin planning, Water Resources Research, 8, 6, 1401-1414 (1972)
[28] Jiao, H.; Liu, S.; Chen, Y., Global optimization algorithm for a generalized linear multiplicative programming, Journal of Applied Mathematics and Computing, 40, 1, 551-568 (2012) · Zbl 1295.90082
[29] Jiao, H.-W.; Liu, S.-Y.; Zhao, Y.-F., Effective algorithm for solving the generalized linear multiplicative problem with generalized polynomial constraints, Applied Mathematical Modelling, 39, 23-24, 7568-7582 (2015) · Zbl 1443.90037
[30] Kaufman, D. E., Shenk, G. W., Bhatt, G., Asplen, K. W., Devereux, O. H., Rigelman, J. R., Ellis, J. H., Hobbs, B. F., Bosch, D. J., Van Houtven, G. L., McGarity, A. E., Linker, L. C., & Ball, W. P. (2021). Supporting cost-effective watershed management strategies for Chesapeake Bay using a modeling and optimization framework,. In revision.
[31] PMID: 25405490
[32] Kennedy, C. M.; Hawthorne, P. L.; Miteva, D. A.; Baumgarten, L.; Sochi, K.; Matsumoto, M.; Kiesecker, J., Optimizing land use decision-making to sustain Brazilian agricultural profits, biodiversity and ecosystem services, Biological Conservation, 204, 221-230 (2016)
[33] Kim, N. T.B.; Le Trang, N. T.; Yen, T. T.H., Outcome-space outer approximation algorithm for linear multiplicative programming, East West Math, 9, 01, 81-98 (2007) · Zbl 1162.90552
[34] Konno, H.; Kuno, T., Linear multiplicative programming, Mathematical Programming, 56, 1, 51-64 (1992) · Zbl 0761.90080
[35] Konno, H.; Shirakawa, H.; Yamazaki, H., A mean-absolute deviation-skewness portfolio optimization model, Annals of Operations Research, 45, 1, 205-220 (1993) · Zbl 0785.90014
[36] Kuno, T., A finite branch-and-bound algorithm for linear multiplicative programming, Computational Optimization and Applications, 20, 2, 119-135 (2001) · Zbl 0983.90075
[37] https://github.com/jon77lee/JLee_LinearOptimizationBook/blob/master/JLee.4.0.pdf 
[38] Lefcheck, J. S.; Orth, R. J.; Dennison, W. C.; Wilcox, D. J.; Murphy, R. R.; Keisman, J.; Batiuk, R. A., Long-term nutrient reductions lead to the unprecedented recovery of a temperate coastal region, Proceedings of the National Academy of Sciences, 115, 14, 3658-3662 (2018)
[39] Liebman, J. C.; Lynn, W. R., The optimal allocation of stream dissolved oxygen, Water Resources Research, 2, 3, 581-591 (1966)
[40] Limbrunner, J. F.; Vogel, R. M.; Chapra, S. C.; Kirshen, P. H., Comparison of linear and non-linear optimization models for storm water and non-point source pollution best management practice decision support, (Kabbes, K. C., World environmental and water resources congress 2007 (2007), American Society of Civil Engineers), 1-10
[41] Lintern, A.; McPhillips, L.; Winfrey, B.; Duncan, J.; Grady, C., Best management practices for diffuse nutrient pollution: Wicked problems across urban and agricultural watersheds, Environmental Science and Technology, 54, 15, 9159-9174 (2020)
[42] Makhorin, A. (2018). GNU linear programming kit. Free software foundation. http://www.gnu.org/software/glpk/glpk.html.
[43] Maling, K.; Heller, W.; Mueller, S., On finding most optimal rectangular package plans, 19th Design automation conference, 663-670 (1982), IEEE
[44] Maranas, C. D.; Androulakis, I.; Floudas, C.; Berger, A.; Mulvey, J., Solving long-term financial planning problems via global optimization, Journal of Economic Dynamics and Control, 21, 8-9, 1405-1425 (1997) · Zbl 0901.90016
[45] Maringanti, C.; Chaubey, I.; Popp, J., Development of a multiobjective optimization tool for the selection and placement of best management practices for nonpoint source pollution control, Water Resources Research, 45, 6 (2009)
[46] McGarity, A. E., Storm-water investment strategy evaluation model for impaired urban watersheds, Journal of Water Resources Planning and Management, 138, 2, 111-124 (2012)
[47] McGarity, A. E., Watershed systems analysis for urban storm-water management to achieve water quality goals, Journal of Water Resources Planning and Management, 139, 5, 464-477 (2013)
[48] Mulvey, J. M.; Vanderbei, R. J.; Zenios, S. A., Robust optimization of large-scale systems, Operations Research, 43, 2, 264-281 (1995) · Zbl 0832.90084
[49] Nicklow, J.; Reed, P.; Savic, D.; Dessalegne, T.; Harrell, L.; Chan-Hilton, A.; Zechman, E., State of the art for genetic algorithms and beyond in water resources planning and management, Journal of Water Resources Planning and Management, 136, 4, 412-432 (2010)
[50] Onishi, H.; Swanson, E. R., Effect of nitrate and sediment constraints on economically optimal crop production, Journal of Environmental Quality, 3, 3, 234-238 (1974)
[51] Pastori, M.; Udías, A.; Bouraoui, F.; Bidoglio, G., A multi-objective approach to evaluate the economic and environmental impacts of alternative water and nutrient management strategies in africa, Journal of Environmental Informatics, 29, 1 (2017)
[52] Pinckney, J. L.; Paerl, H. W.; Tester, P.; Richardson, T. L., The role of nutrient loading and eutrophication in estuarine ecology, Environmental Health Perspectives, 109, suppl 5, 699-706 (2001)
[53] Quesada, I.; Grossmann, I. E., Alternative bounding approximations for the global optimization of various engineering design problems, Global optimization in engineering design, 309-331 (1996), Springer · Zbl 0879.90189
[54] Revelle, C. S.; Loucks, D. P.; Lynn, W. R., Linear programming applied to water quality management, Water Resources Research, 4, 1, 1-9 (1968)
[55] Rodriguez, H. G.; Popp, J.; Maringanti, C.; Chaubey, I., Selection and placement of best management practices used to reduce water quality degradation in lincoln lake watershed, Water Resources Research, 47, 1, 1-13 (2011)
[56] Ryoo, H.-S.; Sahinidis, N. V., Global optimization of multiplicative programs, Journal of Global Optimization, 26, 4, 387-418 (2003) · Zbl 1052.90091
[57] Schaible, S.; Sodini, C., Finite algorithm for generalized linear multiplicative programming, Journal of Optimization Theory and Applications, 87, 2, 441-455 (1995) · Zbl 0839.90113
[58] Schwartz, S. S., Optimization and decision heuristics for Chesapeake Bay nutrient reduction strategies, Environmental Modeling and Assessment, 15, 5, 345-359 (2010)
[59] Shao, L.; Ehrgott, M., Primal and dual multi-objective linear programming algorithms for linear multiplicative programmes, Optimization, 65, 2, 415-431 (2016) · Zbl 1370.90254
[60] Somlyódy, L., Use of optimization models in river basin water quality planning, Water Science and Technology, 36, 5, 209-218 (1997)
[61] Somlyódy, L.; Wets, R. J.-B., Stochastic optimization models for lake eutrophication management, Operations Research, 36, 5, 660-681 (1988) · Zbl 0655.90044
[62] Srivastava, P.; Hamlett, J. M.; Robillard, P. D.; Day, R. L., Watershed optimization of best management practices using AnnAGNPS and a genetic algorithm, Water Resources Research, 38, 3, Article 3-1-3-14 (2002)
[63] Star, M.; Rolfe, J.; Donaghy, P.; Beutel, T.; Whish, G.; Abbott, B., Targeting resource investments to achieve sediment reduction and improved great barrier reef health, Agriculture, Ecosystems & Environment, 180, 148-156 (2013)
[64] Toscano, G.; Hernandez-Suarez, J. S.; Blank, J.; Nejadhashemi, P.; Deb, K., Systematic development of single-objective optimization approaches for Chesapeake Bay watershed management, Technical Report 2021013 (2021), Computational Optimization and Innovation Laboratory (COIN)
[65] Toscano, G.; Hernandez-Suarez, J. S.; Blank, J.; Nejadhashemi, P.; Deb, K.; Linker, L., Large-scale multi-objective optimization for water quality in Chesapeake Bay watershed, Technical Report 2022002 (2022), Computational Optimization and Innovation Laboratory (COIN)
[66] Trapanese, S.; Smolen, M.; Younos, T., A systems approach for agricultural land management and water quality control, Transactions of the ASAE, 27, 3, 817-0821 (1984)
[67] Van Houtven, G., Loomis, R., Baker, J., Beach, R., & Casey, S. (2012). Nutrient credit trading for the chesapeake bay: An economic study. http://www.chesbay.us/Publications/nutrient-trading-2012.pdf.
[68] Veith, T. L.; Wolfe, M. L.; Heatwole, C. D., Optimization procedure for cost effective BMP placement at a watershed scale, JAWRA Journal of the American Water Resources Association, 39, 6, 1331-1343 (2003)
[69] Veith, T. L.; Wolfe, M. L.; Heatwole, C. D., Cost-effective BMP placement: Optimization versus targeting, Transactions of the ASAE, 47, 5, 1585-1594 (2004)
[70] Viessman Jr, W.; Lewis, G. L.; Yomtovian, I.; Viessman, N. J., A screening model for water resources planning 1, JAWRA Journal of the American Water Resources Association, 11, 2, 245-255 (1975)
[71] Vigerske, S. (2021). Personal communication, 23 July 2021.
[72] Wächter, A.; Biegler, L. T., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical Programming, 106, 1, 25-57 (2006) · Zbl 1134.90542
[73] Wang, C.-F.; Liu, S.-Y.; Shen, P.-P., Global minimization of a generalized linear multiplicative programming, Applied Mathematical Modelling, 36, 6, 2446-2451 (2012) · Zbl 1246.90162
[74] http://hdl.handle.net/1969.1/6286
[75] Xu, H.; Brown, D. G.; Moore, M. R.; Currie, W. S., Optimizing spatial land management to balance water quality and economic returns in a lake erie watershed, Ecological Economics, 145, 104-114 (2018)
[76] Yakowitz, S., Dynamic programming applications in water resources, Water Resources Research, 18, 4, 673-696 (1982)
[77] Yang, G.; Best, E. P., Spatial optimization of watershed management practices for nitrogen load reduction using a modeling-optimization framework, Journal of Environmental Management, 161, 252-260 (2015)
[78] Zhao, Y.; Yang, J., Inner approximation algorithm for generalized linear multiplicative programming problems, Journal of inequalities and applications, 2018, 1, 1-13 (2018) · Zbl 1498.90177
[79] Zhen, X.-Y. J.; Yu, S. L.; Lin, J.-Y., Optimal location and sizing of stormwater basins at watershed scale, Journal of Water Resources Planning and Management, 130, 4, 339-347 (2004)
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.