@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{LabbePleinSchmidt2018, author = {Labb{\´e}, Martine and Plein, Fr{\"a}nk and Schmidt, Martin}, title = {Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results}, series = {Optimization and Engineering}, journal = {Optimization and Engineering}, number = {21(1)}, pages = {305 -- 334}, year = {2018}, abstract = {As a consequence of the liberalisation of the European gas market in the last decades, gas trading and transport have been decoupled. At the core of this decoupling are so-called bookings and nominations. Bookings are special capacity right contracts that guarantee that a specified amount of gas can be supplied or withdrawn at certain entry or exit nodes of the network. These supplies and withdrawals are nominated at the day-ahead. The special property of bookings then is that they need to be feasible, i.e., every nomination that complies with the given bookings can be transported. While checking the feasibility of a nomination can typically be done by solving a mixed-integer nonlinear feasibility problem, the verification of feasibility of a set of bookings is much harder. The reason is the robust nature of feasibility of bookings - namely that for a set of bookings to be feasible, all compliant nominations, i.e., infinitely many, need to be checked for feasibility. In this paper, we consider the question of how to verify the feasibility of given bookings for a number of special cases. For our physics model we impose a steady-state potential-based flow model and disregard controllable network elements. For this case we derive a characterisation of feasible bookings, which is then used to show that the problem is in coNP for the general case but can be solved in polynomial time for linear potential-based flow models. Moreover, we present a dynamic programming approach for deciding the feasibility of a booking in tree-shaped networks even for nonlinear flow models. It turns out that the hardness of the problem mainly depends on the combination of the chosen physics model as well as the specific network structure under consideration. Thus, we give an overview over all settings for which the hardness of the problem is known and finally present a list of open problems.}, 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{KleinertLabbePleinetal.2019, author = {Kleinert, Thomas and Labb{\´e}, Martine and Plein, Fr{\"a}nk and Schmidt, Martin}, title = {There's No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization}, series = {Operations Research}, journal = {Operations Research}, number = {68(6)}, pages = {1716 -- 1721}, year = {2019}, abstract = {One of the most frequently used approaches to solve linear bilevel optimization problems consists in replacing the lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions and by reformulating the KKT complementarity conditions using techniques from mixed-integer linear optimization. The latter step requires to determine some big-M constant in order to bound the lower level's dual feasible set such that no bilevel-optimal solution is cut off. In practice, heuristics are often used to find a big-M although it is known that these approaches may fail. In this paper, we consider the hardness of two proxies for the above mentioned concept of a bilevel-correct big-M. First, we prove that verifying that a given big-M does not cut off any feasible vertex of the lower level's dual polyhedron cannot be done in polynomial time unless P=NP. Second, we show that verifying that a given big-M does not cut off any optimal point of the lower level's dual problem (for any point in the projection of the high-point relaxation onto the leader's decision space) is as hard as solving the original bilevel problem.}, language = {en} } @unpublished{AlldredgeFrankGiesselmann2023, author = {Alldredge, Graham and Frank, Martin and Giesselmann, Jan}, title = {On the convergence of the regularized entropy-based moment method for kinetic equations}, volume = {9}, doi = {https://doi.org/10.5802/smai-jcm.93}, pages = {1-29}, year = {2023}, abstract = {The entropy-based moment method is a well-known discretization for the velocity variable in kinetic equations which has many desirable theoretical properties but is difficult to implement with high-order numerical methods. The regularized entropy-based moment method was recently introduced to remove one of the main challenges in the implementation of the entropy-based moment method, namely the requirement of the realizability of the numerical solution. In this work we use the method of relative entropy to prove the convergence of the regularized method to the original method as the regularization parameter goes to zero and give convergence rates. Our main assumptions are the boundedness of the velocity domain and that the original moment solution is Lipschitz continuous in space and bounded away from the boundary of realizability. We provide results from numerical simulations showing that the convergence rates we prove are optimal.}, language = {en} }