 |
Universität Augsburg
|
|
|
Universität Augsburg
|
|
Professor Dr. Johannes Thürauf
Technische Universität Nürnberg
spricht am
Dienstag, 21. Januar 2025
um
11:45 Uhr
im
Raum 3008 (L1)
über das Thema:
| Abstract: |
| Bilevel optimization problems are a class of mathematical programming problems in which some of the variables need to solve another optimization problem. On the one hand, this allows to model hierarchical decision processes. On the other hand, bilevel optimization problems are generally hard to solve. From a theoretical and computational point of view, there has been significant progress in solving bilevel optimization problems in the recent years. In this talk, we start with an introduction into linear bilevel optimization. To this end, we briefly present common solution techniques such as single-level reformulations for bilevel optimization problems with linear lower-level problems. After this short introduction to bilevel optimization, we study a specific class of bilevel problems so-called network flow interdiction problems. In doing so, we focus on 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. |
| Hierzu ergeht herzliche Einladung. |
| Prof. Dr. Elisabeth Gaar |