An Exact Method for Nonlinear Network Flow Interdiction Problems
SIAM Journal on Optimization · 31.12.2024 · 34 (4) · 3623-3652
DOI: 10.1137/22m152983x ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Optimization, online erschienen am 19.11.2024. Verfasst von Martin Schmidt und 1 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 31 Literaturangaben. Gefördert von: Deutsche Forschungsgemeinschaft.
Abstract (Originalsprache)
We study network flow interdiction problems with nonlinear and nonconvex flow models. The resulting model is a max-min bilevel optimization problem in which the follower’s problem is nonlinear and nonconvex. In this game, the leader attacks a limited number of arcs with the goal of maximizing the load shed, and the follower aims at minimizing the load shed by solving a transport problem in the interdicted network. We develop an exact algorithm consisting of lower and upper bounding schemes that computes an optimal interdiction under the assumption that the interdicted network remains weakly connected. The main challenge consists of computing valid upper bounds for the maximal load shed, whereas lower bounds can directly be derived from the follower’s problem. To compute an upper bound, we propose solving a specific bilevel problem, which is derived from restricting the flexibility of the follower when adjusting the load flow. This bilevel problem still has a nonlinear and nonconvex follower’s problem, for which we then prove necessary and sufficient optimality conditions. Consequently, we obtain equivalent single-level reformulations of the specific bilevel model to compute upper bounds. Our numerical results show the applicability of this exact approach using the example of gas networks.
Förderung
- Deutsche Forschungsgemeinschaft
Zitieren
APA
Schmidt, M., & Thürauf, J. (2024). An Exact Method for Nonlinear Network Flow Interdiction Problems. SIAM Journal on Optimization, 34(4), 3623-3652. https://doi.org/10.1137/22m152983x
Vancouver
Schmidt M, Thürauf J. An Exact Method for Nonlinear Network Flow Interdiction Problems. SIAM Journal on Optimization. 2024;34(4):3623-3652. doi:10.1137/22m152983x
BibTeX
@article{Schmidt2024,
author = {Schmidt, Martin and Thürauf, Johannes},
title = {An Exact Method for Nonlinear Network Flow Interdiction Problems},
journal = {SIAM Journal on Optimization},
year = {2024},
volume = {34},
number = {4},
pages = {3623--3652},
doi = {10.1137/22m152983x}
}
EUVIMED