@unpublished{GugatHabermannHintermuelleretal.2021, author = {Gugat, Martin and Habermann, Jens and Hinterm{\"u}ller, Michael and Huber, Olivier}, title = {Constrained exact boundary controllability of a semilinear model for pipeline gas flow}, year = {2021}, abstract = {While the quasilinear isothermal Euler equations are an excellent model for gas pipeline flow, the operation of the pipeline flow with high pressure and small Mach numbers allows us to obtain approximate solutions by a simpler semilinear model. We provide a derivation of the semilinear model that shows that the semilinear model is valid for sufficiently low Mach numbers and sufficiently high pressures. We prove an existence result for continuous solutions of the semilinear model that takes into account lower and upper bounds for the pressure and an upper bound for the magnitude of the Mach number of the gas flow. These state constraints are important both in the operation of gas pipelines and to guarantee that the solution remains in the set where the model is physically valid. We show the constrained exact boundary controllability of the system with the same pressure and Mach number constraints.}, language = {en} } @unpublished{GruebelHuberHuembsetal.2021, author = {Gr{\"u}bel, Julia and Huber, Olivier and H{\"u}mbs, Lukas and Klimm, Max and Schmidt, Martin and Schwartz, Alexandra}, title = {Nonconvex Equilibrium Models for Energy Markets: Exploiting Price Information to Determine the Existence of an Equilibrium}, pages = {29}, year = {2021}, abstract = {Motivated by examples from the energy sector, we consider market equilibrium problems (MEPs) involving players with nonconvex strategy spaces or objective functions, where the latter are assumed to be linear in market prices. We propose an algorithm that determines if an equilibrium of such an MEP exists and that computes an equilibrium in case of existence. Three key prerequisites have to be met. First, appropriate bounds on market prices have to be derived from necessary optimality conditions of some players. Second, a technical assumption is required for those prices that are not uniquely determined by the derived bounds. Third, nonconvex optimization problems have to be solved to global optimality. We test the algorithm on well-known instances from the power and gas literature that meet these three prerequisites. There, nonconvexities arise from considering the transmission system operator as an additional player besides producers and consumers who, e.g., switches lines or faces nonlinear physical laws. Our numerical results indicate that equilibria often exist, especially for the case of continuous nonconvexities in the context of gas market problems.}, language = {en} } @article{BarcenaPetiscoCavalcanteCocliteetal.2021, author = {B{\´a}rcena-Petisco, J.A. and Cavalcante, M. and Coclite, G.M. and de Nitti, N. and Zuazua, E.}, title = {Control of Hyperbolic and Parabolic Equations on Networks and Singular limits}, year = {2021}, abstract = {We study the controllability properties of the transport equation and of parabolic equations posed on a tree. Using a control localized on the exterior nodes, we prove that the hyperbolic and the parabolic systems are null-controllable. The hyperbolic proof relies on the method of characteristics, the parabolic one on duality arguments and Carleman inequalities. We also show that the parabolic system may not be controllable if we do not act on all exterior vertices because of symmetries. Moreover, we estimate the cost of the null-controllability of transport-diffusion equations with diffusivity ε > 0ε>0 and study its asymptotic behavior when ε → 0^+ε→0 + . We prove that the cost of the controllability decays for a time sufficiently large and explodes for short times. This is done by duality arguments allowing to reduce the problem to obtain observability estimates which depend on the viscosity parameter. These are derived by using Agmon and Carleman inequalities.}, language = {en} } @phdthesis{Nowak2021, author = {Nowak, Daniel}, title = {Nonconvex Nash Games - Solution Concepts and Algorithms}, publisher = {E-Publishing-Service der TU Darmstadt}, address = {Darmstadt}, doi = {10.26083/tuprints-00017637}, year = {2021}, abstract = {Game theory is a mathematical approach to model competition between several parties, called players. The goal of each player is to choose a strategy, which solves his optimization problem, i.e. minimizes or maximizes his objective function. Due to the competitive setting, this strategy may influence the optimization problems of other players. In the non-cooperative setting each player acts selfish, meaning he does not care about the objective of his opponents. A solution concept for this problem is a Nash equilibrium, which was introduced by John Forbes Nash in his Ph.D. thesis in 1950. Convexity of the optimization problems is a crucial assumption for the existence of Nash equilibria. This work investigates settings, where this convexity assumption fails to hold. The first part of this thesis extends results of Jong-Shi Pang and Gesualdo Scutari from their paper ``Nonconvex Games with Side Constraints'' published in 2011. In this publication, a game with possibly nonconvex objective functions and nonconvex individual and shared inequality constraints was investigated. We extend these results twofold. Firstly, we generalize the individual and shared polyhedral constraints to general convex constraints and, secondly, we introduce convex and nonconvex, individual and shared equality constraints. After a detailed comparison of solution concepts for the generalized Nash game and a related Nash game, we show that so-called quasi-Nash equilibria exist under similar assumptions than in the original work, provided some additional constraint qualification holds. Subsequently, we prove that the existence of Nash equilibria needs additional assumptions on the gradients of the equality constraints. Furthermore, a special case of a multi-leader multi-follower game is investigated. We show the convergence of epsilon-quasi-Nash equilibria to C-stationary points and prove that these are also Clarke-stationary under reasonable assumptions. In the second part of this thesis, an application in computation offloading is investigated. We consider several mobile users that are able to offload parts of a computation task to a connected server. However, the server has limited computation capacities which leads to competition among the mobile users. If a user decides to offload a part of his computation, he needs to wait for the server to finish before he can assemble the results of his computation. This leads to a vanishing constraint in the optimization problem of the mobile users which is a nonconvex and nonsmooth condition. We show the existence of a unique Nash equilibrium for the computation offloading game and provide an efficient algorithm for its computation. Furthermore, we present two extensions to this game, which inherit similar properties and we also show the limitations of these formulations. The third part investigates a hierarchical constrained Cournot game. In the upper level, several firms decide on capacities which act as constraints for the production variables. In the lower level the same firms engage in a Cournot competition, where they choose production variables to maximize profit. The prior chosen capacities are upper bounds on these production variables. This hierarchical setting induces nonconvexity and nonsmoothness in the upper level objective functions. After a detailed sensitivity analysis of the lower level, we give necessary optimality conditions for the upper level, i.e. for the hierarchical Cournot game. Using these conditions, we construct an algorithm which provably finds all Nash equilibria of the game, provided some assumptions are satisfied. This algorithm is numerically tested on several examples which are motivated by the gas market.}, language = {en} } @article{KrugLeugeringMartinetal.2021, author = {Krug, Richard and Leugering, G{\"u}nter and Martin, Alexander and Schmidt, Martin and Weninger, Dieter}, title = {Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems with Mixed Two-Point Boundary Conditions}, series = {Control and Cybernetics}, journal = {Control and Cybernetics}, pages = {20}, year = {2021}, abstract = {In this article, we continue our work (Krug et al., 2021) on time-domain decomposition of optimal control problems for systems of semilinear hyperbolic equations in that we now consider mixed two-point boundary value problems and provide an in-depth well-posedness analysis. The more general boundary conditions significantly enlarge the scope of applications, e.g., to hyperbolic problems on metric graphs with cycles. We design an iterative method based on the optimality systems that can be interpreted as a decomposition method for the original optimal control problem into virtual control problems on smaller time domains.}, language = {en} } @article{KleinertMannsSchmidtetal.2021, author = {Kleinert, Thomas and Manns, Julian and Schmidt, Martin and Weninger, Dieter}, title = {Presolving Linear Bilevel Optimization Problems}, series = {EURO Journal on Computational Optimization}, journal = {EURO Journal on Computational Optimization}, number = {9}, doi = {10.1016/j.ejco.2021.100020}, year = {2021}, abstract = {Linear bilevel optimization problems are known to be strongly NP-hard and the computational techniques to solve these problems are often motivated by techniques from single-level mixed-integer optimization. Thus, during the last years and decades many branch-and-bound methods, cutting planes, or heuristics have been proposed. On the other hand, there is almost no literature on presolving linear bilevel problems although presolve is a very important ingredient in state-of-the-art mixed-integer optimization solvers. In this paper, we carry over standard presolve techniques from single-level optimization to bilevel problems and show that this needs to be done with great caution since a naive application of well-known techniques does often not lead to correctly presolved bilevel models. Our numerical study shows that presolve can also be very beneficial for bilevel problems but also highlights that these methods have a more heterogeneous effect on the solution process compared to what is known from single-level optimization. As a side result, our numerical experiments reveal that there is an urgent need for better and more heterogeneous test instance libraries to further propel the field of computational bilevel optimization.}, language = {en} } @unpublished{EgererGrimmGruebeletal.2021, author = {Egerer, Jonas and Grimm, Veronika and Gr{\"u}bel, Julia and Z{\"o}ttl, Gregor}, title = {Long-run market equilibria in coupled energy sectors: A study of uniqueness}, pages = {32}, year = {2021}, abstract = {We propose an equilibrium model for coupled markets of multiple energy sectors. The agents in our model are operators of sector-specific production and sector-coupling technologies, as well as price-sensitive consumers with varying demand. We analyze long-run investment in production capacity in each sector and investment in coupling capacity between sectors, as well as production decisions determined at repeated spot markets. We show that in our multi-sector model, multiplicity of equilibria may occur, even if all assumptions hold that would be sufficient for uniqueness in a single-sector model. We then contribute to the literature by deriving sufficient conditions for the uniqueness of short- and long-run market equilibrium in coupled markets of multiple energy sectors. We illustrate via simple examples that these conditions are indeed required to guarantee uniqueness in general. The uniqueness result is an important step to be able to incorporate the proposed market equilibrium problem in more complex computational multilevel equilibrium models, in which uniqueness of lower levels is a prerequisite for obtaining meaningful solutions. Our analysis also paves the way to understand and analyze more complex sector coupling models in the future.}, language = {en} } @article{RuizBaletZuazua2021, author = {Ruiz-Balet, Domenec and Zuazua, Enrique}, title = {Neural ODE Control for Classification, Approximation and Transport}, year = {2021}, abstract = {We analyze Neural Ordinary Differential Equations (NODEs) from a control theoretical perspective to address some of the main properties and paradigms of Deep Learning (DL), in particular, data classification and universal approximation. These objectives are tackled and achieved from the perspective of the simultaneous control of systems of NODEs. For instance, in the context of classification, each item to be classified corresponds to a different initial datum for the control problem of the NODE, to be classified, all of them by the same common control, to the location (a subdomain of the euclidean space) associated to each label. Our proofs are genuinely nonlinear and constructive, allowing us to estimate the complexity of the control strategies we develop. The nonlinear nature of the activation functions governing the dynamics of NODEs under consideration plays a key role in our proofs, since it allows deforming half of the phase space while the other half remains invariant, a property that classical models in mechanics do not fulfill. This very property allows to build elementary controls inducing specific dynamics and transformations whose concatenation, along with properly chosen hyperplanes, allows achieving our goals in finitely many steps. The nonlinearity of the dynamics is assumed to be Lipschitz. Therefore, our results apply also in the particular case of the ReLU activation function. We also present the counterparts in the context of the control of neural transport equations, establishing a link between optimal transport and deep neural networks.}, language = {en} } @phdthesis{Kleinert2021, author = {Kleinert, Thomas}, title = {Algorithms for Mixed-Integer Bilevel Problems with Convex Followers}, year = {2021}, abstract = {Bilevel problems are optimization problems for which a subset of variables is constrained to be an optimal solution of another optimization problem. As such, bilevel problems are capable of modeling hierarchical decision processes. This is required by many real-world problems from a broad spectrum of applications such as energy markets, traffic planning, or critical infrastructure defense, to name only a few. However, the hierarchy of decisions makes bilevel optimization problems also very challenging to solve—both in theory and practice. This cumulative PhD thesis is concerned with computational bilevel optimization. In the first part, we summarize several solution approaches that we developed over the last years and highlight the significant computational progress that these methods provide. For linear bilevel problems, we review branch-and-bound methods, critically discuss their practical use, and propose valid inequalities to extend the methods to branch-and-cut approaches. Further, we demonstrate on a large test set that it is no longer necessary to use the well-known but error-prone big-M reformulation to solve linear bilevel problems. We also present a bilevel-specific heuristic that is based on a penalty alternating direction method. This heuristic is applicable to a broad class of bilevel problems, e.g., linear or mixed-integer quadratic bilevel problems. In a computational study, we show that the method computes optimal or close-to-optimal feasible points in a very short time and that it outperforms a state-of-the-art local method from the literature. Finally, we review global approaches for mixed-integer quadratic bilevel problems. In addition to a Benders-like decomposition, we present a multi-tree and a single-tree outer-approximation approach. A computational evaluation demonstrates that both variants outperform known benchmark algorithms. The second part of this thesis consists of reprints of our original articles and preprints. These articles contain all details and are referenced throughout the first part of the thesis.}, language = {en} } @article{EsteveGeshkovskiPighinetal., author = {Esteve, Carlos and Geshkovski, Borjan and Pighin, Dario and Zuazua, Enrique}, title = {Turnpike in Lipschitz-nonlinear optimal control}, abstract = {We present a new proof of the turnpike property for nonlinear optimal control problems, when the running target is a steady control-state pair of the underlying dynamics. Our strategy combines the construction of suboptimal quasi-turnpike trajectories via controllability, and a bootstrap argument, and does not rely on analyzing the optimality system or linearization techniques. This in turn allows us to address several optimal control problems for finite-dimensional, control-affine systems with globally Lipschitz (possibly nonsmooth) nonlinearities, without any smallness conditions on the initial data or the running target. These results are motivated by the large-layer regime of residual neural networks, commonly used in deep learning applications. We show that our methodology is applicable to controlled PDEs as well, such as the semilinear wave and heat equation with a globally Lipschitz nonlinearity, once again without any smallness assumptions.}, language = {en} } @article{KrugLeugeringMartinetal.2020, author = {Krug, Richard and Leugering, G{\"u}nter and Martin, Alexander and Schmidt, Martin and Weninger, Dieter}, title = {Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems}, series = {SIAM Journal on Control and Optimization}, journal = {SIAM Journal on Control and Optimization}, pages = {28}, year = {2020}, abstract = {In this article, we extend the time-domain decomposition method described by Lagnese and Leugering (2003) to semilinear optimal control problems for hyperbolic balance laws with spatio-temporal varying coefficients. We provide the design of the iterative method applied to the global first-order optimality system, prove its convergence, and derive an a posteriori error estimate. The analysis is done entirely on the continuous level. A distinguishing feature of the method is that the decomposed optimality system can be interpreted as an optimality system of a local "virtual" optimal control problem. Thus, the iterative time-domain decomposition of the optimality system can be interpreted as an iterative parallel scheme for virtual optimal control problems on the subintervals. A typical example and further comments are given to show the range of potential applications. Moreover, we provide some numerical experiments to give a first interpretation of the role of the parameters involved in the iterative process.}, language = {en} } @article{KleinertLabbeLjubićetal.2021, author = {Kleinert, Thomas and Labb{\´e}, Martine and Ljubić, Ivana and Schmidt, Martin}, title = {A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization}, series = {EURO Journal on Computational Optimization}, journal = {EURO Journal on Computational Optimization}, pages = {47}, year = {2021}, abstract = {Bilevel optimization is a field of mathematical programming in which some variables are constrained to be the solution of another optimization problem. As a consequence, bilevel optimization is able to model hierarchical decision processes. This is appealing for modeling real-world problems, but it also makes the resulting optimization models hard to solve in theory and practice. The scientific interest in computational bilevel optimization increased a lot over the last decade and is still growing. Independent of whether the bilevel problem itself contains integer variables or not, many state-of-the-art solution approaches for bilevel optimization make use of techniques that originate from mixed-integer programming. These techniques include branch-and-bound methods, cutting planes and, thus, branch-and-cut approaches, or problem-specific decomposition methods. In this survey article, we review bilevel-tailored approaches that exploit these mixed-integer programming techniques to solve bilevel optimization problems. To this end, we first consider bilevel problems with convex or, in particular, linear lower-level problems. The discussed solution methods in this field stem from original works from the 1980's but, on the other hand, are still actively researched today. Second, we review modern algorithmic approaches to solve mixed-integer bilevel problems that contain integrality constraints in the lower level. Moreover, we also briefly discuss the area of mixed-integer nonlinear bilevel problems. Third, we devote some attention to more specific fields such as pricing or interdiction models that genuinely contain bilinear and thus nonconvex aspects. Finally, we sketch a list of open questions from the areas of algorithmic and computational bilevel optimization, which may lead to interesting future research that will further propel this fascinating and active field of research.}, language = {en} } @unpublished{Thuerauf, author = {Th{\"u}rauf, Johannes}, title = {Deciding the Feasibility of a Booking in the European Gas Market is coNP-hard}, abstract = {We show that deciding the feasibility of a booking (FB) in the European entry-exit gas market is coNP-hard if a nonlinear potential-based flow model is used. The feasibility of a booking can be characterized by polynomially many load flow scenarios with maximum potential-difference, which are computed by solving nonlinear potential-based flow models. We use this existing characterization of the literature to prove that FB is coNP-hard by reducing Partition to the infeasibility of a booking. We further prove that computing a potential-difference maximizing load flow scenario is NP-hard even if we can determine the flow direction a priori. From the literature, it is known that FB can be decided in polynomial time on trees and a single cycle. Thus, our hardness result draws the first line that separates the easy from the hard variants of FB and finally answers that FB is hard in general.}, language = {en} } @article{KleinertLabbeSchmidtetal.2020, author = {Kleinert, Thomas and Labb{\´e}, Martine and Schmidt, Martin and Plein, Fr{\"a}nk}, title = {Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality}, series = {Optimization Letters}, journal = {Optimization Letters}, number = {15}, pages = {1027 -- 1040}, year = {2020}, abstract = {Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem's optimality conditions. While in mixed-integer single-level optimization branch-and-cut has proven to be a powerful extension of branch-and-bound, in linear bilevel optimization not too many bilevel-tailored valid inequalities exist. In this paper, we briefly review existing cuts for linear bilevel problems and introduce a new valid inequality that exploits the strong duality condition of the lower level. We further discuss strengthened variants of the inequality that can be derived from McCormick envelopes. In a computational study, we show that the new valid inequalities can help to close the optimality gap very effectively on a large test set of linear bilevel instances.}, language = {de} } @article{BoettgerGrimmKleinertetal.2020, author = {B{\"o}ttger, Tom and Grimm, Veronika and Kleinert, Thomas and Schmidt, Martin}, title = {The Cost of Decoupling Trade and Transport in the European Entry-Exit Gas Market with Linear Physics Modeling}, series = {European Journal of Operational Research}, journal = {European Journal of Operational Research}, pages = {27}, year = {2020}, abstract = {Liberalized gas markets in Europe are organized as entry-exit regimes so that gas trade and transport are decoupled. The decoupling is achieved via the announcement of technical capacities by the transmission system operator (TSO) at all entry and exit points of the network. These capacities can be booked by gas suppliers and customers in long-term contracts. Only traders who have booked capacities up-front can "nominate" quantities for injection or withdrawal of gas via a day-ahead market. To ensure feasibility of the nominations for the physical network, the TSO must only announce technical capacities for which all possibly nominated quantities are transportable. In this paper, we use a four-level model of the entry-exit gas market to analyze possible welfare losses associated with the decoupling of gas trade and transport. In addition to the multilevel structure, the model contains robust aspects to cover the conservative nature of the European entry-exit system. We provide several reformulations to obtain a single-level mixed-integer quadratic problem. The overall model of the considered market regime is extremely challenging and we thus have to make the main assumption that gas flows are modeled as potential-based linear flows. Using the derived single-level reformulation of the problem, we show that the feasibility requirements for technical capacities imply significant welfare losses due to unused network capacity. Furthermore, we find that the specific structure of the network has a considerable influence on the optimal choice of technical capacities. Our results thus show that trade and transport are not decoupled in the long term. As a further source of welfare losses and discrimination against individual actors, we identify the minimum prices for booking capacity at the individual nodes.}, language = {en} } @unpublished{GrimmNowakScheweetal.2020, author = {Grimm, Veronika and Nowak, Daniel and Schewe, Lars and Schmidt, Martin and Schwartz, Alexandra and Z{\"o}ttl, Gregor}, title = {A Tractable Multi-Leader Multi-Follower Peak-Load-Pricing Model with Strategic Interaction}, doi = {10.1007/s10107-021-01708-0}, pages = {35}, year = {2020}, abstract = {While single-level Nash equilibrium problems are quite well understood nowadays, less is known about multi-leader multi-follower games. However, these have important applications, e.g., in the analysis of electricity and gas markets, where often a limited number of firms interacts on various subsequent markets. In this paper, we consider a special class of two-level multi-leader multi-follower games that can be applied, e.g., to model strategic booking decisions in the European entry-exit gas market. For this nontrivial class of games, we develop a solution algorithm that is able to compute the complete set of Nash equilibria instead of just individual solutions or a bigger set of stationary points. Additionally, we prove that for this class of games, the solution set is finite and provide examples for instances without any Nash equilibria in pure strategies. We apply the algorithm to a case study in which we compute strategic booking and nomination decisions in a model of the European entry-exit gas market system. Finally, we use our algorithm to provide a publicly available test library for the considered class of multi-leader multi-follower games. This library contains problem instances with different economic and mathematical properties so that other researchers in the field can test and benchmark newly developed methods for this challenging class of problems.}, language = {en} } @article{GugatHanteJin2020, author = {Gugat, Martin and Hante, Falk and Jin, Li}, title = {Closed loop control of gas flow in a pipe: Stability for a transient model}, series = {at - Automatisierungstechnik}, journal = {at - Automatisierungstechnik}, year = {2020}, abstract = {This contribution focuses on the analysis and control of friction-dominated flow of gas in pipes. The pressure in the gas flow is governed by a partial differential equation that is a doubly nonlinear parabolic equation of p-Laplace type, where p=2/3. Such equations exhibit positive solutions, finite speed of propagation and satisfy a maximum principle. The pressure is fixed on one end (upstream), and the flow is specified on the other end (downstream). These boundary conditions determine a unique steady equilibrium flow. We present a boundary feedback flow control scheme, that ensures local exponential stability of the equilibrium in an L2-sense. The analysis is done both for the pde system and an ode system that is obtained by a suitable spatial semi-discretization. The proofs are based upon suitably chosen Lyapunov functions.}, language = {en} } @unpublished{BiefelLiersRolfesetal.2020, author = {Biefel, Christian and Liers, Frauke and Rolfes, Jan and Schmidt, Martin}, title = {Affinely Adjustable Robust Linear Complementarity Problems}, pages = {20}, year = {2020}, abstract = {Linear complementarity problems are a powerful tool for modeling many practically relevant situations such as market equilibria. They also connect many sub-areas of mathematics like game theory, optimization, and matrix theory. Despite their close relation to optimization, the protection of LCPs against uncertainties - especially in the sense of robust optimization - is still in its infancy. During the last years, robust LCPs have only been studied using the notions of strict and Γ-robustness. Unfortunately, both concepts lead to the problem that the existence of robust solutions cannot be guaranteed. In this paper, we consider affinely adjustable robust LCPs. In the latter, a part of the LCP solution is allowed to adjust via a function that is affine in the uncertainty. We show that this notion of robustness allows to establish strong characterizations of solutions for the cases of uncertain matrix and vector, separately, from which existence results can be derived. Our main results are valid for the case of an uncertain LCP vector. Here, we additionally provide sufficient conditions on the LCP matrix for the uniqueness of a solution. Moreover, based on characterizations of the affinely adjustable robust solutions, we derive a mixed-integer programming formulation that allows to solve the corresponding robust counterpart. If, in addition, the certain LCP matrix is positive semidefinite, we prove polynomial-time solvability and uniqueness of robust solutions. If the LCP matrix is uncertain, characterizations of solutions are developed for every nominal matrix, i.e., these characterizations are, in particular, independent of the definiteness of the nominal matrix. Robust solutions are also shown to be unique for positive definite LCP matrix but both uniqueness and mixed-integer programming formulations still remain open problems if the nominal LCP matrix is not positive definite.}, language = {en} } @misc{Manns2020, type = {Master Thesis}, author = {Manns, Julian}, title = {Presolve of Linear Bilevel Programs}, year = {2020}, abstract = {Bilevel programs are complex optimization problems that can be used to model hierarchical decision processes, which occur e.g. in energy markets, critical infrastructure defense or pricing models. Even the most simple bilevel programs, where only linear objective functions and constraints appear, are non-convex optimization problems and equivalent single level formulations replace the lower level problem by its non-convex optimality constraints. This makes linear bilevel programs inherently difficult so solve. The simplification of mixed-integer linear programs before solving them, called presolve, significantly accelerated the solving of these problems. However, there is only very few literature on the topic of presolve of bilevel programs. In this thesis we review said literature on presolve of bilevel programs in the context of linear bilevel programming, derive new theoretical foundations for presolve of linear bilevel programs and then apply these results to analyze how common presolve techniques for linear and mixed integer programs can be used to presolve linear bilevel programs.}, language = {en} } @article{ScheweSchmidtThuerauf, author = {Schewe, Lars and Schmidt, Martin and Th{\"u}rauf, Johannes}, title = {Global Optimization for the Multilevel European Gas Market System with Nonlinear Flow Models on Trees}, series = {Journal of Global Optimization}, journal = {Journal of Global Optimization}, doi = {10.1007/s10898-021-01099-8}, abstract = {The European gas market is implemented as an entry-exit system, which aims to decouple transport and trading of gas. It has been modeled in the literature as a multilevel problem, which contains a nonlinear flow model of gas physics. Besides the multilevel structure and the nonlinear flow model, the computation of so-called technical capacities is another major challenge. These lead to nonlinear adjustable robust constraints that are computationally intractable in general. We provide techniques to equivalently reformulate these nonlinear adjustable constraints as finitely many convex constraints including integer variables in the case that the underlying network is tree-shaped. We further derive additional combinatorial constraints that significantly speed up the solution process. Using our results, we can recast the multilevel model as a single-level nonconvex mixed-integer nonlinear problem, which we then solve on a real-world network, namely the Greek gas network, to global optimality. Overall, this is the first time that the considered multilevel entry-exit system can be solved for a real-world sized network and a nonlinear flow model.}, language = {en} }