@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{PleinThueraufLabbeetal.2021, author = {Plein, Fr{\"a}nk and Th{\"u}rauf, Johannes and Labb{\´e}, Martine and Schmidt, Martin}, title = {A Bilevel Optimization Approach to Decide the Feasibility of Bookings in the European Gas Market}, series = {Mathematical Methods of Operations Research}, journal = {Mathematical Methods of Operations Research}, doi = {10.1007/s00186-021-00752-y}, pages = {37}, year = {2021}, abstract = {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.}, language = {en} } @article{LabbePleinSchmidtetal.2019, author = {Labb{\´e}, Martine and Plein, Fr{\"a}nk and Schmidt, Martin and Th{\"u}rauf, Johannes}, title = {Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks}, series = {Networks}, volume = {78}, journal = {Networks}, number = {2}, doi = {10.1007/s00186-021-00752-y}, pages = {128 -- 152}, year = {2019}, abstract = {We show that the feasibility of a booking in the European entry-exit gas market can be decided in polynomial time on single-cycle networks that are passive, i.e., do not contain controllable elements. The feasibility of a booking can be characterized by solving polynomially many nonlinear potential-based flow models for computing so-called potential-difference maximizing load flow scenarios. We thus analyze the structure of these models and exploit both the cyclic graph structure as well as specific properties of potential-based flows. This enables us to solve the decision variant of the nonlinear potential-difference maximization by reducing it to a system of polynomials of constant dimension that is independent of the cycle's size. This system of fixed dimension can be handled with tools from real algebraic geometry to derive a polynomial-time algorithm. The characterization in terms of potential-difference maximizing load flow scenarios then leads to a polynomial-time algorithm for deciding the feasibility of a booking. Our theoretical results extend the existing knowledge about the complexity of deciding the feasibility of bookings from trees to single-cycle networks.}, language = {en} } @unpublished{CattaruzzaLabbePetrisetal.2021, author = {Cattaruzza, Diego and Labb{\´e}, Martine and Petris, Matteo and Roland, Marius and Schmidt, Martin}, title = {Exact and Heuristic Solution Techniques for Mixed-Integer Quantile Minimization Problems}, pages = {35}, year = {2021}, abstract = {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.}, language = {en} }