581. An Exact Method for Nonlinear Network Flow Interdiction Problems
Invited abstract in session MB-17: Combinatorial bilevel optimization 2, stream Combinatorial Optimization.
Monday, 10:30-12:00Room: Esther Simpson 2.08
Authors (first author is the speaker)
| 1. | Martin Schmidt
|
| Department of Mathematics, Trier University | |
| 2. | Johannes Thürauf
|
| Discrete Optimization, University of Technology Nuremberg |
Abstract
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 to maximize 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.
Keywords
- Global Optimization
- Graphs and Networks
- Network Flows
Status: accepted
Back to the list of papers