TY - INPR A1 - Grübel, Julia A1 - Huber, Olivier A1 - Hümbs, Lukas A1 - Klimm, Max A1 - Schmidt, Martin A1 - Schwartz, Alexandra T1 - Nonconvex Equilibrium Models for Energy Markets: Exploiting Price Information to Determine the Existence of an Equilibrium N2 - 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. KW - Energy markets KW - Nonconvex games KW - Existence KW - Equilibrium computation KW - Perfect competition Y1 - 2021 ER - TY - GEN A1 - Beck, Yasmine A1 - Schmidt, Martin T1 - A Gentle and Incomplete Introduction to Bilevel Optimization N2 - These are lecture notes on bilevel optimization. The class of bilevel optimization problems is formally introduced and motivated using examples from different fields. Afterward, the main focus is on how to solve linear and mixed-integer linear bilevel optimization problems. To this end, we first consider various single-level reformulations of bilevel optimization problems with linear or convex follower problems, discuss geometric properties of linear bilevel problems, and study different algorithms for solving linear bilevel problems. Finally, we consider mixed-integer linear bilevel problems, discuss the main obstacles for deriving exact as well as effective solution methods, and derive a branch-and-bound method for solving these problems. KW - Bilevel Optimization KW - Lecture Notes Y1 - 2021 ER - TY - THES A1 - Plein, Fränk T1 - When Bilevel Optimization Meets Gas Networks: Feasibility of Bookings in the European Entry-Exit Gas Market. Computational Complexity Results and Bilevel Optimization Approaches N2 - Transport and trade of gas are decoupled after the liberalization of the European gas markets, which are now organized as so-called entry-exit systems. At the core of this market system are bookings and nominations, two special capacity-right contracts that grant traders access to the gas network. The latter is operated by a separate entity, known as the transmission system operator (TSO), who is in charge of the transport of gas from entry to exit nodes. In the mid to long term, traders sign a booking contract with the TSO to obtain injection and withdrawal capacities at entry and exit nodes, respectively. On a day-ahead basis, they then nominate within these booked capacities a balanced load flow of the planned amounts of gas to be injected into and withdrawn from the network the next day. The key property is that by signing a booking contract, the TSO is obliged to guarantee transportability for all balanced load flows in compliance with the booked capacities. To assess the feasibility of a booking, it is therefore necessary to check the feasibility of infinitely many nominations. As a result, deciding if a booking is feasible is a challenging mathematical problem, which we investigate in this dissertation. Our results range from passive networks, consisting of pipes only, to active networks, containing controllable elements to influence gas flows. Since the study of the latter naturally leads to a bilevel framework, we first consider some more general properties of bilevel optimization. For the case of linear bilevel optimization, we consider the hardness of validating the correctness of big-Ms often used in solving these problems via a single-level reformulation. We also derive a family of valid inequalities to be used in a bilevel-tailored branch-and-cut algorithm as a big-M-free alternative. We then turn to the study of feasible bookings. First, we present our results on passive networks, for which bilevel approaches are not required. A characterization of feasible bookings on passive networks is derived in terms of a finite set of nominations. While computing these nominations is a difficult task in general, we present polynomial complexity results for the special cases of tree-shaped or single-cycle passive networks. Finally, we consider networks with linearly modeled active elements. After obtaining a bilevel optimization model that allows us to determine the feasibility of a booking in this case, we derive various single-level reformulations to solve the problem. In addition, we obtain novel characterizations of feasible bookings on active networks, which generalize our characterization in the passive case. The performance of these various approaches is compared in a case study on two networks from the literature, one of which is a simplified version of the Greek gas network. Y1 - 2021 ER - TY - INPR A1 - De Santis, Marianna A1 - de Vries, Sven A1 - Schmidt, Martin A1 - Winkel, Lukas T1 - A Penalty Branch-and-Bound Method for Mixed-Binary Linear Complementarity Problems N2 - Linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations but also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, almost no tailored algorithms are known besides reformulations of the problem that allow to apply general-purpose mixed-integer linear programming solvers. In this paper, we present, theoretically analyze, enhance, and test a novel branch-and-bound method for MILCPs. The main property of this method is that we do not ``branch'' on constraints as usual but by adding suitably chosen penalty terms to the objective function. By doing so, we can either provably compute an MILCP solution if one exists or compute an approximate solution that minimizes an infeasibility measure combining integrality and complementarity conditions. We enhance the method by MILCP-tailored valid inequalities, node selection strategies, branching rules, and warmstarting techniques. The resulting algorithm is shown to clearly outperform two benchmark approaches from the literature. KW - Mixed-Integer Programming KW - Linear Complementarity Problems KW - Mixed-Integer Linear Complementarity Problems KW - Branch-and-Bound KW - Penalty Methods Y1 - 2021 ER - TY - JOUR A1 - Krug, Richard A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems with Mixed Two-Point Boundary Conditions JF - Control and Cybernetics N2 - 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. KW - Time-domain decomposition KW - Optimal control KW - Semilinear hyperbolic systems KW - Convergence Y1 - 2021 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Manns, Julian A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - Presolving Linear Bilevel Optimization Problems JF - EURO Journal on Computational Optimization N2 - 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. KW - Linear Bilevel Optimization KW - Presolve KW - Computational Analysis Y1 - 2021 U6 - https://doi.org/10.1016/j.ejco.2021.100020 IS - 9 ER - TY - INPR A1 - Egerer, Jonas A1 - Grimm, Veronika A1 - Grübel, Julia A1 - Zöttl, Gregor T1 - Long-run market equilibria in coupled energy sectors: A study of uniqueness N2 - 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. KW - Energy Markets KW - Sector Coupling KW - Regional Pricing KW - Uniqueness KW - Short- and Long-Run Market Equilibrium Y1 - 2021 ER - TY - THES A1 - Kleinert, Thomas T1 - Algorithms for Mixed-Integer Bilevel Problems with Convex Followers N2 - 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. Y1 - 2021 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Labbé, Martine A1 - Ljubić, Ivana A1 - Schmidt, Martin T1 - A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization JF - EURO Journal on Computational Optimization N2 - 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. KW - Bilevel optimization KW - Mixed-integer programming KW - Applications KW - Branch-and-bound KW - Branch-and-cut Y1 - 2021 ER - TY - INPR A1 - Hante, Falk A1 - Krug, Richard A1 - Schmidt, Martin T1 - Time-Domain Decomposition for Mixed-Integer Optimal Control Problems N2 - We consider mixed-integer optimal control problems, whose optimality conditions involve global combinatorial optimization aspects for the corresponding Hamiltonian pointwise in time. We propose a time-domain decomposition, which makes this problem class accessible for mixed-integer programming using parallel-in-time direct discretizations. The approach is based on a decomposition of the optimality system and the interpretation of the resulting subproblems as suitably chosen mixed-integer optimal control problems on subintervals in time. An iterative procedure then ensures continuity of the states at the boundaries of the subintervals via co-state information encoded in virtual controls. We prove convergence of this iterative scheme for discrete-continuous linear-quadratic problems and present numerical results both for linear-quadratic as well as nonlinear problems. KW - Mixed-integer optimal control problems KW - Time-domain decomposition KW - Mixed-integer nonlinear optimization KW - Convergence Y1 - 2021 ER - TY - JOUR A1 - Beck, Yasmine A1 - Schmidt, Martin T1 - A Robust Approach for Modeling Limited Observability in Bilevel Optimization JF - Operations Research Letters N2 - Many applications of bilevel optimization contain a leader facing a follower whose reaction deviates from the one expected by the leader due to some kind of bounded rationality. We consider bilinear bilevel problems with follower's response uncertainty due to limited observability regarding the leader's decision and exploit robust optimization to model the decision making of the follower. We show that the robust counterpart of the lower level allows to tackle the problem via the lower level's KKT conditions. KW - Bilevel optimization KW - Robust optimization KW - Bounded rationality KW - Limited observability KW - Reformulations Y1 - 2021 IS - 49(5) SP - 752 EP - 758 ER - TY - JOUR A1 - Plein, Fränk A1 - Thürauf, Johannes A1 - Labbé, Martine A1 - Schmidt, Martin T1 - A Bilevel Optimization Approach to Decide the Feasibility of Bookings in the European Gas Market JF - Mathematical Methods of Operations Research N2 - The European gas market is organized as a so-called entry-exit system with the main goal to decouple transport and trading. To this end, gas traders and the transmission system operator (TSO) sign so-called booking contracts that grant capacity rights to traders to inject or withdraw gas at certain nodes up to this capacity. On a day-ahead basis, traders then nominate the actual amount of gas within the previously booked capacities. By signing a booking contract, the TSO guarantees that all nominations within the booking bounds can be transported through the network. This results in a highly challenging mathematical problem. Using potential-based flows to model stationary gas physics, feasible bookings on passive networks, i.e., networks without controllable elements, have been characterized in the recent literature. In this paper, we consider networks with linearly modeled active elements such as compressors or control valves. Since these active elements allow the TSO to control the gas flow, the single-level approaches for passive networks from the literature are no longer applicable. We thus present a bilevel model to decide the feasibility of bookings in networks with active elements. While this model is well-defined for general active networks, we focus on the class of networks for which active elements do not lie on cycles. This assumption allows us to reformulate the original bilevel model such that the lower-level problem is linear for every given upper-level decision. Consequently, we derive several single-level reformulations for this case. Besides the classic Karush-Kuhn-Tucker reformulation, we obtain three problem-specific optimal-value-function reformulations. The latter also lead to novel characterizations of feasible bookings in networks with active elements that do not lie on cycles. We compare the performance of our methods by a case study based on data from the GasLib. KW - Gas networks KW - Bilevel optimization KW - European entry-exit market KW - Bookings KW - Active elements Y1 - 2021 U6 - https://doi.org/10.1007/s00186-021-00752-y ER - TY - INPR A1 - Heitsch, Holger A1 - Henrion, René A1 - Kleinert, Thomas A1 - Schmidt, Martin T1 - On Convex Lower-Level Black-Box Constraints in Bilevel Optimization with an Application to Gas Market Models with Chance Constraints N2 - Bilevel optimization is an increasingly important tool to model hierarchical decision making. However, the ability of modeling such settings makes bilevel problems hard to solve in theory and practice. In this paper, we add on the general difficulty of this class of problems by further incorporating convex black-box constraints in the lower level. For this setup, we develop a cutting-plane algorithm that computes approximate bilevel-feasible points. We apply this method to a bilevel model of the European gas market in which we use a joint chance constraint to model uncertain loads. Since the chance constraint is not available in closed form, this fits into the black-box setting studied before. For the applied model, we use further problem-specific insights to derive bounds on the objective value of the bilevel problem. By doing so, we are able to show that we solve the application problem to approximate global optimality. In our numerical case study we are thus able to evaluate the welfare sensitivity in dependence of the achieved safety level of uncertain load coverage. KW - Bilevel optimization KW - Black-box constraints KW - Chance constraints KW - Cutting planes KW - European gas market Y1 - 2021 ER - TY - INPR A1 - Grimm, Veronika A1 - Hintermüller, Michael A1 - Huber, Olivier A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - A PDE-Constrained Generalized Nash Equilibrium Approach for Modeling Gas Markets with Transport N2 - We investigate a class of generalized Nash equilibrium problems (GNEPs) in which the objectives of the individuals are interdependent and the shared constraint consists of a system of partial differential equations. This setup is motivated by the modeling of strategic interactions of competing firms, which explicitly take into account the dynamics of transporting a commodity, such as natural gas, through a network. We establish the existence of a variational equilibrium of the GNEP. In the case of symmetric firms, we identify an equivalent optimization problem. We use this model to numerically explore the impact of linepacking, that is the use of the network as a temporary storage device. In particular, we study the firms' decisions under various linepacking abilities and analyze which market participants benefit from it. Y1 - ER - TY - INPR A1 - Cattaruzza, Diego A1 - Labbé, Martine A1 - Petris, Matteo A1 - Roland, Marius A1 - Schmidt, Martin T1 - Exact and Heuristic Solution Techniques for Mixed-Integer Quantile Minimization Problems N2 - We consider mixed-integer linear quantile minimization problems that yield large-scale problems that are very hard to solve for real-world instances. We motivate the study of this problem class by two important real-world problems: a maintenance planning problem for electricity networks and a quantile-based variant of the classic portfolio optimization problem. For these problems, we develop valid inequalities and present an overlapping alternating direction method. Moreover, we discuss an adaptive scenario clustering method for which we prove that it terminates after a finite number of iterations with a global optimal solution. We study the computational impact of all presented techniques and finally show that their combination leads to an overall method that can solve the maintenance planning problem on large-scale real-world instances provided by the ROADEF challenge 2020 and that they also lead to significant improvements when solving a quantile-version of the classic portfolio optimization problem. KW - Quantile Minimization KW - Value-at-Risk (VaR) KW - Mixed-Integer Optimization KW - Valid Inequalities KW - Adaptive Clustering Y1 - 2021 ER - 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 -