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; G. Verweij; P. Zwaneveld

doi:10.1016/j.disopt.2019.100565

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

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

Abstract

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.

Original language	English
Article number	100565
Number of pages	27
Journal	Discrete Optimization
Volume	37
DOIs	https://doi.org/10.1016/j.disopt.2019.100565
Publication status	Published - Aug 2020

Funding

We thank Kees Roos for helpful discussions in an early stage of this work, André Woning from Rijkswaterstaat for useful background information and Gary Greaves for reading the manuscript. Parts of our results were obtained in the 2017 Study Group Mathematics with Industry , for which we thank the organizers. M. Mnich is supported by a DFG, Germany grant MN 59/4-1 . L. Vena is supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement 339109 , and by the project 18-13685Y of the Czech Science Foundation (GAČR). We thank two anonymous referees whose comments and suggestions have enhanced the accessibility of this article and made the proofs easier to follow. Appendix

Funders	Funder number
Seventh Framework Programme	339109
H2020 European Research Council	18-13685Y
Deutsche Forschungsgemeinschaft	MN 59/4-1
Grantová Agentura České Republiky
Seventh Framework Programme
Ministerie van Infrastructuur en Waterstaat

Keywords

Cost–benefit analysis
Dynamic programming
Integer programming

Access to Document

10.1016/j.disopt.2019.100565

Cite this

@article{f713c0230d3c4bdbb408411599f89bd0,

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

abstract = "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.",

keywords = "Cost–benefit analysis, Dynamic programming, Integer programming",

author = "A. Abiad and S. Gribling and D. Lahaye and M. Mnich and G. Regts and L. Vena and G. Verweij and P. Zwaneveld",

year = "2020",

month = aug,

doi = "10.1016/j.disopt.2019.100565",

language = "English",

volume = "37",

journal = "Discrete Optimization",

issn = "1572-5286",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - On the complexity of solving a decision problem with flow-depending costs

T2 - The case of the IJsselmeer dikes

AU - Abiad, A.

AU - Gribling, S.

AU - Lahaye, D.

AU - Mnich, M.

AU - Regts, G.

AU - Vena, L.

AU - Verweij, G.

AU - Zwaneveld, P.

PY - 2020/8

Y1 - 2020/8

N2 - 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.

AB - 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.

KW - Cost–benefit analysis

KW - Dynamic programming

KW - Integer programming

UR - http://www.scopus.com/inward/record.url?scp=85077655121&partnerID=8YFLogxK

U2 - 10.1016/j.disopt.2019.100565

DO - 10.1016/j.disopt.2019.100565

M3 - Article

AN - SCOPUS:85077655121

SN - 1572-5286

VL - 37

JO - Discrete Optimization

JF - Discrete Optimization

M1 - 100565

ER -

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

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this