IDEAS home Printed from https://ideas.repec.org/p/arx/papers/1804.09752.html
   My bibliography  Save this paper

On the complexity of solving a decision problem with flow-depending costs: the case of the IJsselmeer dikes

Author

Listed:
  • Aida Abiad
  • Sander Gribling
  • Domenico Lahaye
  • Matthias Mnich
  • Guus Regts
  • Lluis Vena
  • Gerard Verweij
  • Peter Zwaneveld

Abstract

We consider a fundamental integer programming (IP) model for cost-benefit analysis flood protection through dike building in the Netherlands, due to Verweij and Zwaneveld. Experimental analysis with data for the Ijsselmeer lead to integral optimal solution of the linear programming relaxation of the IP model. This naturally led to the question of integrality of the polytope associated with the IP model. In this paper we first give a negative answer to this question by establishing non-integrality of the polytope. Second, we establish natural conditions that guarantee the linear programming relaxation of the IP model to be integral. We then test the most recent data on flood probabilities, damage and investment costs of the IJsselmeer for these conditions. Third, we show that the IP model can be solved in polynomial time when the number of dike segments, or the number of feasible barrier heights, are constant.

Suggested Citation

  • Aida Abiad & Sander Gribling & Domenico Lahaye & Matthias Mnich & Guus Regts & Lluis Vena & Gerard Verweij & Peter Zwaneveld, 2018. "On the complexity of solving a decision problem with flow-depending costs: the case of the IJsselmeer dikes," Papers 1804.09752, arXiv.org.
    • Handle: RePEc:arx:papers:1804.09752
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/1804.09752
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Ruud Brekelmans & Dick den Hertog & Kees Roos & Carel Eijgenraam, 2012. "Safe Dike Heights at Minimal Costs: The Nonhomogeneous Case," Operations Research, INFORMS, vol. 60(6), pages 1342-1355, December.
    2. Peter Zwaneveld & Gerard Verweij, 2018. "Economic Decision Problems in Multi-Level Flood Prevention: a new graph-based approach used for real world applications," CPB Discussion Paper 380.rdf, CPB Netherlands Bureau for Economic Policy Analysis.
    3. Peter Zwaneveld & Gerard Verweij, 2018. "Economic Decision Problems in Multi-Level Flood Prevention: a new graph-based approach used for real world applications," CPB Discussion Paper 380, CPB Netherlands Bureau for Economic Policy Analysis.
    4. Peter Zwaneveld & Gerard Verweij, 2014. "Safe Dike Heights at Minimal Costs: An Integer Programming Approach," CPB Discussion Paper 277, CPB Netherlands Bureau for Economic Policy Analysis.
    5. Peter Zwaneveld & Gerard Verweij, 2014. "Safe Dike Heights at Minimal Costs: An Integer Programming Approach," CPB Discussion Paper 277.rdf, CPB Netherlands Bureau for Economic Policy Analysis.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Peter Zwaneveld & Gerard Verweij, 2018. "Economic Decision Problems in Multi-Level Flood Prevention: a new graph-based approach used for real world applications," CPB Discussion Paper 380.rdf, CPB Netherlands Bureau for Economic Policy Analysis.
    2. Peter Zwaneveld & Gerard Verweij, 2018. "Economic Decision Problems in Multi-Level Flood Prevention: a new graph-based approach used for real world applications," CPB Discussion Paper 380, CPB Netherlands Bureau for Economic Policy Analysis.
    3. Johanna Grames & Dieter Grass & Peter M. Kort & Alexia Prskawetz, 2019. "Optimal investment and location decisions of a firm in a flood risk area using impulse control theory," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 27(4), pages 1051-1077, December.
    4. Dupuits, E.J.C. & Klerk, W.J. & Schweckendiek, T. & de Bruijn, K.M., 2019. "Impact of including interdependencies between multiple riverine flood defences on the economically optimal flood safety levels," Reliability Engineering and System Safety, Elsevier, vol. 191(C).
    5. Dupuits, E.J.C. & Schweckendiek, T. & Kok, M., 2017. "Economic optimization of coastal flood defense systems," Reliability Engineering and System Safety, Elsevier, vol. 159(C), pages 143-152.
    6. Thomas D. Pol & Ekko C. Ierland & Silke Gabbert, 2017. "Economic analysis of adaptive strategies for flood risk management under climate change," Mitigation and Adaptation Strategies for Global Change, Springer, vol. 22(2), pages 267-285, February.
    7. Postek, Krzysztof & den Hertog, Dick & Kind, J. & Pustjens, Chris, 2016. "Adjustable Robust Strategies for Flood Protection," Discussion Paper 2016-038, Tilburg University, Center for Economic Research.
    8. Zwaneveld, P. & Verweij, G. & van Hoesel, S., 2018. "Safe dike heights at minimal costs: An integer programming approach," European Journal of Operational Research, Elsevier, vol. 270(1), pages 294-301.
    9. T. D. Pol & S. Gabbert & H.-P. Weikard & E. C. Ierland & E. M. T. Hendrix, 2017. "A Minimax Regret Analysis of Flood Risk Management Strategies Under Climate Change Uncertainty and Emerging Information," Environmental & Resource Economics, Springer;European Association of Environmental and Resource Economists, vol. 68(4), pages 1087-1109, December.
    10. Bos, Frits & Zwaneveld, Peter, 2017. "Cost-benefit analysis for flood risk management and water governance in the Netherlands; an overview of one century," MPRA Paper 80933, University Library of Munich, Germany.
    11. Chahim, M. & Brekelmans, R.C.M. & den Hertog, D. & Kort, P.M., 2012. "An Impulse Control Approach to Dike Height Optimization (Revised version of CentER DP 2011-097)," Discussion Paper 2012-079, Tilburg University, Center for Economic Research.
    12. Carel Eijgenraam & Jarl Kind & Carlijn Bak & Ruud Brekelmans & Dick den Hertog & Matthijs Duits & Kees Roos & Pieter Vermeer & Wim Kuijken, 2014. "Economically Efficient Standards to Protect the Netherlands Against Flooding," Interfaces, INFORMS, vol. 44(1), pages 7-21, February.
    13. Carel Eijgenraam & Ruud Brekelmans & Dick den Hertog & Kees Roos, 2017. "Optimal Strategies for Flood Prevention," Management Science, INFORMS, vol. 63(5), pages 1644-1656, May.
    14. Perry C. Oddo & Ben S. Lee & Gregory G. Garner & Vivek Srikrishnan & Patrick M. Reed & Chris E. Forest & Klaus Keller, 2020. "Deep Uncertainties in Sea‐Level Rise and Storm Surge Projections: Implications for Coastal Flood Risk Management," Risk Analysis, John Wiley & Sons, vol. 40(1), pages 153-168, January.
    15. Grass, D. & Chahim, M., 2012. "Numerical Algorithms for Deterministic Impulse Control Models with Applications," Discussion Paper 2012-081, Tilburg University, Center for Economic Research.
    16. Alessio Ciullo & Jan H. Kwakkel & Karin M. De Bruijn & Neelke Doorn & Frans Klijn, 2020. "Efficient or Fair? Operationalizing Ethical Principles in Flood Risk Management: A Case Study on the Dutch‐German Rhine," Risk Analysis, John Wiley & Sons, vol. 40(9), pages 1844-1862, September.
    17. Postek, Krzysztof & den Hertog, Dick & Kind, Jarl & Pustjens, Chris, 2019. "Adjustable robust strategies for flood protection," Omega, Elsevier, vol. 82(C), pages 142-154.
    18. Grames, Johanna & Prskawetz, Alexia & Grass, Dieter & Viglione, Alberto & Blöschl, Günter, 2016. "Modeling the interaction between flooding events and economic growth," Ecological Economics, Elsevier, vol. 129(C), pages 193-209.
    19. Bos, Frits & Zwaneveld, Peter & van Puijenbroek, Peter, 2012. "Een snelle kosten-effectiviteitsanalyse voor het Deltaprogramma IJsselmeergebied: wat zijn de kosten en veiligheidsbaten van wel of niet meestijgen met de zeespiegel en extra zoetwaterbuffer? [A co," MPRA Paper 61507, University Library of Munich, Germany.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:1804.09752. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.