TY - INPR A1 - Beck, Yasmine A1 - Ljubic, Ivana A1 - Schmidt, Martin T1 - Exact Methods for Discrete Γ-Robust Interdiction Problems with an Application to the Bilevel Knapsack Problem N2 - Developing solution methods for discrete bilevel problems is known to be a challenging task - even if all parameters of the problem are exactly known. Many real-world applications of bilevel optimization, however, involve data uncertainty. We study discrete min-max problems with a follower who faces uncertainties regarding the parameters of the lower-level problem. Adopting a Γ-robust approach, we present an extended formulation and a multi-follower formulation to model this type of problem. For both settings, we provide a generic branch-and-cut framework. Specifically, we investigate interdiction problems with a monotone Γ-robust follower and we derive problem-tailored cuts, which extend existing techniques that have been proposed for the deterministic case. For the Γ-robust knapsack interdiction problem, we computationally evaluate and compare the performance of the proposed algorithms for both modeling approaches. KW - Bilevel optimization KW - Robust optimization KW - Knapsack interdiction KW - Mixed-integer programming KW - Branch-and-Cut Y1 - 2021 ER - TY - INPR A1 - Thürauf, Johannes A1 - Grübel, Julia A1 - Schmidt, Martin T1 - Adjustable Robust Nonlinear Network Design under Demand Uncertainties N2 - We study network design problems for nonlinear and nonconvex flow models under demand uncertainties. To this end, we apply the concept of adjustable robust optimization to compute a network design that admits a feasible transport for all, possibly infinitely many, demand scenarios within a given uncertainty set. For solving the corresponding adjustable robust mixed-integer nonlinear optimization problem, we show that a given network design is robust feasible, i.e., it admits a feasible transport for all demand uncertainties, if and only if a finite number of worst-case demand scenarios can be routed through the network. We compute these worst-case scenarios by solving polynomially many nonlinear optimization problems. Embedding this result for robust feasibility in an adversarial approach leads to an exact algorithm that computes an optimal robust network design in a finite number of iterations. Since all of the results are valid for general potential-based flows, the approach can be applied to different utility networks such as gas, hydrogen, or water networks. We finally demonstrate the applicability of the method by computing robust gas networks that are protected from future demand fluctuations. KW - Robust Optimization KW - Nonlinear Flows KW - Potential-based Networks KW - Demand Uncertainties KW - Mixed-integer Nonlinear Optimization Y1 - 2024 ER - TY - INPR A1 - Hannes, Dänschel A1 - Volker, Mehrmann A1 - Roland, Marius A1 - Schmidt, Martin T1 - Adaptive Nonlinear Optimization of District Heating Networks Based on Model and Discretization Catalogs N2 - We propose an adaptive optimization algorithm for operating district heating networks in a stationary regime. The behavior of hot water flow in the pipe network is modeled using the incompressible Euler equations and a suitably chosen energy equation. By applying different simplifications to these equations, we derive a catalog of models. Our algorithm is based on this catalog and adaptively controls where in the network which model is used. Moreover, the granularity of the applied discretization is controlled in a similar adaptive manner. By doing so, we are able to obtain optimal solutions at low computational costs that satisfy a prescribed tolerance w.r.t. the most accurate modeling level. To adaptively control the switching between different levels and the adaptation of the discretization grids, we derive error measure formulas and a posteriori error measure estimators. Under reasonable assumptions we prove that the adaptive algorithm terminates after finitely many iterations. Our numerical results show that the algorithm is able to produce solutions for problem instances that have not been solvable before. KW - District heating networks KW - Adaptive methods KW - Nonlinear optimization Y1 - 2022 ER - TY - INPR A1 - Beck, Yasmine A1 - Schmidt, Martin A1 - Thürauf, Johannes A1 - Bienstock, Daniel T1 - On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level N2 - It is well known that bilevel optimization problems are hard to solve both in theory and practice. In this paper, we highlight a further computational difficulty when it comes to solving bilevel problems with continuous but nonconvex lower levels. Even if the lower-level problem is solved to ɛ-feasibility regarding its nonlinear constraints for an arbitrarily small but positive ɛ, the obtained bilevel solution as well as its objective value may be arbitrarily far away from the actual bilevel solution and its actual objective value. This result even holds for bilevel problems for which the nonconvex lower level is uniquely solvable, for which the strict complementarity condition holds, for which the feasible set is convex, and for which Slater's constraint qualification is satisfied for all feasible upper-level decisions. Since the consideration of ɛ-feasibility cannot be avoided when solving nonconvex problems to global optimality, our result shows that computational bilevel optimization with continuous and nonconvex lower levels needs to be done with great care. Finally, we illustrate that the nonlinearities in the lower level are the key reason for the observed bad behavior by showing that linear bilevel problems behave much better at least on the level of feasible solutions. KW - Bilevel optimization KW - Nonconvex lower levels KW - Approximate feasibility KW - Global optimization Y1 - 2022 ER - TY - INPR A1 - Schmidt, Martin A1 - Thürauf, Johannes T1 - An Exact Method for Nonlinear Network Flow Interdiction Problems N2 - 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. KW - Interdiction Games KW - Bilevel Optimization KW - Potential-Based Flows KW - Mixed-Integer Nonlinear Optimization Y1 - 2022 ER - TY - INPR A1 - Hante, Falk M. A1 - Schmidt, Martin T1 - Gas Transport Network Optimization: PDE-Constrained Models N2 - The optimal control of gas transport networks was and still is a very important topic for modern economies and societies. Accordingly, a lot of research has been carried out on this topic during the last years and decades. Besides mixed-integer aspects in gas transport network optimization, one of the main challenges is that a physically and technically detailed modeling of transient gas dynamics leads to theoretically and computationally highly demanding models involving nonlinear partial differential equations (PDEs). For further background on the application, historical notes and a detailed discussion of mixed-integer aspects for stationary descriptions we refer to Hante and Schmidt (2023). In this chapter, we focus on the most common modeling approaches concerning transient descriptions, point out the challenges, and summarize important contributions concerning the optimization of the most relevant control parameters for this particular class of problems. KW - Gas networks KW - Partial differential equations KW - Optimal control KW - PDE-constrained optimization KW - Modeling Y1 - 2023 ER - TY - INPR A1 - Hante, Falk M. A1 - Schmidt, Martin T1 - Gas Transport Network Optimization: Mixed-Integer Nonlinear Models N2 - Although modern societies strive towards energy systems that are entirely based on renewable energy carriers, natural gas is still one of the most important energy sources. This became even more obvious in Europe with Russia's 2022 war against the Ukraine and the resulting stop of gas supplies from Russia. Besides that it is very important to use this scarce resource efficiently. To this end, it is also of significant relevance that its transport is organized in the most efficient, i.e., cost- or energy-efficient, way. The corresponding mathematical optimization models have gained a lot of attention in the last decades in different optimization communities. These models are highly nonlinear mixed-integer problems that are constrained by algebraic constraints and partial differential equations (PDEs), which usually leads to models that are not tractable. Hence, simplifications have to be made and in this chapter, we present a commonly accepted finite-dimensional stationary model, i.e., a model in which the steady-state solutions of the PDEs are approximated with algebraic constraints. For more details about the involved PDEs and the treatment of transient descriptions we refer to Hante and Schmidt (2023). The presented finite-dimensional as well as mixed-integer nonlinear and nonconvex model is still highly challenging if it needs to be solved for real-world gas transport networks. Hence, we also review some classic solution approaches from the literature. KW - Gas networks KW - Mixed-integer nonlinear optimization KW - Mixed-integer linear optimization KW - Nonlinear optimization Y1 - 2023 ER - TY - INPR A1 - Hante, Falk M. A1 - Schmidt, Martin A1 - Topalovic, Antonia T1 - Stabilizing GNEP-Based Model Predictive Control: Quasi-GNEPs and End Constraints N2 - We present a feedback scheme for non-cooperative dynamic games and investigate its stabilizing properties. The dynamic games are modeled as generalized Nash equilibrium problems (GNEP), in which the shared constraint consists of linear time-discrete dynamic equations (e.g., sampled from a partial or ordinary differential equation), which are jointly controlled by the players’ actions. Further, the individual objectives of the players are interdependent and defined over a fixed time horizon. The feedback law is synthesized by moving-horizon model predictive control (MPC). We investigate the asymptotic stability of the resulting closed-loop dynamics. To this end, we introduce α-quasi GNEPs, a family of auxiliary problems based on a modification of the Nikaido–Isoda function, which approximate the original games. Basing the MPC scheme on these auxiliary problems, we derive conditions on the players’ objectives, which guarantee asymptotic stability of the closed-loop if stabilizing end constraints are enforced. This analysis is based on showing that the associated optimal-value function is a Lyapunov function. Additionally, we identify a suitable Lyapunov function for the MPC scheme based on the original GNEP, whose solution fulfills the stabilizing end constraints. The theoretical results are complemented by numerical experiments. KW - Model predictive control KW - Non-cooperative distributed control KW - Closed-loop stability KW - Generalized Nash equilibrium problems Y1 - 2024 ER - TY - JOUR A1 - Henrion, René A1 - Schmidt, Martin T1 - Chance-Constrained Linear Complementarity Problems N2 - We study linear complementarity problems (LCPs) under uncer- tainty, which we model using chance constraints. Since the complementarity condition of the LCP is an equality constraint, it is required to consider relax- ations, which naturally leads to optimization problems in which the relaxation parameters are minimized for given probability levels. We focus on these optimization problems and first study the continuity of the related probability functions and the compactness of the feasible sets. This leads to existence results for both types of models: one with a joint chance constraint and one with separate chance constraints for both uncertainty-affected conditions of the LCP. For both, we prove the differentiability of all probability functions and derive respective gradient formulae. For the separate case, we prove con- vexity of the respective optimization problem and use the gradient formulae to derive necessary and sufficient optimality conditions. In a small case study regarding a Cournot oligopoly among energy producers, we finally illustrate the applicability of our theoretical findings. KW - Linear complementarity problems KW - Chance constraints KW - Existence KW - Convexity KW - Optimality conditions Y1 - 2026 ER -