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

A. Abiad, S. Gribling, D. Lahaye, M. Mnich, G. Regts, L. Vena (Corresponding author), G. Verweij, P. Zwaneveld

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Samenvatting

We consider a fundamental integer programming (IP) model for cost–benefit analysis and flood protection through dike building in the Netherlands, due to Zwaneveld and Verweij (2017). Experimental analysis with data for the IJsselmeer shows that the solution of the linear programming relaxation of the IP model is integral. This naturally leads to question whether the polytope associated to the IP is always integral. In this paper we first give a negative answer to this question by proving the non-integrality of the polytope. Secondly, we establish natural conditions that guarantee the linear programming relaxation of the IP model is integral. We show that these conditions are indeed satisfied by the recent data on flood probabilities, damage and investment costs of IJsselmeer. Finally, 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 bounded.

Originele taal-2Engels
Artikelnummer100565
Aantal pagina's27
TijdschriftDiscrete Optimization
Volume37
DOI's
StatusGepubliceerd - aug 2020

Vingerafdruk Duik in de onderzoeksthema's van 'On the complexity of solving a decision problem with flow-depending costs: The case of the IJsselmeer dikes'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit