Fränk Plein
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Fränk Plein has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Martin Schmidt
Trier University
6 shared publications - Martine Labbé
Département d'Informatique Université libre de Bruxelles Brussels Belgium
6 shared publications - Johannes Thürauf
Department Liberal Arts and Social Sciences, Discrete Optimization Lab, University of Technology Nuremberg (UTN), Nuremberg, Germany
3 shared publications - Thomas Kleinert
Quantagonia GmbH, Bad Homburg, Germany
2 shared publications - Eglantine Camby
Universite Libre de Bruxelles
1 shared publication
Latest Publications
- Open Access
- 23 September 2021
- Published by Springer Nature in Mathematical Methods of Operations Research
- Vol. 95 (3) , 409-449
A bilevel optimization approach to decide the feasibility of bookings in the European gas market
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 .
- 23 September 2021
- Published by Springer Nature in Mathematical Methods of Operations Research
- Vol. 95 (3) , 409-449
Open AccessA bilevel optimization approach to decide the feasibility of bookings in the European gas market
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 .
- Open Access
- 11 November 2020
- Published by Springer Nature in Optimization Letters
- Vol. 15 (4) , 1027-1040
Closing the gap in linear bilevel optimization: a new valid primal-dual inequality
Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker 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.
- 11 November 2020
- Published by Springer Nature in Optimization Letters
- Vol. 15 (4) , 1027-1040
Open AccessClosing the gap in linear bilevel optimization: a new valid primal-dual inequality
Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker 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.
- Top Cited Papers
- 1 November 2020
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 68 (6) , 1716-1721
Technical Note—There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization
There's No Free Lunch in Bilevel Optimization
- 1 November 2020
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 68 (6) , 1716-1721
Top Cited PapersTechnical Note—There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization
There's No Free Lunch in Bilevel Optimization
- Open Access
Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks
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.
Open AccessDeciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks
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.
- 17 July 2019
- Published by Springer Nature in Optimization and Engineering
- Vol. 21 (1) , 305-334
Bookings in the European gas market: characterisation of feasibility and computational complexity results
- 17 July 2019
- Published by Springer Nature in Optimization and Engineering
- Vol. 21 (1) , 305-334
Bookings in the European gas market: characterisation of feasibility and computational complexity results
- 1 January 2017
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 217, 711-717
A note on an induced subgraph characterization of domination perfect graphs
- 1 January 2017
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 217, 711-717
A note on an induced subgraph characterization of domination perfect graphs