389
2021
eng
29
preprint
1
2021-05-31
2021-05-31
--
Nonconvex Equilibrium Models for Energy Markets: Exploiting Price Information to Determine the Existence of an Equilibrium
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.
under review
publish
2
Creative Commons - CC BY - Namensnennung 4.0 International
Julia Grübel
Olivier Huber
Lukas Hümbs
Max Klimm
Martin Schmidt
Alexandra Schwartz
eng
uncontrolled
Energy markets
eng
uncontrolled
Nonconvex games
eng
uncontrolled
Existence
eng
uncontrolled
Equilibrium computation
eng
uncontrolled
Perfect competition
Friedrich-Alexander-Universität Erlangen-Nürnberg
Technische Universität Berlin
Weierstraß-Institut für Angewandte Analysis und Stochastik
A05
A07
B02
B07
B08
Universität Trier
B09
https://opus4.kobv.de/opus4-trr154/files/389/nonconvex-gas-markets_preprint_v2.pdf
394
2021
eng
24
preprint
1
2021-07-02
2021-07-02
--
A Penalty Branch-and-Bound Method for Mixed-Binary Linear Complementarity Problems
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.
under review
publish
2
Creative Commons - CC BY - Namensnennung 4.0 International
Marianna De Santis
Sven de Vries
Martin Schmidt
Lukas Winkel
eng
uncontrolled
Mixed-Integer Programming
eng
uncontrolled
Linear Complementarity Problems
eng
uncontrolled
Mixed-Integer Linear Complementarity Problems
eng
uncontrolled
Branch-and-Bound
eng
uncontrolled
Penalty Methods
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/394/8476.pdf
399
2021
eng
20
article
1
2021-07-13
2021-07-13
--
Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems with Mixed Two-Point Boundary Conditions
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.
Control and Cybernetics
Accepted
publish
2
Creative Commons - CC BY - Namensnennung 4.0 International
Richard Krug
Günter Leugering
Alexander Martin
Martin Schmidt
Dieter Weninger
eng
uncontrolled
Time-domain decomposition
eng
uncontrolled
Optimal control
eng
uncontrolled
Semilinear hyperbolic systems
eng
uncontrolled
Convergence
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/399/time-domain-decomp_tp_bnd_cond_preprint.pdf
380
2021
eng
9
article
1
2021-03-05
2021-03-05
--
Presolving Linear Bilevel Optimization Problems
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.
EURO Journal on Computational Optimization
10.1016/j.ejco.2021.100020
publish
2
Creative Commons - CC BY - Namensnennung 4.0 International
Thomas Kleinert
Julian Manns
Martin Schmidt
Dieter Weninger
eng
uncontrolled
Linear Bilevel Optimization
eng
uncontrolled
Presolve
eng
uncontrolled
Computational Analysis
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
Z01
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/380/bilevel_presolve_preprint.pdf
359
2020
eng
28
article
1
2020-11-29
2020-11-29
--
Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems
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.
SIAM Journal on Control and Optimization
2
Creative Commons - CC BY - Namensnennung 4.0 International
Richard Krug
Günter Leugering
Alexander Martin
Martin Schmidt
Dieter Weninger
eng
uncontrolled
Time-domain decomposition
eng
uncontrolled
Optimal control
eng
uncontrolled
Semilinear hyperbolic systems
eng
uncontrolled
Convergence
eng
uncontrolled
A posteriori error estimates
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/359/time-domain-decomp_preprint.pdf
361
2021
2021
eng
47
article
1
2021-01-01
2021-01-01
--
A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization
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.
EURO Journal on Computational Optimization
2
Creative Commons - CC BY - Namensnennung 4.0 International
Thomas Kleinert
Martine Labbé
Ivana Ljubić
Martin Schmidt
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
Mixed-integer programming
eng
uncontrolled
Applications
eng
uncontrolled
Branch-and-bound
eng
uncontrolled
Branch-and-cut
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/361/bilevel-survey-preprint.pdf
316
2020
2021
eng
27
article
1
2020-06-19
2020-06-19
--
The Cost of Decoupling Trade and Transport in the European Entry-Exit Gas Market with Linear Physics Modeling
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.
European Journal of Operational Research
2
Creative Commons - CC BY - Namensnennung 4.0 International
Tom Böttger
Veronika Grimm
Thomas Kleinert
Martin Schmidt
eng
uncontrolled
Entry-Exit Gas Market
eng
uncontrolled
Gas Market Design
eng
uncontrolled
Multilevel Optimization
eng
uncontrolled
Robust Optimization
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/316/b08-robust-bilevel_preprint.pdf
317
2020
eng
35
preprint
1
2020-07-21
2020-07-21
--
A Tractable Multi-Leader Multi-Follower Peak-Load-Pricing Model with Strategic Interaction
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.
10.1007/s10107-021-01708-0
"Mathematical Programming" forthcoming
2
Creative Commons - CC BY - Namensnennung 4.0 International
Veronika Grimm
Daniel Nowak
Lars Schewe
Martin Schmidt
Alexandra Schwartz
Gregor Zöttl
eng
uncontrolled
Game theory
eng
uncontrolled
Nash-Cournot equilibria
eng
uncontrolled
Multi-leader multi-follower game
eng
uncontrolled
Peak-load pricing
Friedrich-Alexander-Universität Erlangen-Nürnberg
Technische Universität Darmstadt
A05
B07
B08
Universität Trier
University of Edinburgh
B09
https://opus4.kobv.de/opus4-trr154/files/317/article_mainfile.pdf
319
2020
eng
20
preprint
1
2020-08-13
2020-08-13
--
Affinely Adjustable Robust Linear Complementarity Problems
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.
under review
2
Creative Commons - CC BY - Namensnennung 4.0 International
Christian Biefel
Frauke Liers
Jan Rolfes
Martin Schmidt
eng
uncontrolled
Linear Complementarity Problems
eng
uncontrolled
Adjustable Robustness
eng
uncontrolled
Robust Optimization
eng
uncontrolled
Existence
eng
uncontrolled
Uniqueness
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B06
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/319/adjustable-robust-lcps-preprint.pdf
322
eng
article
0
2020-08-21
2020-08-21
--
Global Optimization for the Multilevel European Gas Market System with Nonlinear Flow Models on Trees
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.
Journal of Global Optimization
10.1007/s10898-021-01099-8
Accepted
Creative Commons - CC BY - Namensnennung 4.0 International
Lars Schewe
Martin Schmidt
Johannes Thürauf
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
B08
Universität Trier
University of Edinburgh
https://opus4.kobv.de/opus4-trr154/files/322/technical-capacities-tree-modeling.pdf
323
eng
preprint
1
2020-08-24
2020-08-24
--
Solving AC Optimal Power Flow with Discrete Decisions to Global Optimality
We present a solution framework for general alternating current optimal power flow (AC OPF) problems that include discrete decisions.
The latter occur, for instance, in the context of the curtailment of renewables or the
switching of power generation units and transmission lines.
Our approach delivers globally optimal solutions and is provably convergent.
We model AC OPF problems with discrete decisions as mixed-integer nonlinear programs.
The solution method starts from a known framework that uses piecewise linear relaxations.
These relaxations are modeled as as mixed-integer linear programs and adaptively refined until some termination criterion is fulfilled.
In this work, we extend and complement this approach by problem-specific as well as very general algorithmic enhancements.
In particular, these are mixed-integer second-order cone programs as well as primal and dual cutting planes.
For example objective cuts and no-good-cuts help to compute good feasible solutions as where outer approximation constraints tighten the relaxations.
We present extensive numerical results for various AC OPF problems where discrete decisions play a major role.
Even for hard instances with a large proportion of discrete decisions, the method is able
to generate high quality solutions efficiently.
Furthermore, we compare our approach with state-of-the-art MINLP.
Our method outperforms all other algorithms.
under review
2
Creative Commons - CC BY - Namensnennung 4.0 International
Kevin-Martin Aigner
Robert Burlacu
Frauke Liers
Alexander Martin
eng
uncontrolled
Mixed-Integer Nonlinear Programming
eng
uncontrolled
Second-Order Cone Programming
eng
uncontrolled
AC Optimal Power Flow
eng
uncontrolled
Discrete Decisions
eng
uncontrolled
Piecewise Linear Relaxation
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B06
B07
B10
https://opus4.kobv.de/opus4-trr154/files/323/discrete-ac-opf.pdf
427
2021
eng
preprint
1
2021-10-07
--
--
Space-time-domain decomposition for optimal control problems governed by linear hyperbolic systems
In this article, we combine a domain decomposition method in space and time for optimal control problems with PDE-constraints described by Lagnese and Leugering to a simultaneous space-time decomposition applied to optimal control problems for systems of linear hyperbolic equations with distributed control. We thereby extend the recent work by Krug et al. and answer a long standing open question as to whether the combination of time- and space domain decomposition for the method under consideration can be put into one single convergent iteration procedure. The algorithm is designed for a semi-elliptic system of equations obtained from the hyperbolic optimality system by the way of reduction to the adjoint state. The focus is on the relation to the classical procedure introduced by Lions for elliptic problems.
accepted for publication
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Günter Leugering
eng
uncontrolled
Space- and time-domain decomposition
eng
uncontrolled
Optimal control
eng
uncontrolled
linear hyperbolic systems
eng
uncontrolled
Convergence
eng
uncontrolled
A posteriori error estimates
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
https://opus4.kobv.de/opus4-trr154/files/427/space_time_domain_decomp.pdf
343
2020
eng
8
preprint
1
2020-10-19
--
--
Why there is no need to use a big-M in linear bilevel optimization: A computational study of two ready-to-use approaches
Linear bilevel optimization problems have gained increasing attention both in theory as well as in practical applications of Operations Research (OR) during the last years and decades. The latter is mainly due to the ability of this class of problems to model hierarchical decision processes. However, this ability makes bilevel problems also very hard to solve. Since no general-purpose solvers are available, a "best-practice" has developed in the applied OR community, in which not all people want to develop tailored algorithms but "just use" bilevel optimization as a modeling tool for practice. This best-practice is the big-M reformulation of the Karush-Kuhn-Tucker (KKT) conditions of the lower-level problem - an approach that has been shown to be highly problematic by Pineda and Morales (2019). Choosing invalid values for M yields solutions that may be arbitrarily bad. Checking the validity of the big-Ms is however shown to be as hard as solving the original bilevel problem in Kleinert et al. (2019). Nevertheless, due to its appealing simplicity, especially w.r.t. the required implementation effort, this ready-to-use approach still is the most popular method. Until now, there has been a lack of approaches that are competitive both in terms of implementation effort and computational cost.
In this note we demonstrate that there is indeed another competitive ready-to-use approach: If the SOS-1 technique is applied to the KKT complementarity conditions, adding the simple additional root-node inequality developed by Kleinert et al. (2020) leads to a competitive performance - without having all the possible theoretical disadvantages of the big-M approach.
under review
Creative Commons - CC BY - Namensnennung 4.0 International
Thomas Kleinert
Martin Schmidt
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
Big-M
eng
uncontrolled
SOS-1
eng
uncontrolled
Valid inequalities
eng
uncontrolled
Computational analysis
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/343/bilevel_lp_lp_global_shortnote_preprint.pdf
344
2020
eng
16
preprint
1
2020-10-21
--
--
On Linear Bilevel Optimization Problems with Complementarity-Constrained Lower Levels
We consider a novel class of linear bilevel optimization models with a lower level that is a linear program with complementarity constraints (LPCC). We present different single-level reformulations depending on whether the linear complementarity problem (LCP) as part of the lower-level constraint set depends on the upper-level decisions or not as well as on whether the LCP matrix is positive definite or positive semidefinite. Moreover, we illustrate the connection to linear trilevel models that can be reduced to bilevel problems with LPCC lower levels having positive (semi)definite matrices. Finally, we provide two generic and illustrative bilevel models from the fields of transportation and energy to show the practical relevance of the newly introduced class of bilevel problems and show related theoretical results.
under review
Creative Commons - CC BY - Namensnennung 4.0 International
Steven A. Gabriel
Marina Leal
Martin Schmidt
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
Linear programs with complementarity constraints
eng
uncontrolled
Linear complementarity problems
eng
uncontrolled
Reformulations
eng
uncontrolled
Spatial price equilibria
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/344/bilevel-w-lower-level-lpcc-preprint.pdf
363
2021
2021
eng
752
758
7
49(5)
article
1
2021-01-07
2021-01-07
--
A Robust Approach for Modeling Limited Observability in Bilevel Optimization
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.
Operations Research Letters
under review
2
Creative Commons - CC BY - Namensnennung 4.0 International
Yasmine Beck
Martin Schmidt
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
Robust optimization
eng
uncontrolled
Bounded rationality
eng
uncontrolled
Limited observability
eng
uncontrolled
Reformulations
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/363/bilevel-bounded-observability-preprint.pdf
364
2021
2021
eng
37
article
1
2021-01-28
2021-01-28
--
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 GasLib.
Mathematical Methods of Operations Research
10.1007/s00186-021-00752-y
Published
2
Creative Commons - CC BY - Namensnennung 4.0 International
Fränk Plein
Johannes Thürauf
Martine Labbé
Martin Schmidt
eng
uncontrolled
Gas networks
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
European entry-exit market
eng
uncontrolled
Bookings
eng
uncontrolled
Active elements
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
B08
Universität Trier
Université libre de Bruxelles
https://opus4.kobv.de/opus4-trr154/files/364/validation-active-elements.pdf
371
2021
eng
34
preprint
1
2021-02-26
--
--
On Convex Lower-Level Black-Box Constraints in Bilevel Optimization with an Application to Gas Market Models with Chance Constraints
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.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Holger Heitsch
René Henrion
Thomas Kleinert
Martin Schmidt
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
Black-box constraints
eng
uncontrolled
Chance constraints
eng
uncontrolled
Cutting planes
eng
uncontrolled
European gas market
Friedrich-Alexander-Universität Erlangen-Nürnberg
Weierstraß-Institut für Angewandte Analysis und Stochastik
A05
B04
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/371/bilevel_chance_constraint_preprint.pdf
415
2021
eng
18
preprint
1
2021-08-20
2021-08-20
--
Space-Time-Domain Decomposition for Optimal Control Problems Governed by Linear Hyperbolic Systems
In this article, we combine a domain decomposition method in space and time for optimal control problems with PDE-constraints described by Lagnese and Leugering to a simultaneous space-time decomposition applied to optimal control problems for systems of linear hyperbolic equations with distributed control. We thereby extend the recent work by Krug et al. and answer a long standing open question as to whether the combination of time- and space domain decomposition for the method under consideration can be put into one single convergent iteration procedure. The algorithm is designed for a semi-elliptic system of equations obtained from the hyperbolic optimality system by the way of reduction to the adjoint state. The focus is on the relation to the classical procedure introduced by Lions for elliptic problems.
under review
publish
false
false
2
Creative Commons - CC BY - Namensnennung 4.0 International
Günter Leugering
eng
uncontrolled
Space- and time-domain decomposition
eng
uncontrolled
Optimal control
eng
uncontrolled
linear hyperbolic systems
eng
uncontrolled
Convergence
eng
uncontrolled
A posteriori error estimates
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
https://opus4.kobv.de/opus4-trr154/files/415/space-time-domain-decompostion.pdf
416
eng
25
40
16
1st Edition
Computational Science and Its Applications
article
1
2021-08-20
2021-08-20
--
Industrial Applications of Optimal Control for Partial Differential Equations on Networks: Reduction and Decomposition Methods Applied to the Discrete–Continuous Control of Gas Flow in Complex Pipe Systems
This chapter provides an exemplary road map—in a nutshell—from a given industrial application, the control of gas networks, which is far too complex for a direct approach, to a problem that can be actually handled using well-known methods in control theory. It also provides an iterative non-overlapping domain decomposition that can be interpreted as an Uzawa method. The chapter outline two strategies. The first one can be seen as a Jacobi-type approach. In the second approach, fix the integer controls s and decompose the corresponding optimality system for the entire graph into the subgraphs Gk by a another, but very similar, non-overlapping domain decomposition. The problem is the intrinsic coupling of integer controls, continuous controls, and nonlinear dynamics on a metric graph. The idea is to introduce a virtual control that aims at controlling classical in homogeneous Neumann condition including the iteration history at the interface as inhomogeneity to the Robin-type condition that appears in the decomposition.
in press
publish
2
Creative Commons - CC BY - Namensnennung 4.0 International
Günter Leugering
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
https://opus4.kobv.de/opus4-trr154/files/416/sharda2018-contribution-leugering.pdf
419
2021
eng
preprint
1
2021-09-02
2021-09-02
--
Transient gas pipeline flow: Analytical examples, numerical simulation and a comparison to the quasi-static approach
The operation of gas pipeline flow with high pressure and small Mach numbers allows to model the flow by a semilinear hyperbolic system of partial differential equations. In this paper we present a number of transient and stationary analytical solutions of this model. They are used to discuss and clarify why a pde model is necessary to handle certain dynamic situations in the operation of gas transportation networks. We show that adequate numerical discretizations can capture the dynamical behavior sufficiently accurate. We also present examples that show that in certain cases an optimization approach that is based upon multi-period optimization of steady states does not lead to approximations that converge to the optimal state.
10.1007/s11081-021-09690-4
under review
publish
2
Creative Commons - CC BY - Namensnennung 4.0 International
Martin Gugat
Richard Krug
Alexander Martin
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
C03
C05
https://opus4.kobv.de/opus4-trr154/files/419/transient-gas.pdf
145
2017
2019
eng
449
483
35
178(1)
article
1
2017-07-17
2017-07-17
--
A Decomposition Method for MINLPs with Lipschitz Continuous Nonlinearities
Many mixed-integer optimization problems are constrained by nonlinear functions that do not possess desirable analytical properties like convexity or factorability or cannot even be evaluated exactly. This is, e.g., the case for problems constrained by differential equations or for models that rely on black-box simulation runs. For these problem classes, we present, analyze, and test algorithms that solve mixed-integer problems with only Lipschitz continuous nonlinearities. Our theoretical results depend on the assumptions made on the (in)exactness of function evaluations and on the knowledge of Lipschitz constants. If Lipschitz constants are known, we prove finite termination at approximate globally optimal points both for the case of exact and inexact function evaluations. If only approximate Lipschitz constants are known, we prove finite termination and derive additional conditions under which infeasibility can be detected. A computational study for gas transport problems and an academic case study show the applicability of our algorithms to real-world problems and how different assumptions on the constraint functions up- or downgrade the practical performance of the methods.
Mathematical Programming
2
Martin Schmidt
Mathias Sirvent
Winnifried Wollner
eng
uncontrolled
Mixed-Integer Nonlinear Optimization, Lipschitz Optimization, Inexact Function Evaluations, Decomposition Methods, Gas Networks
Friedrich-Alexander-Universität Erlangen-Nürnberg
Technische Universität Darmstadt
A05
B08
A08
https://opus4.kobv.de/opus4-trr154/files/145/global-mi-opt-lipschitz_preprint.pdf
179
2017
eng
419
448
3
7
article
1
2017-10-12
2017-10-12
--
Neumann boundary feedback stabilization for a nonlinear wave equation: A strict H2-Lyapunov function
For a system that is governed by the isothermal Euler equations with friction for ideal gas, the corresponding field of characteristic curves is determined by the velocity of the flow. This velocity is determined by a second-order quasilinear hyperbolic equation. For the corresponding initial-boundary value problem with Neumann-boundary feedback, we consider non-stationary solutions locally around a stationary state on a finite time interval and discuss the well-posedness of this kind of problem. We introduce a strict H2-Lyapunov function and show that the boundary feedback constant can be chosen such that the H2-Lyapunov function and hence also the H2-norm of the difference between the non-stationary and the stationary state decays exponentially with time.
Mathematical Control and Related Fields (MCRF)
10.3934/mcrf.2017015
in press
2
Martin Gugat
Günter Leugering
Ke Wang
eng
uncontrolled
Boundary feedback control, feedback stabilization, exponential stability, isothermal Euler equations, second-order quasilinear equation, Lyapunov function, stationary state, non-stationary state, gas pipeline.
Friedrich-Alexander-Universität Erlangen-Nürnberg
A03
A05
C03
192
2017
eng
15
International Series for Numerical Mathematics
conferenceobject
Birkhäuser
1
2017-11-03
2017-11-03
--
Instantaneous optimal control of friction dominated flow in a gas-network
We consider optimal control problems for the flow of gas
in a pipe network. The equations of motions are taken to be represented
by a nonlinear model derived from a semi-linear approximation
of the fully nonlinear isothermal Euler gas equations. We formulate
an optimal control problem on a given network and introduce a time
discretization thereof. We then study the well-posedness of the corresponding
time-discrete optimal control problem. In order to further
reduce the complexity, we consider an instantaneous control strategy.
This involves a p-Laplace-type problem on the graph with p =3/2. We
prove well-posedness, existence of optimal controls and derive a first
order optimality condition.
DFG-AIMS-Workshop, in Mbour, Senegal, 13-16. March 2017
accepted for publication
2
Günter Leugering
Gisèle Mophou
A05
https://opus4.kobv.de/opus4-trr154/files/192/frcition-dominated-flow.pdf
121
2016
eng
40
article
1
2016-12-09
2016-12-09
--
Challenges in optimal control problems for gas and fluid flow in networks of pipes and canals: From modeling to industrial applications
We consider optimal control problems for the flow of gas or fresh water in pipe networks as well as drainage or sewer systems in open canals. The equations of motion are taken to be represented by the nonlinear isothermal Euler gas equations, the water hammer equations, or the St.~Venant equations for flow. We formulate model hierarchies and derive an abstract model for such network flow problems including pipes, junctions, and controllable elements such as valves, weirs, pumps, as well as compressors. We use the abstract model to give an overview of the known results and challenges concerning equilibria, well-posedness, controllability, and optimal control. A major challenge concerning the optimization is to deal with switching on-off states that are inherent to controllable devices in such applications combined with
continuous simulation and optimization of the gas flow. We formulate the corresponding mixed-integer nonlinear optimal control problems and outline a decomposition approach as a solution technique.
2
Falk Hante
Günter Leugering
Alexander Martin
Lars Schewe
Martin Schmidt
eng
uncontrolled
Networks
eng
uncontrolled
pipes
eng
uncontrolled
optimal control
eng
uncontrolled
Euler and St. Venant equations
eng
uncontrolled
hierarchy of models
Friedrich-Alexander-Universität Erlangen-Nürnberg
A03
A05
B07
B08
https://opus4.kobv.de/opus4-trr154/files/121/isiam-paper.pdf
168
2017
eng
18
2
4
article
1
2017-12-01
2017-12-01
--
GasLib – A Library of Gas Network Instances
The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances that can be used by researchers in the field of gas transport. The advantages are that researchers save time by using these instances and that different models and algorithms can be compared on the same specified test sets. The library instances are encoded in an XML format. In this paper, we explain this format and present the instances that are available in the library.
Data
10.3390/data2040040
Martin Schmidt
Denis Aßmann
Robert Burlacu
Jesco Humpola
Imke Joormann
Nikolaos Kanelakis
Thorsten Koch
Djamal Oucherif
Marc E. Pfetsch
Lars Schewe
Robert Schwarz
Mathias Sirvent
eng
uncontrolled
Gas Transport
eng
uncontrolled
Networks
eng
uncontrolled
Problem Instances
eng
uncontrolled
Mixed-Integer Nonlinear Optimization
eng
uncontrolled
GasLib
Friedrich-Alexander-Universität Erlangen-Nürnberg
Technische Universität Darmstadt
A01
A05
A07
B06
B07
Z01
Z02
B08
175
2017
eng
1074-1099
8
periodical
1
2017-08-17
2017-10-12
--
Domain Decomposition of an Optimal Control Problem for Semi-Linear Elliptic Equations on Metric Graphs with Application to Gas Networks
We consider optimal control problems for the flow of gas in a pipe network.
The equations of motions are taken to be represented by a semi-linear model
derived from the fully nonlinear isothermal Euler gas equations. We formulate
an optimal control problem on a given network and introduce a time discretization
thereof. We then study the well-posedness of the corresponding
time-discrete optimal control problem. In order to further reduce the complexity,
we consider an instantaneous control strategy. The main part of the
paper is concerned with a non-overlapping domain decomposition of the
semi-linear elliptic optimal control problem on the graph into local problems
on a small part of the network, ultimately on a single edge.
https://doi.org/10.4236/am.2017.88082
2152-7393
epub ahead of print
2
Günter Leugering
deu
swd
28
eng
uncontrolled
nonoverlapping omain decomposition, optimal control of semi-linear ellioptic systems on netowrks
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
https://opus4.kobv.de/opus4-trr154/files/175/Leugering-AM.pdf
93
2015
eng
749
785
4
10
article
1
2016-09-20
2016-09-20
--
Analysis of a system of nonlocal conservation laws for multi-commodity flow on networks
We consider a system of scalar nonlocal conservation laws on networks that model a highly re-entrant multi-commodity manufacturing system as encountered in semiconductor production. Every single commodity is mod-eled by a nonlocal conservation law, and the corresponding PDEs are coupled via a collective load, the work in progress. We illustrate the dynamics for two commodities. In the applications, directed acyclic networks naturally occur, therefore this type of networks is considered. On every edge of the network we have a system of coupled conservation laws with nonlocal velocity. At the junctions the right hand side boundary data of the foregoing edges is passed as left hand side boundary data to the following edges and PDEs. For distributing junctions, where we have more than one outgoing edge, we impose time dependent distribution functions that guarantee conservation of mass. We provide results of regularity, existence and well-posedness of the multi-commodity network model for L p-, BV-and W 1,p-data. Moreover, we define an L 2-tracking type objective and show the existence of minimizers that solve the corresponding optimal control problem.
Networks and Heterogeneous Media
DOI: 10.3934/nhm.2015.10.749
in press
2
Martin Gugat
Alexander Keimer
Günter Leugering
Zhiqiang Wang
eng
uncontrolled
conservation laws on network
eng
uncontrolled
nonlocal conservation laws
eng
uncontrolled
optimal nodal control
eng
uncontrolled
systems of hyperbolic pdes
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
C03
https://opus4.kobv.de/opus4-trr154/files/93/document.pdf
95
2015
eng
article
1
2016-09-25
2016-09-25
--
Time delay in optimal control loops for wave equations
In optimal control loops delays can occur, for example through transmission via digital communication channels. Such delays influence the state that is generated by the implemented control. We study the effect of a delay in the implementation of L 2-norm minimal Neumann boundary controls for the wave equation. The optimal controls are computed as solutions of problems of exact optimal control, that is if they are implemented without delay, they steer the system to a position of rest in a given finite time T. We show that arbitrarily small delays δ > 0 can have a destabilizing effect in the sense that we can find initial states such that if the optimal control u is implemented in the form yx(t, 1) = u(t − δ) for t > δ, the energy of the system state at the terminal time T is almost twice as big as the initial energy. We also show that for more regular initial states, the effect of a delay in the implementation of the optimal control is bounded above in the sense that for initial positions with derivatives of BV-regularity and initial velocities with BV-regularity, the terminal energy is bounded above by the delay δ multiplied with a factor that depends on the BV-norm of the initial data. We show that for more general hyperbolic optimal exact control problems the situation is similar. For systems that have arbitrarily large eigenvalues, we can find terminal times T and arbitrarily small time delays δ, such that at the time T + δ, in the optimal control loop with delay the norm of the state is twice as large as the corresponding norm for the initial state. Moreover, if the initial state satisfies an additional regularity condition, there is an upper bound for the effect of time delay of the order of the delay with a constant that depends on the initial state only.
ESAIM: COCV
http://dx.doi.org/10.1051/cocv/2015038
epub ahead of print
2
Martin Gugat
Günter Leugering
eng
uncontrolled
PDE constrained optimization
eng
uncontrolled
delay
eng
uncontrolled
wave equation
eng
uncontrolled
boundary control
eng
uncontrolled
hyperbolic system
Friedrich-Alexander-Universität Erlangen-Nürnberg
A03
A05
C03
https://opus4.kobv.de/opus4-trr154/files/95/cocv150038.pdf
96
2016
eng
article
1
2016-09-27
2016-09-27
--
Networks of pipelines for gas with nonconstant compressibility factor: stationary states
For the management of gas transportation networks, it is essential to know how the stationary states of the system are determined by the boundary data. The isothermal Euler equations are an accurate pde-model for the gas flow through each pipe. A compressibility factor is used to model the nonlinear relationship between density and pressure that occurs in real gas in contrast to ideal gas. The gas flow through the nodes is governed by algebraic node conditions that require the conservation of mass and the continuity of the pressure. We examine networks that are described by arbitrary finite graphs and show that for suitably chosen boundary data, subsonic stationary states exist and are uniquely determined by the boundary data. Our construction of the stationary states is based upon explicit representations of the stationary states on each single pipe that can easily be evaluated numerically. We also use the monotonicity properties of these states as functions of the boundary data.
Computational and Applied Mathematics
10.1007/s40314-016-0383-z
epub ahead of print
2
Martin Gugat
David Wintergerst
Rüdiger Schultz
Friedrich-Alexander-Universität Erlangen-Nürnberg
Universität Duisburg-Essen
A05
B05
C03
https://opus4.kobv.de/opus4-trr154/files/96/zfactorstationarystatesforgasnetworks.pdf
97
2015
eng
189
217
2
7
article
1
2015-03-25
2015-03-25
--
Solving network design problems via iterative aggregation
In this work, we present an exact approach for solving network design problems that is based on an iterative graph aggregation procedure. The scheme allows existing preinstalled capacities. Starting with an initial aggregation, we solve a sequence of network design master problems over increasingly fine-grained representations of the original network. In each step, a subproblem is solved that either proves optimality of the solution or gives a directive where to refine the representation of the network in the subsequent iteration. The algorithm terminates with a globally optimal solution to the original problem. Our implementation uses a standard integer programming solver for solving the master problems as well as the subproblems. The computational results on random and realistic instances confirm the profitable use of the iterative aggregation technique. The computing time often reduces drastically when our method is compared to solving the original problem from scratch.
Mathematical Programming Computation
10.1007/s12532-015-0079-1
2
Andreas Bärmann
Frauke Liers
Alexander Martin
Maximilian Merkert
Christoph Thurner
Dieter Weninger
eng
uncontrolled
Aggregation
eng
uncontrolled
Network design
eng
uncontrolled
Combinatorial optimization
eng
uncontrolled
Mixed-integer programming
eng
uncontrolled
Branch-and-cut
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B06
B07
99
2016
eng
24
preprint
0
2016-09-06
2016-09-28
--
Staircase Compatibility and its Applications in Scheduling and Piecewise Linearization
We consider the clique problem with multiple-choice constraints (CPMC) and characterize a case where it is possible to give an efficient description of the convex hull of its feasible solutions. This case, which we call staircase compatibility, generalizes common properties in applications and allows for a linear description of the integer feasible solutions to (CPMC) with a totally unimodular constraint matrix
of polynomial size. We derive two such totally unimodular reformulations for the problem: one that is obtained by a strengthening of the compatibility constraints
and one that is based on a representation as a dual network flow problem. Furthermore, we show a natural way to derive integral solutions from fractional solutions to the problem by determining integral extreme points generating this fractional
solution. We also evaluate our reformulations from a computational point of view by applying them to two different real-world applications. The first one is
a problem in railway timetabling where we try to adapt a given timetable slightly such that energy costs from operating the trains are reduced. The second one is the piecewise linearization of non-linear flow problems on a gas network. In both cases, we are able to reduce the solution times significantly by passing to the theoretically stronger formulations of the problem.
under review
2
Andreas Bärmann
Thorsten Gellermann
Maximilian Merkert
Oskar Schneider
eng
uncontrolled
Clique Problem
eng
uncontrolled
Multiple-Choice Constraints
eng
uncontrolled
Total Unimodularity
eng
uncontrolled
Scheduling
eng
uncontrolled
Piecewise Linearization
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B06
B07
https://opus4.kobv.de/opus4-trr154/files/99/StaircaseCompatibility-Preprint-0916.pdf
198
2015
deu
other
1
2015-03-30
--
--
Gasnetzwerke: Mathematische Modellierung, Simulation und Optimierung
Im Mai 2014 wurde seitens der DFG der Transregio
154 Mathematische Modellierung, Simulation und
Optimierung am Beispiel von Gasnetzwerken bewilligt.
Die Forschungsarbeiten an den beteiligten Standorten,
der Friedrich-Alexander-Universität Erlangen-Nürnberg
(Sprecheruniversität; Sprecher: Alexander Martin), der
Technischen Universität Darmstadt (stellvertretender
Sprecher: Jens Lang), der Technischen Universität Berlin,
der Humboldt Universität (stellvertretende Sprecherin:
Caren Tischendorf) sowie den Partnerinstitutionen
Weierstraß-Institut (Berlin), Konrad-Zuse-Zentrum (Berlin)
und Universität Duisburg-Essen haben im Oktober
2014 begonnen.
10.1515/dmvm-2015-0013
2
Jens Lang
Günter Leugering
Alexander Martin
Caren Tischendorf
A05
B01
B07
C02
https://opus4.kobv.de/opus4-trr154/files/198/MDMV2015-LangLeugeringMartinTischendorf.pdf
202
2017
eng
191
225
35
3
46
article
Control and Cybernetics
1
2017-11-17
2017-11-17
--
Nonoverlapping Domain Decomposition for Optimal Control Problems governed by Semilinear Models for Gas Flow in Networks
We consider optimal control problems for gas flow in pipeline networks. The equations of motion are taken to be represented by a first-order system of hyperbolic semilinear equations derived from the fully nonlinear isothermal Euler gas equations. We formulate an optimal control problem on a network and introduce a tailored time discretization thereof. In order to further reduce the complexity, we consider an instantaneous control strategy. The main part of the paper is concerned with a nonoverlapping domain decomposition of the optimal control problem on the graph into local problems on smaller sub-graphs - ultimately on single edges. We prove convergence of the domain decomposition method on networks and study the wellposedness of the corresponding time-discrete optimal control problems. The point of the paper is that we establish virtual control problems on the decomposed subgraphs such that the corresponding optimality systems are in fact equal to the systems obtained via the domain decomposition of the entire optimality system.
submitted
Günter Leugering
Alexander Martin
Martin Schmidt
Mathias Sirvent
eng
uncontrolled
Optimal control, Gas networks, Euler's equation, Semilinear PDE, Nonoverlapping domain decomposition
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
B08
109
2016
eng
493
509
2
254
article
1
2016-04-06
2016-10-20
--
Transmission and generation investment in electricity markets: The effects of market splitting and network fee regimes
We propose an equilibrium model that allows to analyze the long-run impact of the electricity market design on transmission line expansion by the regulator and investment in generation capacity by private firms in liberalized electricity markets. The model incorporates investment decisions of the transmission system operator and private firms in expectation of an energy-only market and cost-based redispatch. In different specifications we consider the cases of one vs. multiple price zones (market splitting) and analyze different approaches to recover network cost—in particular lump sum, generation capacity based, and energy based fees. In order to compare the outcomes of our multilevel market model with a first best benchmark, we also solve the corresponding integrated planner problem. Using two test networks we illustrate that energy-only markets can lead to suboptimal locational decisions for generation capacity and thus imply excessive network expansion. Market splitting heals these problems only partially. These results are valid for all considered types of network tariffs, although investment slightly differs across those regimes.
European Journal of Operational Research
10.1016/j.ejor.2016.03.044
2
Veronika Grimm
Alexander Martin
Martin Schmidt
Martin Weibelzahl
Gregor Zöttl
eng
uncontrolled
Electricity market modeling
eng
uncontrolled
Mixed-integer nonlinear optimization
eng
uncontrolled
Multilevel programming
eng
uncontrolled
Network expansion
eng
uncontrolled
Transmission management
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
63
2018
eng
24
article
1
2018-03-12
2018-03-12
--
Towards Simulation Based Mixed-Integer Optimization with Differential Equations
We propose a decomposition based method for solving mixed-integer nonlinear optimization problems with “black-box” nonlinearities, where the latter, e.g., may arise due to differential equations or expensive simulation runs. The method alternatingly solves a mixed-integer linear master problem and a separation problem for iteratively refining the mixed-integer linear relaxation of the nonlinear equalities. The latter yield nonconvex feasible sets for the optimization model but we have to restrict ourselves to convex and monotone constraint functions. Under these assumptions, we prove that our algorithm finitely terminates with an approximate feasible global optimal solution of the mixed integer nonlinear problem. Additionally, we show the applicability of our approach for three applications from optimal control with integer variables, from the field of pressurized flows in pipes with elastic walls, and from steady-state gas transport. For the latter we also present promising numerical results of our method applied to real-world instances that particularly show the effectiveness of our method for problems defined on networks.
Networks
10.1002/net.21812
2
Martin Gugat
Günter Leugering
Alexander Martin
Martin Schmidt
Mathias Sirvent
David Wintergerst
eng
uncontrolled
Mixed-Integer Optimization
eng
uncontrolled
Simulation Based Optimization
eng
uncontrolled
Optimization with Differential Equations
eng
uncontrolled
Decomposition Method
eng
uncontrolled
Gas Transport Networks
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
C03
B08
64
2017
2017
eng
364
374
3
5
article
1
2017-04-25
2017-01-09
--
A Linearized Model for the Optimization of the Coupled Electricity and Natural Gas System
In the following paper a combined optimization of a coupled electricity and gas system is presented. For the electricity network a unit commitment problem with optimization of energy and reserves under a power pool, considering all system operational and unit technical constraints is solved. The gas network subproblem is a medium-scale mixed-integer nonconvex and nonlinear programming problem. The coupling constraints between the two networks are nonlinear as well. The resulting mixed-integer nonlinear program is linearized with the extended incremental method and an outer approximation technique. The resulting model is evaluated using the Greek power and gas system comprising fourteen gas-fired units under four different approximation accuracy levels. The results indicate the efficiency of the proposed MIP model and the interplay between computational requirements and accuracy.
Journal of Modern Power Systems and Clean Energy
10.1007/s40565-017-0275-2
Mathias Sirvent
Nikolaos Kanelakis
Björn Geißler
Pandelis Biskas
eng
uncontrolled
Electricity System
eng
uncontrolled
Natural Gas System
eng
uncontrolled
Mixed-Integer (Non)Linear Programming
eng
uncontrolled
Extended Incremental Method
eng
uncontrolled
Outer Approximation
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
Z01
Aristotle University of Thessaloniki
73
2015
eng
295
320
2
10
article
1
2016-09-16
2016-09-16
--
Stationary States in Gas Networks
Pipeline networks for gas transportation often contain circles. For such networks it is more difficult to determine the stationary states than for networks without circles. We present a method that allows to compute the stationary states for subsonic pipe flow governed by the isothermal Euler equations for certain pipeline networks that contain circles. We also show that suitably chosen boundary data determine the stationary states uniquely. The construction is based upon novel explicit representations of the stationary states on single pipes for the cases with zero slope and with nonzero slope. In the case with zero slope, the state can be represented using the Lambert-W function.
Networks and Heterogeneous Media
doi:10.3934/nhm.2015.10.295
2
Martin Gugat
Günter Leugering
Falk Hante
eng
uncontrolled
Network
A03
A05
C03
https://opus4.kobv.de/opus4-trr154/files/73/stationarystatesforgasnetworksnhm.pdf
491
2022
eng
57
preprint
1
2022-06-24
--
--
A Survey on Bilevel Optimization Under Uncertainty
Bilevel optimization is a very active field of applied mathematics. The main reason is that bilevel optimization problems can serve as a powerful tool for modeling hierarchical decision making processes. This ability, however, also makes the resulting problems challenging to solve - both in theory and practice. Fortunately, there have been significant algorithmic advances in the field of bilevel optimization so that we can solve much larger and also more complicated problems today compared to what was possible to solve two decades ago. This results in more and more challenging bilevel problems that researchers try to solve today. This survey gives a detailed overview of one of these more challenging classes of bilevel problems: bilevel optimization under uncertainty. We review the classic ways of addressing uncertainties in bilevel optimization using stochastic or robust techniques. Moreover, we highlight that the sources of uncertainty in bilevel optimization are much richer than for usual, i.e., single-level, problems since not only the problem's data can be uncertain but also the (observation of the) decisions of the two players can be subject to uncertainty. We thus also review the field of bilevel optimization under limited observability, the area of problems considering only near-optimal decisions, and discuss intermediate solution concepts between the optimistic and pessimistic cases. Finally, we also review the rich literature on applications studied using uncertain bilevel problems such as in energy, for interdiction games and security applications, in management sciences, and networks.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Yasmine Beck
Ivana Ljubic
Martin Schmidt
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
Optimization under uncertainty
eng
uncontrolled
Bounded rationality
eng
uncontrolled
Survey
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/491/bilevel-under-uncertainty-survey-preprint.pdf
495
2022
eng
16
preprint
1
2022-07-01
--
--
Using Neural Networks to Solve Linear Bilevel Problems with Unknown Lower Level
Bilevel problems are used to model the interaction between two decision makers in which the lower-level problem, the so-called follower's problem, appears as a constraint in the upper-level problem of the so-called leader. One issue in many practical situations is that the follower's problem is not explicitly known by the leader. For such bilevel problems with unknown lower-level model we propose the use of neural networks to learn the follower's optimal response for given decisions of the leader based on available historical data of pairs of leader and follower decisions. Integrating the resulting neural network in a single-level reformulation of the bilevel problem leads to a challenging model with a black-box constraint. We exploit Lipschitz optimization techniques from the literature to solve this reformulation and illustrate the applicability of the proposed method with some preliminary case studies using academic and linear bilevel instances.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Ioana Molan
Martin Schmidt
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
Unknown follower problems
eng
uncontrolled
Neural networks
eng
uncontrolled
Lipschitz optimization
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/495/dnns-lipschitz-for-unknown-bilevel-preprint.pdf
497
2022
eng
9
preprint
1
2022-07-14
--
--
A Penalty Branch-and-Bound Method for Mixed-Integer Quadratic Bilevel Problems
We propose an algorithm for solving bilevel problems with mixed-integer convex-quadratic upper level as well as convex-quadratic and continuous lower level. The method is based on a classic branch-and-bound procedure, where branching is performed on the integer constraints and on the complementarity constraints resulting from the KKT reformulation of the lower-level problem. However, instead of branching on constraints as usual, suitably chosen penalty terms are added to the objective function in order to create new subproblems in the tree. We prove the correctness of the method and present its applicability by some first numerical results.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Andreas Horländer
Martin Schmidt
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
Branch-and-bound
eng
uncontrolled
Penalty methods
eng
uncontrolled
Mixed-integer optimization
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/497/penalty-bnb-for-bilevel-preprint.pdf
453
2019
eng
article
0
2019-11-15
--
--
Modeling Hydrogen Networks for Future Energy Systems: A Comparison of Linear and Nonlinear Approaches
Common energy system models that integrate hydrogen transport in pipelines typically simplify fluid flow models and reduce the network size in order to achieve solutions quickly. This contribution analyzes two different types of pipeline network topologies (namely, star and tree networks) and two different fluid flow models (linear and nonlinear) for a given hydrogen capacity scenario of electrical reconversion in Germany to analyze the impact of these simplifications. For each network topology, robust demand and supply scenarios are generated. The results show that a simplified topology, as well as the consideration of detailed fluid flow, could heavily influence the total pipeline investment costs. For the given capacity scenario, an overall cost reduction of the pipeline costs of 37% is observed for the star network with linear cost compared to the tree network with nonlinear fluid flow. The impact of these improvements regarding the total electricity reconversion costs has led to a cost reduction of 1.4%, which is fairly small. Therefore, the integration of nonlinearities into energy system optimization models is not recommended due to their high computational burden. However, the applied method for generating robust demand and supply scenarios improved the credibility and robustness of the network topology, while the simplified fluid flow consideration can lead to infeasibilities. Thus, we suggest the utilization of the nonlinear model for post- processing to prove the feasibility of the results and strengthen their credibility, while retaining the computational performance of linear modeling.
International Journal of Hydrogen Energy
10.1016/j.ijhydene.2019.10.080
Published
Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International
Markus Reuß
Lara Welder
Johannes Thürauf
Jochen Linßen
Thomas Grube
Lars Schewe
Martin Schmidt
Detlef Stolten
Martin Robinius
A05
B07
B08
https://opus4.kobv.de/opus4-trr154/files/453/Modeling_Hydrogen_Networks_for_Energy_Systems.pdf
476
2021
eng
preprint
0
2021-11-12
--
--
Computing optimality certificates for convex mixed-integer nonlinear problems
Every optimization problem has a corresponding verification problem which verifies whether a given optimal solution is in fact optimal. In the literature there are a lot of such ways to verify optimality for a given solution, e.g., the branch-and-bound tree. To simplify this task, Baes et al. introduced optimality certificates for convex mixed-integer nonlinear programs and proved that these are bounded in the number of integer variables. We introduce an algorithm to compute the certificates and conduct computational experiments. Through the experiments we show that the optimality certificates can be surprisingly small.
publish
false
false
Creative Commons - CC BY - Namensnennung 4.0 International
Katrin Halbig
Lukas Hümbs
Florian Rösel
Lars Schewe
Dieter Weninger
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
https://opus4.kobv.de/opus4-trr154/files/476/optimality_certificates_preprint.pdf
480
eng
preprint
1
2021-11-29
--
--
Robust DC Optimal Power Flow with Modeling of Solar Power Supply Uncertainty via R-Vine Copulas
We present a robust approximation of joint chance constrained DC Optimal Power Flow in combination with a model-based prediction of uncertain power supply via R-vine copulas.
It is applied to optimize the discrete curtailment of solar feed-in in an electrical distribution network and guarantees network stability under fluctuating feed-in.
This is modeled by a two-stage mixed-integer stochastic optimization problem proposed by Aigner et al. (European Journal of Operational Research, (2021)).
The solution approach is based on the approximation of chance constraints via robust constraints using suitable uncertainty sets.
The resulting robust optimization problem has a known equivalent tractable reformulation.
To compute uncertainty sets that lead to an inner approximation of the stochastic problem, an R-vine copula model is fitted to the distribution of the multi-dimensional power forecast error, i.e., the difference between the forecasted solar power and the measured feed-in at several network nodes.
The uncertainty sets are determined by encompassing a sufficient number of samples drawn from the R-vine copula model.
Furthermore, an enhanced algorithm is proposed to fit R-vine copulas which can be used to draw conditional samples for given solar radiation forecasts.
The experimental results obtained for real-world weather and network data demonstrate the effectiveness of the combination of stochastic programming and model-based prediction of uncertainty via copulas.
We improve the outcomes of previous work by showing that the resulting uncertainty sets are much smaller and lead to less conservative solutions while maintaining the same probabilistic guarantees.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Kevin-Martin Aigner
Peter Schaumann
Freimut von Loeper
Alexander Martin
Volker Schmidt
Frauke Liers
eng
uncontrolled
chance constrained programming
eng
uncontrolled
optimal power flow
eng
uncontrolled
robust optimization
eng
uncontrolled
conditional uncertainty set
eng
uncontrolled
R-vine copula
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B06
B07
B10
https://opus4.kobv.de/opus4-trr154/files/480/robust_dc_opf_copula.pdf
482
2022
eng
15
preprint
1
2022-01-12
--
--
Nonoverlapping Domain Decomposition for Instantaneous Optimal Control of Friction Dominated Flow in a Gas-Network
We consider a non-overlapping domain decomposition method for an optimal control problem related to the flow of gas in a pipe network. The equations of motions are taken to be represented by a friction dominated model derived from a semi-linear approximation of the fully nonlinear isothermal Euler gas equations. This involves a p-Laplace-type problem on the graph with p = 3/2. We continue the work by Leugering and Mophou where such a problem has been discussed in the context of an instantaneous control strategy. We provide a non-overlapping domain decomposition in the spirit of P.L. Lions for elliptic problems and extend the method to the first order optimality system.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Günter Leugering
eng
uncontrolled
Optimal control
eng
uncontrolled
Gas networks
eng
uncontrolled
p-Laplace problem on a graph
eng
uncontrolled
Optimality system
eng
uncontrolled
Domain decomposition
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
https://opus4.kobv.de/opus4-trr154/files/482/Leugering_TRR154_31_01_22.pdf
489
2022
eng
bookpart
1
2022-04-05
--
--
Nonoverlapping Domain Decomposition in Space and Time for Optimal Control Problems on Metric Graphs by the Example of Gas Flow in Pipe Networks
We consider non-overlapping domain decomposition methods for ordinary and partial differential equations and corresponding optimal control problems on metric graphs. As an exemplary context, we chose a semilinear approximation of the Euler system and a doubly nonlinear parabolic model that has come to be known as friction dominated flow in gas pipe networks. By this choice, we encounter hyperbolic, parabolic and elliptic linear and nonlinear problems in a single highly motivating application. We depart from the classical domain decomposition methods described by P.L. Lions and J.L. Lions and O. Pironneau and extend those to problems on metric graphs. The choice of methods is determined by the desire to use a control concept that has come to be known as virtual controls which, in turn, possibly lead to a fully parallel decomposition of the corresponding optimality systems. In a second step, we extend the methods to p-Laplace problems on networks. The analysis, due to space limitations, will appear in a forthcoming publication. See however J.E. Lagnese and G. Leugering. Furthermore, we then describe methods for space and time domain decomposition or optimal control problems in the spirit of J.E. Lagnese and G. Leugering. We finally provide some comments on PINN-based approximations of the methods described before. We provide numerical evidence for all algorithms discussed.
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Günter Leugering
eng
uncontrolled
Optimal control
eng
uncontrolled
PDEs on graphs
eng
uncontrolled
p-Laplace problem on a graph
eng
uncontrolled
p-parabolic problems
eng
uncontrolled
instantaneous control
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
https://opus4.kobv.de/opus4-trr154/files/489/leugering_handbook_survey.pdf
412
2021
eng
32
preprint
1
2021-08-17
2021-08-17
--
Time-Domain Decomposition for Mixed-Integer Optimal Control Problems
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.
under review
publish
2
Creative Commons - CC BY - Namensnennung 4.0 International
Falk Hante
Richard Krug
Martin Schmidt
eng
uncontrolled
Mixed-integer optimal control problems
eng
uncontrolled
Time-domain decomposition
eng
uncontrolled
Mixed-integer nonlinear optimization
eng
uncontrolled
Convergence
Friedrich-Alexander-Universität Erlangen-Nürnberg
Humboldt-Universität zu Berlin
A03
A05
B08
Universität Trier
C08
https://opus4.kobv.de/opus4-trr154/files/412/miocp-dd_preprint.pdf
302
2019
eng
28
article
1
2019-12-23
2019-12-23
--
Outer Approximation for Global Optimization of Mixed-Integer Quadratic Bilevel Problems
Bilevel optimization problems have received a lot of attention in the last years and decades. Besides numerous theoretical developments there also evolved novel solution algorithms for mixed-integer linear bilevel problems and the most recent algorithms use branch-and-cut techniques from mixed-integer programming that are especially tailored for the bilevel context. In this paper, we consider MIQP-QP bilevel problems, i.e., models with a mixed-integer convex-quadratic upper level and a continuous convex-quadratic lower level. This setting allows for a strong-duality-based transformation of the lower level which yields, in general, an equivalent nonconvex single-level reformulation of the original bilevel problem. Under reasonable assumptions, we can derive both a multi- and a single-tree outer-approximation-based cutting-plane algorithm. We show finite termination and correctness of both methods and present extensive numerical results that illustrate the applicability of the approaches. It turns out that the proposed methods are capable of solving bilevel instances with several thousand variables and constraints and significantly outperform classical solution approaches.
Mathematical Programming (Series B)
2
Creative Commons - CC BY - Namensnennung 4.0 International
Thomas Kleinert
Veronika Grimm
Martin Schmidt
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
Outer approximation
eng
uncontrolled
Quadratic programming
eng
uncontrolled
Convex mixed-integer nonlinear optimization
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/302/miqp-qp-bilevel_preprint.pdf
140
2017
eng
267
294
28
1
70
article
1
2017-04-11
2017-04-11
--
MIP-Based Instantaneous Control of Mixed-Integer PDE-Constrained Gas Transport Problems
We study the transient optimization of gas transport networks including both discrete controls due to switching of controllable elements and nonlinear fluid dynamics described by the system of isothermal Euler equations, which are partial differential equations in time and 1-dimensional space. This combination leads to mixed-integer optimization problems subject to nonlinear hyperbolic partial differential equations on a graph. We propose an instantaneous control approach in which suitable Euler discretizations yield systems of ordinary differential equations on a graph. This networked system of ordinary differential equations is shown to be well-posed and affine-linear solutions of these systems are derived analytically. As a consequence, finite-dimensional mixed-integer linear optimization problems are obtained for every time step that can be solved to global optimality using general-purpose solvers. We illustrate our approach in practice by presenting numerical results on a realistic gas transport network.
Computational Optimization and Applications
10.1007/s10589-017-9970-1
2
Martin Gugat
Günter Leugering
Alexander Martin
Martin Schmidt
Mathias Sirvent
David Wintergerst
eng
uncontrolled
Mixed-integer optimal control
eng
uncontrolled
Instantaneous control
eng
uncontrolled
Partial differential equations on graphs
eng
uncontrolled
Gas networks
eng
uncontrolled
Mixed-integer linear optimization
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
C03
B08
238
2018
2021
eng
100197
33
89(2)
article
1
2018-07-12
2018-07-13
--
Strictly and Γ-Robust Counterparts of Electricity Market Models: Perfect Competition and Nash-Cournot Equilibria
This paper mainly studies two topics: linear complementarity problems for modeling electricity market equilibria and optimization under uncertainty. We consider both perfectly competitive and Nash–Cournot models of electricity markets and study their robustifications using strict robustness and the Γ-approach. For three out of the four combinations of economic competition and robustification, we derive algorithmically tractable convex optimization counterparts that have a clear-cut economic interpretation. In the case of perfect competition, this result corresponds to the two classical welfare theorems, which also apply in both considered robust cases that again yield convex robustified problems. Using the mentioned counterparts, we can also prove the existence and, in some cases, uniqueness of robust equilibria. Surprisingly, it turns out that there is no such economic sensible counterpart for the case of Γ-robustifications of Nash–Cournot models. Thus, an analogue of the welfare theorems does not hold in this case. Finally, we provide a computational case study that illustrates the different effects of the combination of economic competition and uncertainty modeling.
Operations Research Perspectives
2
Creative Commons - CC BY - Namensnennung 4.0 International
Anja Kramer
Vanessa Krebs
Martin Schmidt
eng
uncontrolled
Robust optimization
eng
uncontrolled
Linear complementarity problems
eng
uncontrolled
Electricity market equilibrium models
eng
uncontrolled
Perfect competition
eng
uncontrolled
Nash-Cournot competition
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/238/robust-market-equilibria_preprint.pdf
239
2018
eng
45
article
1
2018-07-26
--
--
Mixed-Integer Programming Techniques for the Connected Max-k-Cut Problem
We consider an extended version of the classical Max-k-Cut problem in which we additionally require that the parts of the graph partition are connected. For this problem we study two alternative mixed-integer linear formulations and review existing as well as develop new branch-and-cut techniques like cuts, branching rules, propagation, primal heuristics, and symmetry breaking. The main focus of this paper is an extensive numerical study in which we analyze the impact of the different techniques for various test sets. It turns out that the techniques from the existing literature are not sufficient to solve an adequate fraction of the test sets. However, our novel techniques significantly outperform the existing ones both in terms of running times and the overall number of instances that can be solved.
Mathematical Programming Computation
Creative Commons - CC BY-SA - Namensnennung - Weitergabe unter gleichen Bedingungen 4.0 International
Christopher Hojny
Imke Joormann
Hendrik Lüthen
Martin Schmidt
eng
uncontrolled
Max-cut
eng
uncontrolled
Connectivity
eng
uncontrolled
Branch-and-cut
eng
uncontrolled
Mixed-integer programming
Friedrich-Alexander-Universität Erlangen-Nürnberg
Technische Universität Darmstadt
A05
B08
https://opus4.kobv.de/opus4-trr154/files/239/gp-conn-sym_preprint.pdf
242
2018
2020
eng
197
218
24
18
article
1
2018-09-26
2018-10-03
--
Structural Properties of Feasible Bookings in the European Entry-Exit Gas Market System
In this work we analyze the structural properties of the set of feasible bookings in the European entry-exit gas market system. We present formal definitions of feasible bookings and then analyze properties that are important if one wants to optimize over them. Thus, we study whether the sets of feasible nominations and bookings are bounded, convex, connected, conic, and star-shaped. The results depend on the specific model of gas flow in a network. Here, we discuss a simple linear flow model with arc capacities as well as nonlinear and mixed-integer nonlinear models of passive and active networks, respectively. It turns out that the set of feasible bookings has some unintuitive properties. For instance, we show that the set is nonconvex even though only a simple linear flow model is used.
4OR
10.1007/s10288-019-00411-3
2
Published
Creative Commons - CC BY - Namensnennung 4.0 International
Lars Schewe
Martin Schmidt
Johannes Thürauf
eng
uncontrolled
Gas networks
eng
uncontrolled
Booking
eng
uncontrolled
Entry-exit system
eng
uncontrolled
Convexity
eng
uncontrolled
Flow models
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
B08
Universität Trier
University of Edinburgh
https://opus4.kobv.de/opus4-trr154/files/242/struct-prop-feas-bookings_preprint.pdf
243
2018
2020
eng
47
92
article
1
2018-10-18
2018-10-19
--
Endogenous Price Zones and Investment Incentives in Electricity Markets: An Application of Multilevel Optimization with Graph Partitioning
In the course of the energy transition, load and supply centers are growing apart in electricity markets worldwide, rendering regional price signals even more important to provide adequate locational investment incentives. This paper focuses on electricity markets that operate under a zonal pricing market design. For a fixed number of zones, we endogenously derive the optimal configuration of price zones and available transfer capacities on a network in order to optimally govern investment and production decisions in the long run. In a multilevel mixed-integer nonlinear model that contains a graph partitioning problem on the first level, we determine welfare-maximizing price zones and available transfer capacities for a given electricity market and analyze their impact on market outcomes. Using a generalized Benders decomposition approach developed in Grimm et al. (2019) and a problem-tailored scenario clustering for reducing the input data size, we are able to solve the model to global optimality even for large instances. We apply the approach to the German electricity market as an example to examine the impact of optimal zoning on key performance indicators such as welfare, generation mix and locations, or electricity prices. It turns out that even for a small number of price zones, an optimal configuration of zones induces a welfare level that almost approaches the first best.
Energy Economics
2
Creative Commons - CC BY - Namensnennung 4.0 International
Mirjam Ambrosius
Veronika Grimm
Thomas Kleinert
Frauke Liers
Martin Schmidt
Gregor Zöttl
eng
uncontrolled
Electricity Markets
eng
uncontrolled
Price Zones
eng
uncontrolled
Investment Incentives
eng
uncontrolled
Multilevel Optimization
eng
uncontrolled
Graph Partitioning
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B06
B08
https://opus4.kobv.de/opus4-trr154/files/243/price-zones-econ-focus-preprint.pdf
244
2018
eng
16
article
1
2018-12-05
2018-12-06
--
Convergence of Finite-Dimensional Approximations for Mixed-Integer Optimization with Differential Equations
We consider a direct approach to solve mixed-integer nonlinear optimization problems with constraints depending on initial and terminal conditions of an ordinary differential equation. In order to obtain a finite-dimensional problem, the dynamics are approximated using discretization methods. In the framework of general one-step methods, we provide sufficient conditions for the convergence of this approach in the sense of the corresponding optimal values. The results are obtained by considering the discretized problem as a parametric mixed-integer nonlinear optimization problem in finite dimensions, where the maximum step size for discretizing the dynamics is the parameter. In this setting, we prove the continuity of the optimal value function under a stability assumption for the integer feasible set and second-order conditions from nonlinear optimization. We address the necessity of the conditions on the example of pipe sizing problems for gas networks.
Control and Cybernetics
2
Creative Commons - CC BY - Namensnennung 4.0 International
Falk M. Hante
Martin Schmidt
eng
uncontrolled
Optimization with differential equations
eng
uncontrolled
Optimal value function
eng
uncontrolled
Lipschitz continuity
eng
uncontrolled
Parametric optimization
eng
uncontrolled
Mixed-integer nonlinear programming
Friedrich-Alexander-Universität Erlangen-Nürnberg
A03
A05
B08
https://opus4.kobv.de/opus4-trr154/files/244/ode-minlp-discr-conv_preprint.pdf
245
2018
2020
eng
305
334
30
21(1)
article
1
2018-12-06
2018-12-06
--
Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results
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.
Optimization and Engineering
2
Creative Commons - CC BY - Namensnennung 4.0 International
Martine Labbé
Fränk Plein
Martin Schmidt
eng
uncontrolled
Gas networks
eng
uncontrolled
Booking
eng
uncontrolled
Nomination
eng
uncontrolled
Computational complexity
eng
uncontrolled
Trees
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
Z01
B08
https://opus4.kobv.de/opus4-trr154/files/245/PreprintVersion-2019-06-05.pdf
255
2019
2020
eng
article
1
2019-03-07
2019-03-08
--
Γ-Robust Linear Complementarity Problems
Complementarity problems are often used to compute equilibria made up of specifically coordinated solutions of different optimization problems. Specific examples are game-theoretic settings like the bimatrix game or energy market models like for electricity or natural gas. While optimization under uncertainties is rather well-developed, the field of equilibrium models represented by complementarity problems under uncertainty - especially using the concepts of robust optimization - is still in its infancy. In this paper, we extend the theory of strictly robust linear complementarity problems (LCPs) to Γ-robust settings, where existence of worst-case-hedged equilibria cannot be guaranteed. Thus, we study the minimization of the worst-case gap function of Γ-robust counterparts of LCPs. For box and l1-norm uncertainty sets we derive tractable convex counterparts for monotone LCPs and study their feasibility as well as the existence and uniqueness of solutions. To this end, we consider uncertainties in the vector and in the matrix defining the LCP. We additionally study so-called ρ-robust solutions, i.e., solutions of relaxed uncertain LCPs. Finally, we illustrate the Γ-robust concept applied to LCPs in the light of the above mentioned classical examples of bimatrix games and market equilibrium modeling.
Optimization Methods and Software
2
Creative Commons - CC BY - Namensnennung 4.0 International
Vanessa Krebs
Martin Schmidt
eng
uncontrolled
Linear complementarity problems
eng
uncontrolled
Robust optimization
eng
uncontrolled
Optimization under uncertainty
eng
uncontrolled
Γ-robustness
eng
uncontrolled
Tractable counterparts
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/255/gamma-robust-lcp-preprint.pdf
283
2019
2021
eng
783
819
37
22(2)
article
1
2019-10-04
2019-10-04
--
Nonlinear Optimization of District Heating Networks
We develop a complementarity-constrained nonlinear optimization model for the time-dependent control of district heating networks. The main physical aspects of water and heat flow in these networks are governed by nonlinear and hyperbolic 1d partial differential equations. In addition, a pooling-type mixing model is required at the nodes of the network to treat the mixing of different water temperatures. This mixing model can be recast using suitable complementarity constraints. The resulting problem is a mathematical program with complementarity constraints subject to nonlinear partial differential equations describing the physics. In order to obtain a tractable problem, we apply suitable discretizations in space and time, resulting in a finite-dimensional optimization problem with complementarity constraints for which we develop a suitable reformulation with improved constraint regularity. Moreover, we propose an instantaneous control approach for the discretized problem, discuss practically relevant penalty formulations, and present preprocessing techniques that are used to simplify the mixing model at the nodes of the network. Finally, we use all these techniques to solve realistic instances. Our numerical results show the applicability of our techniques in practice.
Optimization and Engineering
2
Creative Commons - CC BY - Namensnennung 4.0 International
Richard Krug
Volker Mehrmann
Martin Schmidt
eng
uncontrolled
District heating networks
eng
uncontrolled
Nonlinear optimization
eng
uncontrolled
Euler equations
eng
uncontrolled
Differential-algebraic equations
eng
uncontrolled
Complementarity constraints
Friedrich-Alexander-Universität Erlangen-Nürnberg
Technische Universität Berlin
A05
B03
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/283/dhn-nl-opt_preprint.pdf
284
2019
2022
eng
417
441
25
29(1)
preprint
1
2019-10-10
2019-10-10
--
Γ-Robust Linear Complementarity Problems with Ellipsoidal Uncertainty Sets
We study uncertain linear complementarity problems (LCPs), i.e., problems in which the LCP vector q or the LCP matrix M may contain uncertain parameters. To this end, we use the concept of Γ-robust optimization applied to the gap function formulation of the LCP. Thus, this work builds upon [16]. There, we studied Γ-robustified LCPs for l1- and box-uncertainty sets, whereas we now focus on ellipsoidal uncertainty set. For uncertainty in q or M, we derive conditions for the tractability of the robust counterparts. For these counterparts, we also give conditions for the existence and uniqueness of their solutions. Finally, a case study for the uncertain traffic equilibrium problem is considered, which illustrates the effects of the values of Γ on the feasibility and quality of the respective robustified solutions.
International Transactions in Operational Research
2
Creative Commons - CC BY - Namensnennung 4.0 International
Vanessa Krebs
Michael Müller
Martin Schmidt
eng
uncontrolled
Robust optimization
eng
uncontrolled
Linear complementarity problems
eng
uncontrolled
Ellipsoidal uncertainty sets
eng
uncontrolled
Traffic equilibrium problems
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/284/gamma-robust-lcps-w-ellipsoids_preprint.pdf
285
2019
eng
8
preprint
1
2019-11-08
2019-11-08
--
Capacity Evaluation for Large-Scale Gas Networks
Natural gas is important for the energy turnaround in many countries like in Germany, where it serves as a "bridging energy" towards a fossil-free energy supply in the future. About 20% of the total German energy demand is provided by natural gas, which is transported through a complex pipeline network with a total length of about 30000 km and the efficient use of the given transport infrastructure for natural gas is of political, economic, and societal importance.
As a consequence of the liberalization of the European gas market in the last decades, gas trading and transport have been decoupled. This has led to new challenges for gas transport companies, and mathematical optimization is perfectly suited for tackling many of these challenges. However, the underlying mathematical problems are by far too hard to be solved by today's general-purpose software so that novel mathematical theory and algorithms are needed. The industrial research project "ForNe: Research Cooperation Network Optimization" has been initiated and funded by Open Grid Europe in 2009 and brought together experts in mathematical optimization from seven German universities and research institutes, which cover almost the entire range of mathematical optimization: integer and nonlinear optimization as well as optimization under uncertainty.
The mathematical research results have been put together in a software package that has been delivered to Open Grid Europe at the end of the project. Moreover, the research is still continuing - e.g., in the Collaborative Research Center/Transregio 154 "Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks" funded by the German Research Foundation.
under review
2
Creative Commons - CC BY - Namensnennung 4.0 International
Martin Schmidt
Benjamin Hiller
Thorsten Koch
Marc Pfetsch
Björn Geißler
René Henrion
Imke Joormann
Alexander Martin
Antonio Morsi
Werner Römisch
Lars Schewe
Rüdiger Schultz
Marc C. Steinbach
Friedrich-Alexander-Universität Erlangen-Nürnberg
Technische Universität Darmstadt
Humboldt-Universität zu Berlin
Zuse-Institut Berlin (ZIB)
Weierstraß-Institut für Angewandte Analysis und Stochastik
Universität Duisburg-Essen
A01
A05
A07
B04
B05
B07
B08
Universität Trier
University of Edinburgh
https://opus4.kobv.de/opus4-trr154/files/285/forne-komso.pdf
286
2019
2021
eng
128
152
25
2
78
article
1
2019-11-12
2019-11-12
--
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.
Networks
10.1007/s00186-021-00752-y
Published
2
Creative Commons - CC BY - Namensnennung 4.0 International
Martine Labbé
Fränk Plein
Martin Schmidt
Johannes Thürauf
eng
uncontrolled
Gas networks
eng
uncontrolled
European entry-exit market
eng
uncontrolled
Bookings
eng
uncontrolled
Potential-based flows
eng
uncontrolled
Computational complexity
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
Z01
B08
Universität Trier
Université libre de Bruxelles
https://opus4.kobv.de/opus4-trr154/files/286/preprint-version-2020-11-20.pdf
289
2019
eng
35
article
1
2019-12-03
2019-12-03
--
The Impact of Neighboring Markets on Renewable Locations, Transmission Expansion, and Generation Investment
Many long-term investment planning models for liberalized electricity markets either optimize for the entire electricity system or focus on confined jurisdictions, abstracting from adjacent markets. In this paper, we provide models for analyzing the impact of the interdependencies between a core electricity market and its neighboring markets on key long-run decisions. This we do both for zonal and nodal pricing schemes. The identification of welfare optimal investments in transmission lines and renewable capacity within a core electricity market requires a spatially restricted objective function, which also accounts for benefits from cross-border electricity trading. This leads to mixed-integer nonlinear multilevel optimization problems with bilinear nonconvexities for which we adapt a Benders-like decomposition approach from the literature. In a case study, we use a stylized six-node network to disentangle different effects of optimal regional (as compared to supra-regional) investment planning. Regional planning alters investment in transmission and renewable capacity in the core region, which affects private investment in generation capacity also in adjacent regions and increases welfare in the core region at the cost of system welfare. Depending on the congestion-pricing scheme, the regulator of the core region follows different strategies to increase welfare causing distributional effects among stakeholders.
European Journal of Operational Research
2
Creative Commons - CC BY - Namensnennung 4.0 International
Jonas Egerer
Veronika Grimm
Thomas Kleinert
Martin Schmidt
Gregor Zöttl
eng
uncontrolled
Neighboring Markets
eng
uncontrolled
Renewables
eng
uncontrolled
Network Expansion
eng
uncontrolled
Multilevel Optimization
eng
uncontrolled
Benders Decomposition
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B08
Universität Trier
B09
https://opus4.kobv.de/opus4-trr154/files/289/ee-and-net-design_preprint.pdf
303
2020
eng
36
preprint
0
2020-02-12
2020-02-12
--
Solving Mixed-Integer Nonlinear Optimization Problems using Simultaneous Convexification - a Case Study for Gas Networks
Solving mixed-integer nonlinear optimization problems (MINLPs) to global optimality is extremely challenging. An important step for enabling their solution consists in the design of convex relaxations of the feasible set. Known solution approaches based on spatial branch-and-bound become more effective the tighter the used relaxations are. Relaxations are commonly established by convex underestimators, where each constraint function is considered separately. Instead, a considerably tighter relaxation can be found via so-called simultaneous convexification, where convex underestimators are derived for more than one constraint function at a time. In this work, we present a global solution approach for solving mixed-integer nonlinear problems that uses simultaneous convexification. We introduce a separation method that relies on determining the convex envelope of linear combinations of the constraint functions and on solving a nonsmooth convex problem. In particular, we apply the method to quadratic absolute value functions and derive their convex envelopes. The practicality of the proposed solution approach is demonstrated on several test instances from gas network optimization, where the method outperforms standard approaches that use separate convex relaxations.
2
Creative Commons - CC BY-NC - Namensnennung - Nicht kommerziell 4.0 International
Frauke Liers
Alexander Martin
Maximilian Merkert
Nick Mertens
Dennis Michaels
eng
uncontrolled
Mixed-Integer Nonlinear Programming
eng
uncontrolled
Simultaneous Convexification
eng
uncontrolled
Convex Envelope
eng
uncontrolled
Gas Network Optimization
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B06
B07
Z01
https://opus4.kobv.de/opus4-trr154/files/303/SolMINLPsusingSimConv.pdf
304
2020
2020
eng
337
362
26
295
article
1
2020-01-21
2020-01-21
--
Computing Technical Capacities in the European Entry-Exit Gas Market is NP-Hard
As a result of its liberalization, the European gas market is organized as an entry-exit system in order to decouple the trading and transport of natural gas. Roughly summarized, the gas market organization consists of four subsequent stages. First, the transmission system operator (TSO) is obliged to allocate so-called maximal technical capacities for the nodes of the network. Second, the TSO and the gas traders sign mid- to long-term capacity-right contracts, where the capacity is bounded above by the allocated technical capacities. These contracts are called bookings. Third, on a day-ahead basis, gas traders can nominate the amount of gas that they inject or withdraw from the network at entry and exit nodes, where the nominated amount is bounded above by the respective booking. Fourth and finally, the TSO has to operate the network such that the nominated amounts of gas can be transported. By signing the booking contract, the TSO guarantees that all possibly resulting nominations can indeed be transported. Consequently, maximal technical capacities have to satisfy that all nominations that comply with these technical capacities can be transported through the network. This leads to a highly challenging mathematical optimization problem. We consider the specific instantiations of this problem in which we assume capacitated linear as well as potential-based flow models. In this contribution, we formally introduce the problem of Computing Technical Capacities (CTC) and prove that it is NP-complete on trees and NP-hard in general. To this end, we first reduce the Subset Sum problem to CTC for the case of capacitated linear flows in trees. Afterward, we extend this result to CTC with potential-based flows and show that this problem is also NP-complete on trees by reducing it to the case of capacitated linear flow. Since the hardness results are obtained for the easiest case, i.e., on tree-shaped networks with capacitated linear as well as potential-based flows, this implies the hardness of CTC for more general graph classes.
Annals of Operations Research
10.1007/s10479-020-03725-2
2
Published
Creative Commons - CC BY - Namensnennung 4.0 International
Lars Schewe
Martin Schmidt
Johannes Thürauf
eng
uncontrolled
European Entry-Exit Gas Market
eng
uncontrolled
Technical Capacities
eng
uncontrolled
Potential-Based Flows
eng
uncontrolled
Computational Complexity
eng
uncontrolled
NP-Hardness
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
B08
Universität Trier
University of Edinburgh
https://opus4.kobv.de/opus4-trr154/files/304/technical-capacities-tree.pdf
305
0202
2021
eng
20
article
1
2020-01-27
2020-01-27
--
Γ-Robust Electricity Market Equilibrium Models with Transmission and Generation Investments
We consider uncertain robust electricity market equilibrium problems including transmission and generation investments. Electricity market equilibrium modeling has a long tradition but is, in most of the cases, applied in a deterministic setting in which all data of the model are known. Whereas there exist some literature on stochastic equilibrium problems, the field of robust equilibrium models is still in its infancy. We contribute to this new field of research by considering Γ-robust electricity market equilibrium models on lossless DC networks with transmission and generation investments. We state the nominal market equilibrium problem as a mixed complementarity problem as well as its variational inequality and welfare optimization counterparts. For the latter, we then derive a Γ-robust formulation and show that it is indeed the counterpart of a market equilibrium problem with robustified player problems. Finally, we present two case studies to gain insights into the general effects of robustification on electricity market models. In particular, our case studies reveal that the transmission system operator tends to act more risk-neutral in the robust setting, whereas generating firms clearly behave more risk-averse.
Energy Systems
2
Creative Commons - CC BY - Namensnennung 4.0 International
Emre Çelebi
Vanessa Krebs
Martin Schmidt
eng
uncontrolled
Robust optimization
eng
uncontrolled
Robust market equilibria
eng
uncontrolled
Electricity market equilibrium models
eng
uncontrolled
Transmission and generation investment
eng
uncontrolled
Perfect competition
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/305/main.pdf
308
2020
eng
24
article
1
2020-02-16
2020-02-16
--
Solving Binary-Constrained Mixed Complementarity Problems Using Continuous Reformulations
Mixed complementarity problems are of great importance in practice since they appear in various fields of applications like energy markets, optimal stopping, or traffic equilibrium problems. However, they are also very challenging due to their inherent, nonconvex structure. In addition, recent applications require the incorporation of integrality constraints. Since complementarity problems often model some kind of equilibrium, these recent applications ask for equilibrium points that additionally satisfy certain integer conditions. Obviously, this makes the problem even harder to solve. The solution approach used most frequently in the literature is to recast the complementarity conditions as disjunctive constraints using additional binary variables and big-M constraints. However, both latter aspects create issues regarding the tractability and correctness of the reformulation. In this paper, we follow the opposite route and restate the integrality conditions as complementarity constraints, leading to purely continuous reformulations that can be tackled by local solvers. We study these reformulations theoretically and provide a numerical study that shows that continuous reformulations are useful in practice both in terms of solution times and solution quality.
Computers & Operations Research
2
Creative Commons - CC BY - Namensnennung 4.0 International
Steven A. Gabriel
Marina Leal
Martin Schmidt
eng
uncontrolled
Binary-constrained mixed complementarity problems
eng
uncontrolled
Mixed-integer optimization
eng
uncontrolled
Continuous reformulations
eng
uncontrolled
Spatial price equilibrium problems
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/308/dc-mcp-cont-reform.pdf
310
2020
eng
22
article
1
2020-04-16
2020-04-16
--
Mixed-Integer Nonlinear Optimization for District Heating Network Expansion
We present a mixed-integer nonlinear optimization model for computing the optimal expansion of an existing tree-shaped district heating network given a number of potential new consumers. To this end, we state a stationary and nonlinear model of all hydraulic and thermal effects in the pipeline network as well as nonlinear models for consumers and the network's depot. For the former, we consider the Euler momentum and the thermal energy equation. The thermal aspects are especially challenging. Here, we develop a novel polynomial approximation that we use in the optimization model. The expansion decisions are modeled by binary variables for which we derive additional valid inequalities that greatly help to solve the highly challenging problem. Finally, we present a case study in which we identify three major aspects that strongly influence investment decisions: the estimated average power demand of potentially new consumers, the distance between the existing network and the new consumers, and thermal losses in the network.
at - Automatisierungstechnik
2
Creative Commons - CC BY - Namensnennung 4.0 International
Marius Roland
Martin Schmidt
eng
uncontrolled
District heating networks
eng
uncontrolled
Network expansion
eng
uncontrolled
Mixed-integer nonlinear optimization
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/310/dhn-expansion_preprint.pdf
312
2021
eng
preprint
1
2020-05-12
2020-05-12
--
Robust Approximation of Chance Constrained DC Optimal Power Flow under Decision-Dependent Uncertainty
We propose a mathematical optimization model and its solution for joint chance constrained DC Optimal Power Flow. In this application, it is particularly important that there is a high probability of transmission limits being satisfied, even in the case of uncertain or fluctuating feed-in from renewable energy sources. In critical network situations where the network risks overload, renewable energy feed-in has to be curtailed by the transmission system operator (TSO). The TSO can reduce the feed-in in discrete steps at each network node. The proposed optimization model minimizes curtailment while ensuring that there is a high probability of transmission limits being maintained. The latter is modeled via (joint) chance constraints that are computationally challenging. Thus, we propose a solution approach based on the robust safe approximation of these constraints. Hereby, probabilistic constraints are replaced by robust constraints with suitably defined uncertainty sets constructed from historical data. The uncertainty sets are calculated by encompassing randomly drawn scenarios using the scenario approach proposed by Margellos et al. (IEEE Transactions on Automatic Control, 59 (2014)). The ability to discretely control the power feed-in then leads to a robust optimization problem with decision-dependent uncertainties, i.e. the uncertainty sets depend on decision variables. We propose an equivalent mixed-integer linear reformulation for box uncertainties with the exact linearization of bilinear terms. Finally, we present numerical results for different test cases from the Nesta archive, as well as for a real network. We consider the discrete curtailment of solar feed-in, for which we use real-world weather and network data. The experimental tests demonstrate the effectiveness of this method and run times are very fast. Moreover, on average the calculated robust solutions lead only to a small increase in curtailment, when compared to nominal solutions.
2
Creative Commons - CC BY - Namensnennung 4.0 International
Kevin-Martin Aigner
Jan-Patrick Clarner
Frauke Liers
Alexander Martin
eng
uncontrolled
OR in energy
eng
uncontrolled
optimal power flow
eng
uncontrolled
chance constrained programming
eng
uncontrolled
robust optimization
eng
uncontrolled
decision-dependent uncertainty
Friedrich-Alexander-Universität Erlangen-Nürnberg
Zuse-Institut Berlin (ZIB)
A05
B06
B07
Z01
https://opus4.kobv.de/opus4-trr154/files/312/robust_cc_dc_opf.pdf
221
2019
2017
eng
543
573
Optimization and Engineering
20
article
0
2017-11-21
--
--
Maximizing the storage capacity of gas networks: a global MINLP approach
In this paper, we study the transient optimization of gas networks, focusing in particular on maximizing the storage capacity of the network. We include nonlinear gas physics and active elements such as valves and compressors, which due to their switching lead to discrete decisions. The former is described by a model derived from the Euler equations that is given by a coupled system of nonlinear parabolic partial differential equations (PDEs). We tackle the resulting mathematical optimization problem by a first-discretize-then-optimize approach. To this end, we introduce a new discretization of the underlying system of parabolic PDEs and prove well-posedness for the resulting nonlinear discretized system. Endowed with this discretization, we model the problem of maximizing the storage capacity as a non-convex mixed-integer nonlinear problem (MINLP). For the numerical solution of the MINLP, we algorithmically extend a well-known relaxation approach that has already been used very successfully in the field of stationary gas network optimization. This method allows us to solve the problem to global optimality by iteratively solving a series of mixed-integer problems (MIPs). Finally, we present two case studies that illustrate the applicability of our approach.
10.1007/s11081-018-9414-5
Robert Burlacu
Herbert Egger
Martin Groß
Alexander Martin
Marc Pfetsch
Lars Schewe
Mathias Sirvent
Martin Skutella
eng
uncontrolled
Mixed-Integer Nonlinear Programming
eng
uncontrolled
Transient Gas Transport Optimization
eng
uncontrolled
Storage Capacity Maximization
eng
uncontrolled
Power-to-Gas
eng
uncontrolled
First-Discretize-Then-Optimize
Friedrich-Alexander-Universität Erlangen-Nürnberg
Technische Universität Darmstadt
Technische Universität Berlin
A05
A07
B07
C04
University of Waterloo
https://opus4.kobv.de/opus4-trr154/files/221/max_storage_capacity-opus.pdf
256
2019
eng
198
215
33 (1)
article
1
2019-03-11
2019-03-14
--
Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method
Bilevel problems are highly challenging optimization problems that appear in many applications of energy market design, critical infrastructure defense, transportation, pricing, etc. Often, these bilevel models are equipped with integer decisions, which makes the problems even harder to solve. Typically, in such a setting in mathematical optimization one develops primal heuristics in order to obtain feasible points of good quality quickly or to enhance the search process of exact global methods. However, there are comparably few heuristics for bilevel problems. In this paper, we develop such a primal heuristic for bilevel problems with mixed-integer linear or quadratic upper level and linear or quadratic lower level. The heuristic is based on a penalty alternating direction method, which allows for a theoretical analysis. We derive a convergence theory stating that the method converges to a stationary point of an equivalent single-level reformulation of the bilevel problem and extensively test the method on a test set of more than 2800 instances - which is one of the largest computational test sets ever used in bilevel programming. The study illustrates the very good performance of the proposed method, both in terms of running times and solution quality. This renders the method a suitable sub-routine in global bilevel solvers as well as a reasonable standalone approach.
INFORMS Journal on Computing
10.1287/ijoc.2019.0945
2
Creative Commons - CC BY - Namensnennung 4.0 International
Thomas Kleinert
Martin Schmidt
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
Mixed-integer bilevel optimization
eng
uncontrolled
Stationary points
eng
uncontrolled
Penalty methods
eng
uncontrolled
Alternating direction methods
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/256/bilevel-padm-heuristic_preprint.pdf
257
2019
2020
eng
114
article
1
2019-03-11
2019-03-14
--
On Electricity Market Equilibria with Storage: Modeling, Uniqueness, and a Distributed ADMM
We consider spot-market trading of electricity including storage operators as additional agents besides producers and consumers. Storages allow for shifting produced electricity from one time period to a later one. Due to this, multiple market equilibria may occur even if classical uniqueness assumptions for the case without storages are satisfied. For models containing storage operators, we derive sufficient conditions that ensure uniqueness of generation and demand. We also prove uniqueness of the market equilibrium for the special case of a single storage operator. Nevertheless, in case of multiple storage operators, uniqueness fails to hold in general, which we show by illustrative examples. We conclude the theoretical discussion with a general ex-post condition for proving the uniqueness of a given solution. In contrast to classical settings without storages, the computation of market equilibria is much more challenging since storage operations couple all trading events over time. For this reason, we propose a tailored parallel and distributed alternating direction method of multipliers (ADMM) for efficiently computing spot-market equilibria over long time horizons. We first analyze the parallel performance of the method itself. Finally, we show that the parallel ADMM clearly outperforms solving the respective problems directly and that it is capable of solving instances with more than 42 million variables in less than 13 minutes.
Computers & Operations Research
10.1016/j.cor.2019.104783
2
Published
Creative Commons - CC BY-NC-SA - Namensnennung - Nicht kommerziell - Weitergabe unter gleichen Bedingungen 4.0 International
Julia Grübel
Thomas Kleinert
Vanessa Krebs
Galina Orlinskaya
Lars Schewe
Martin Schmidt
Johannes Thürauf
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/257/elec-markets-w-storage_preprint.pdf
258
2019
eng
225
232
8
48(3)
preprint
1
2019-03-12
2019-03-14
--
A Decomposition Heuristic for Mixed-Integer Supply Chain Problems
Mixed-integer supply chain models typically are very large but are also very sparse and can be decomposed into loosely coupled blocks. In this paper, we use general-purpose techniques to obtain a block decomposition of supply chain instances and apply a tailored penalty alternating direction method, which exploits the structural properties of the decomposed instances. We further describe problem-specific enhancements of the algorithm and present numerical results on real-world instances that illustrate the applicability of the approach.
Operations Research Letters
2
Creative Commons - CC BY - Namensnennung 4.0 International
Lars Schewe
Martin Schmidt
Dieter Weninger
eng
uncontrolled
Supply chain
eng
uncontrolled
Mixed-integer optimization
eng
uncontrolled
Decomposition
eng
uncontrolled
Penalty method
eng
uncontrolled
Alternating direction methods
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/258/padm-snp_preprint.pdf
264
2019
2020
eng
1716
1721
6
68(6)
preprint
1
2019-04-23
2019-04-23
--
There's No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization
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.
Operations Research
2
Creative Commons - CC BY - Namensnennung 4.0 International
Thomas Kleinert
Martine Labbé
Fränk Plein
Martin Schmidt
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
Mathematical programs with complementarity constraints (MPCC)
eng
uncontrolled
Bounding polyhedra
eng
uncontrolled
Big-M
eng
uncontrolled
Hardness
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
Z01
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/264/bilevel-lp-lp-bigm-hardness_preprint.pdf
273
2019
2020
eng
29
article
1
2019-07-03
2019-07-03
--
Portfolio Optimization with Irreversible Long-Term Investments in Renewable Energy under Policy Risk: A Mixed-Integer Multistage Stochastic Model and a Moving-Horizon Approach
Portfolio optimization is an ongoing hot topic of mathematical optimization and management science. Due to the current financial market environment with low interest rates and volatile stock markets, it is getting more and more important to extend portfolio optimization models by other types of investments than classical assets. In this paper, we present a mixed-integer multistage stochastic model that includes investment opportunities in irreversible and long-term infrastructure projects in the context of renewable energies, which are also subject to policy risk. On realistic time scales for investment problems of this type, the resulting instances are by far too large to be solved with today's most evolved optimization software. Thus, we present a tailored moving-horizon approach together with suitable approximations and simplifications of the model. We evaluate these approximations and simplifications in a computational sensitivity analysis and derive a final model that can be tackled on a realistic instance by our moving-horizon approach.
European Journal of Operational Research
2
Creative Commons - CC BY - Namensnennung 4.0 International
Nadine Gatzert
Alexander Martin
Martin Schmidt
Benjamin Seith
Nikolai Vogl
eng
uncontrolled
Mixed-integer optimization
eng
uncontrolled
Multistage stochastic optimization
eng
uncontrolled
Portfolio optimization
eng
uncontrolled
Illiquid investments
eng
uncontrolled
Policy risk
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/273/main.pdf
274
2019
2020
eng
33
114
article
1
2019-07-18
2019-07-18
--
Optimal Design of Retailer-Prosumer Electricity Tariffs Using Bilevel Optimization
We compare various flexible tariffs that have been proposed to cost-effectively govern a prosumer's electricity management - in particular time-of-use (TOU), critical-peak-pricing (CPP), and a real-time-pricing tariff (RTP). As the outside option, we consider a fixed-price tariff (FP) that restricts the specific characteristics of TOU, CPP, and RTP, so that the flexible tariffs are at least as profitable for the prosumer as the fixed-price tariff. We propose bilevel models to determine the optimal interplay between the retailer's tariff design and the prosumer's decisions on using the storage, on consumption, and on electricity purchases from as well as electricity sales to the grid. The single-level reformulations of the considered bilevel models are computationally highly challenging optimization problems since they, e.g., combine bilinearities and mixed-integer aspects for modeling certain tariff structures. Based on a computational study using real-world data, we find that RTP increases retailer profits, however, leads to the largest price volatility for the prosumer. TOU and CPP only yield mild additional retailer profits and, due to the multiplicity of optimal plans on the part of the prosumer, imply uncertain revenues for the retailer.
Computers & Operations Research
2
Creative Commons - CC BY - Namensnennung 4.0 International
Veronika Grimm
Galina Orlinskaya
Lars Schewe
Martin Schmidt
Gregor Zöttl
eng
uncontrolled
Electricity tariffs
eng
uncontrolled
Pricing
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
Mixed-integer optimization
eng
uncontrolled
Tariff design
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B07
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/274/bilevel-tariff-opt_preprint.pdf
275
2019
eng
17
article
1
2019-09-10
2019-09-10
--
Port-Hamiltonian modeling of district heating networks
This paper provides a first contribution to port-Hamiltonian modeling of district heating networks. By introducing a model hierarchy of flow equations on the network, this work aims at a thermodynamically consistent port-Hamiltonian embedding of the partial differential-algebraic systems. We show that a spatially discretized network model describing the advection of the internal energy density with respect to an underlying incompressible stationary Euler-type hydrodynamics can be considered as a parameter-dependent finite-dimensional port-Hamiltonian system. Moreover, we present an infinite-dimensional port-Hamiltonian formulation for a compressible instationary thermodynamic fluid flow in a pipe. Based on these first promising results, we raise open questions and point out research perspectives concerning structure-preserving discretization, model reduction, and optimization.
Progress in Differential Algebraic Equations II (edited by Reis T., Grundel S., and Schöps S). Differential-Algebraic Equations Forum
2
Creative Commons - CC BY - Namensnennung 4.0 International
Sarah-Alexa Hauschild
Nicole Marheineke
Volker Mehrmann
Jan Mohring
Arbi Moses Badlyan
Markus Rein
Martin Schmidt
eng
uncontrolled
Partial differential equations on networks
eng
uncontrolled
Port-Hamiltonian model framework
eng
uncontrolled
Energy-based formulation
eng
uncontrolled
District heating network
eng
uncontrolled
Thermodynamic fluid flow
Technische Universität Berlin
A05
B03
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/275/mso-dhn.pdf
235
2018
eng
16
article
1
2018-04-26
2018-04-26
--
The Cost of Not Knowing Enough: Mixed-Integer Optimization with Implicit Lipschitz Nonlinearities
It is folklore knowledge that nonconvex mixed-integer nonlinear optimization problems can be notoriously hard to solve in practice. In this paper we go one step further and drop analytical properties that are usually taken for granted in mixed-integer nonlinear optimization. First, we only assume Lipschitz continuity of the nonlinear functions and additionally consider multivariate implicit constraint functions that cannot be solved for any parameter analytically. For this class of mixed-integer problems we propose a novel algorithm based on an approximation of the feasible set in the domain of the nonlinear function---in contrast to an approximation of the graph of the function considered in prior work. This method is shown to compute approximate global optimal solutions in finite time and we also provide a worst-case iteration bound. In some first numerical experiments we show that the ``cost of not knowing enough'' is rather high by comparing our approach with the open-source global solver SCIP. This reveals that a lot of work is still to be done for this highly challenging class of problems and we thus finally propose some possible directions of future research.
Optimization Letters
accepted
2
Martin Schmidt
Mathias Sirvent
Winnifried Wollner
eng
uncontrolled
Mixed-Integer Nonlinear Optimization, Global Optimization, Lipschitz Optimization, Gas Networks
Friedrich-Alexander-Universität Erlangen-Nürnberg
Technische Universität Darmstadt
A05
B08
A08
https://opus4.kobv.de/opus4-trr154/files/235/global-mi-opt-implicit-lipschitz_preprint.pdf
458
eng
preprint
0
2021-11-10
--
--
A PDE-Constrained Generalized Nash Equilibrium Approach for Modeling Gas Markets with Transport
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.
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Veronika Grimm
Michael Hintermüller
Olivier Huber
Lars Schewe
Martin Schmidt
Gregor Zöttl
A05
B02
B07
B08
B09
https://opus4.kobv.de/opus4-trr154/files/458/gas-gnep-w-pdes_preprint.pdf
505
2023
eng
8
preprint
1
2023-01-19
--
--
Gas Transport Network Optimization: Mixed-Integer Nonlinear Models
Although modern societies strive towards energy systems that are entirely based on renewable energy carriers, natural gas is still one of the most important energy sources. This became even more obvious in Europe with Russia's 2022 war against the Ukraine and the resulting stop of gas supplies from Russia. Besides that it is very important to use this scarce resource efficiently. To this end, it is also of significant relevance that its transport is organized in the most efficient, i.e., cost- or energy-efficient, way. The corresponding mathematical optimization models have gained a lot of attention in the last decades in different optimization communities. These models are highly nonlinear mixed-integer problems that are constrained by algebraic constraints and partial differential equations (PDEs), which usually leads to models that are not tractable. Hence, simplifications have to be made and in this chapter, we present a commonly accepted finite-dimensional stationary model, i.e., a model in which the steady-state solutions of the PDEs are approximated with algebraic constraints. For more details about the involved PDEs and the treatment of transient descriptions we refer to Hante and Schmidt (2023). The presented finite-dimensional as well as mixed-integer nonlinear and nonconvex model is still highly challenging if it needs to be solved for real-world gas transport networks. Hence, we also review some classic solution approaches from the literature.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Falk M. Hante
Martin Schmidt
eng
uncontrolled
Gas networks
eng
uncontrolled
Mixed-integer nonlinear optimization
eng
uncontrolled
Mixed-integer linear optimization
eng
uncontrolled
Nonlinear optimization
Humboldt-Universität zu Berlin
A03
A05
B08
Universität Trier
C07
https://opus4.kobv.de/opus4-trr154/files/505/eoo-gtno-mip-models-preprint.pdf
525
2023
eng
doctoralthesis
1
2023-10-03
--
2023-05-22
Decomposition Methods for Time-Dependent Mixed-Integer Nonlinear Optimization Problems on Graphs
Decomposition can be the method of choice to deal with optimization problems that contain hard to solve model structures or that are of large scale. The main idea is to decompose the problematic aspects of the problem into multiple smaller blocks that can be solved more easily. Here, the challenge is to combine the single pieces to a solution that is not only feasible but maybe even optimal for the original problem. In many cases, this can be done by introducing an iteration that eventually converges to a desired solution.
In this cumulative dissertation, we present several iterative decomposition methods that are tailored to different types of optimization models and use distinct approaches to split up the problems. Our main motivation for this originates from the optimization of gas transport networks, where we encounter partial differential equations as well as discrete control decisions. Additionally, we engage in the related field of district heating network optimization to study the challenges arising from large-scale and fully discretized systems as well as undesirable model features such as, e.g., complementarity constraints. Here, we introduce two temperature mixing models that are well suited for optimization and a number of techniques to speed up the solution process, which are applied in numerical experiments.
As a next step, we develop an iterative time-domain decomposition method that is applied to optimal control problems subject to semilinear hyperbolic systems of partial differential equations. For this, we derive first-order optimality conditions that are then split using a non-overlapping decomposition of the time horizon. We exploit the fact that the resulting systems have a primal interpretation as so-called virtual control problems. We prove the convergence of the iterative method and develop a posteriori error estimates. Later, we extend the scheme to systems of ordinary differential equations with mixed- integer controls by using Pontryagin’s maximum principle. We again show the convergence and conduct a numerical case study.
Moreover, we use a consensus-based version of the classic penalty alternating direction method to solve tailored reformulations of transient gas network problems that allow us to minimize the number of coupling constraints between sub-problems. Here, we utilize the quasi-separable structure of the network to decompose it into sub-networks with more desirable properties. We also discuss different decomposition strategies and test them in a numerical case study. Finally, we present a successive linear relaxation method for mixed-integer nonlinear problems with multivariate Lipschitz continuous nonlinearities. The distinguishing feature of this algorithm is that it exploits no properties of the nonlinearities besides the Lipschitz constants. Therefore, the method is
applicable for problems with non-convex or even non-differentiable constraints. The nonlinearities do not even need to be given in a closed form, which allows us to integrate black-box constraints into the model. We prove that the algorithm converges to an approximate global optimum and we provide a worst-case estimate for the number of iterations. The iterative method is applied to stationary gas transport problems, where implicitly given solutions of the differential equations are modeled via black-box constraints.
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Richard Krug
A05
Friedrich-Alexander-Universität Erlangen-Nürnberg
https://opus4.kobv.de/opus4-trr154/files/525/DissertationRichardKrug.pdf
392
2021
eng
104
lecture
1
2021-06-15
2021-06-15
--
A Gentle and Incomplete Introduction to Bilevel Optimization
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.
under review
publish
2
Creative Commons - CC BY - Namensnennung 4.0 International
Yasmine Beck
Martin Schmidt
eng
uncontrolled
Bilevel Optimization
eng
uncontrolled
Lecture Notes
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/392/bilevel-optimization.pdf
467
2021
eng
35
preprint
1
2021-11-09
--
--
Exact and Heuristic Solution Techniques for Mixed-Integer Quantile Minimization Problems
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.
under review
publish
Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International
Diego Cattaruzza
Martine Labbé
Matteo Petris
Marius Roland
Martin Schmidt
eng
uncontrolled
Quantile Minimization
eng
uncontrolled
Value-at-Risk (VaR)
eng
uncontrolled
Mixed-Integer Optimization
eng
uncontrolled
Valid Inequalities
eng
uncontrolled
Adaptive Clustering
A05
B08
Universität Trier
Université libre de Bruxelles
https://opus4.kobv.de/opus4-trr154/files/467/roadef-challenge_preprint.pdf
502
2022
eng
28
preprint
1
2022-10-19
--
--
An Exact Method for Nonlinear Network Flow Interdiction Problems
We study network flow interdiction problems with nonlinear and nonconvex flow models. The resulting model is a max-min bilevel optimization problem in which the follower's problem is nonlinear and nonconvex. In this game, the leader attacks a limited number of arcs with the goal to maximize the load shed and the follower aims at minimizing the load shed by solving a transport problem in the interdicted network. We develop an exact algorithm consisting of lower and upper bounding schemes that computes an optimal interdiction under the assumption that the interdicted network remains weakly connected. The main challenge consists of computing valid upper bounds for the maximal load shed, whereas lower bounds can directly be derived from the follower's problem. To compute an upper bound, we propose solving a specific bilevel problem, which is derived from restricting the flexibility of the follower when adjusting the load flow. This bilevel problem still has a nonlinear and nonconvex follower's problem, for which we then prove necessary and sufficient optimality conditions. Consequently, we obtain equivalent single-level reformulations of the specific bilevel model to compute upper bounds. Our numerical results show the applicability of this exact approach using the example of gas networks.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Martin Schmidt
Johannes Thürauf
eng
uncontrolled
Interdiction Games
eng
uncontrolled
Bilevel Optimization
eng
uncontrolled
Potential-Based Flows
eng
uncontrolled
Mixed-Integer Nonlinear Optimization
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/502/potential-based-interdiction-games-r1.pdf
503
2022
eng
26
preprint
1
2022-10-24
--
--
A Consensus-Based Alternating Direction Method for Mixed-Integer and PDE-Constrained Gas Transport Problems
We consider dynamic gas transport optimization problems, which lead to large-scale and nonconvex mixed-integer nonlinear optimization problems (MINLPs) on graphs. Usually, the resulting instances are too challenging to be solved by state-of-the-art MINLP solvers. In this paper, we use graph decompositions to obtain multiple optimization problems on smaller blocks, which can be solved in parallel and which may result in simpler classes of optimization problems since not every block necessarily contains mixed-integer or nonlinear aspects. For achieving feasibility at the interfaces of the several blocks, we employ a tailored consensus-based penalty alternating direction method. Our numerical results show that such decomposition techniques can outperform the baseline approach of just solving the overall MINLP from scratch. However, a complete answer to the question of how to decompose MINLPs on graphs in dependence of the given model is still an open topic for future research.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Richard Krug
Günter Leugering
Alexander Martin
Martin Schmidt
Dieter Weninger
eng
uncontrolled
Gas transport networks
eng
uncontrolled
Mixed-integer nonlinear optimization
eng
uncontrolled
Alternating direction methods
eng
uncontrolled
Graph decomposition
eng
uncontrolled
Penalty methods
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/503/gas-network_opti-padm_preprint.pdf
499
2022
eng
preprint
1
2022-09-02
--
--
On a Frank-Wolfe Approach for Abs-smooth Functions
We propose an algorithm which appears to be the first bridge between the fields of conditional gradient methods and abs-smooth optimization. Our nonsmooth nonconvex problem setting is motivated by machine learning, since the broad class of abs-smooth functions includes, for instance, the squared $\ell_2$-error of a neural network with ReLU or hinge Loss activation. To overcome the nonsmoothness in our problem, we propose a generalization to the traditional Frank-Wolfe gap and prove that first-order minimality is achieved when it vanishes. We derive a convergence rate for our algorithm which is identical to the smooth case. Although our algorithm necessitates the solution of a subproblem which is more challenging than the smooth case, we provide an efficient numerical method for its partial solution, and we identify several applications where our approach fully solves the subproblem. Numerical and theoretical convergence is demonstrated, yielding several conjectures.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Timo Kreimeier
Sebastian Pokutta
Andrea Walther
Zev Woodstock
eng
uncontrolled
Frank-Wolfe algorithm
eng
uncontrolled
Active Signature Method
eng
uncontrolled
abs-smooth functions
eng
uncontrolled
nonsmooth optimization
eng
uncontrolled
convergence rate
Humboldt-Universität zu Berlin
Zuse-Institut Berlin (ZIB)
Technische Universität Berlin
A05
B10
https://opus4.kobv.de/opus4-trr154/files/499/abssmooth-fw.pdf
498
2022
eng
34
preprint
1
2022-08-12
--
--
A Successive Linear Relaxation Method for MINLPs with Multivariate Lipschitz Continuous Nonlinearities
We present a novel method for mixed-integer optimization problems with multivariate and Lipschitz continuous nonlinearities. In particular, we do not assume that the nonlinear constraints are explicitly given but that we can only evaluate them and that we know their global Lipschitz constants. The algorithm is a successive linear relaxation method in which we alternate between solving a master problem, which is a mixed-integer linear relaxation of the original problem, and a subproblem, which is designed to tighten the linear relaxation of the next master problem by using the Lipschitz information about the respective functions. By doing so, we follow the ideas of Schmidt et al. (2018, 2021) and improve the tackling of multivariate constraints. Although multivariate nonlinearities obviously increase modeling capabilities, their incorporation also significantly increases the computational burden of the proposed algorithm. We prove the correctness of our method and also derive a worst-case iteration bound. Finally, we show the generality of the addressed problem class and the proposed method by illustrating that both bilevel optimization problems with nonconvex and quadratic lower levels as well as nonlinear and mixed-integer models of gas transport can be tackled by our method. We provide the necessary theory for both applications and briefly illustrate the outcomes of the new method when applied to these two problems.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Julia Grübel
Richard Krug
Martin Schmidt
Winnifried Wollner
eng
uncontrolled
Mixed-Integer Nonlinear Optimization
eng
uncontrolled
Global Optimization
eng
uncontrolled
Lipschitz Optimization
eng
uncontrolled
Bilevel Optimization
eng
uncontrolled
Gas Networks
Friedrich-Alexander-Universität Erlangen-Nürnberg
A05
B08
Universität Hamburg
Universität Trier
C08
https://opus4.kobv.de/opus4-trr154/files/498/multidim-lipschitz-minlp-preprint.pdf
504
2023
eng
8
preprint
1
2023-01-19
--
--
Gas Transport Network Optimization: PDE-Constrained Models
The optimal control of gas transport networks was and still is a very important topic for modern economies and societies. Accordingly, a lot of research has been carried out on this topic during the last years and decades. Besides mixed-integer aspects in gas transport network optimization, one of the main challenges is that a physically and technically detailed modeling of transient gas dynamics leads to theoretically and computationally highly demanding models involving nonlinear partial differential equations (PDEs). For further background on the application, historical notes and a detailed discussion of mixed-integer aspects for stationary descriptions we refer to Hante and Schmidt (2023). In this chapter, we focus on the most common modeling approaches concerning transient descriptions, point out the challenges, and summarize important contributions concerning the optimization of the most relevant control parameters for this particular class of problems.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Falk M. Hante
Martin Schmidt
eng
uncontrolled
Gas networks
eng
uncontrolled
Partial differential equations
eng
uncontrolled
Optimal control
eng
uncontrolled
PDE-constrained optimization
eng
uncontrolled
Modeling
Humboldt-Universität zu Berlin
A03
A05
B08
Universität Trier
C07
https://opus4.kobv.de/opus4-trr154/files/504/eoo-gtno-pde-models-preprint.pdf
471
2021
eng
39
preprint
1
2021-11-10
--
--
Exact Methods for Discrete Γ-Robust Interdiction Problems with an Application to the Bilevel Knapsack Problem
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.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Yasmine Beck
Ivana Ljubic
Martin Schmidt
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
Robust optimization
eng
uncontrolled
Knapsack interdiction
eng
uncontrolled
Mixed-integer programming
eng
uncontrolled
Branch-and-Cut
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/471/gamma-robust-bilevel-preprint.pdf
483
2022
eng
29
preprint
1
2022-01-27
--
--
Adaptive Nonlinear Optimization of District Heating Networks Based on Model and Discretization Catalogs
We propose an adaptive optimization algorithm for operating district heating networks in a stationary regime. The behavior of hot water flow in the pipe network is modeled using the incompressible Euler equations and a suitably chosen energy equation. By applying different simplifications to these equations, we derive a catalog of models. Our algorithm is based on this catalog and adaptively controls where in the network which model is used. Moreover, the granularity of the applied discretization is controlled in a similar adaptive manner. By doing so, we are able to obtain optimal solutions at low computational costs that satisfy a prescribed tolerance w.r.t. the most accurate modeling level. To adaptively control the switching between different levels and the adaptation of the discretization grids, we derive error measure formulas and a posteriori error measure estimators. Under reasonable assumptions we prove that the adaptive algorithm terminates after finitely many iterations. Our numerical results show that the algorithm is able to produce solutions for problem instances that have not been solvable before.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Dänschel Hannes
Mehrmann Volker
Marius Roland
Martin Schmidt
eng
uncontrolled
District heating networks
eng
uncontrolled
Adaptive methods
eng
uncontrolled
Nonlinear optimization
Technische Universität Berlin
A05
B03
Z01
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/483/dhn-adaptive.pdf
484
2022
eng
16
preprint
1
2022-02-02
--
--
On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level
It is well known that bilevel optimization problems are hard to solve both in theory and practice. In this paper, we highlight a further computational difficulty when it comes to solving bilevel problems with continuous but nonconvex lower levels. Even if the lower-level problem is solved to ɛ-feasibility regarding its nonlinear constraints for an arbitrarily small but positive ɛ, the obtained bilevel solution as well as its objective value may be arbitrarily far away from the actual bilevel solution and its actual objective value. This result even holds for bilevel problems for which the nonconvex lower level is uniquely solvable, for which the strict complementarity condition holds, for which the feasible set is convex, and for which Slater's constraint qualification is satisfied for all feasible upper-level decisions. Since the consideration of ɛ-feasibility cannot be avoided when solving nonconvex problems to global optimality, our result shows that computational bilevel optimization with continuous and nonconvex lower levels needs to be done with great care. Finally, we illustrate that the nonlinearities in the lower level are the key reason for the observed bad behavior by showing that linear bilevel problems behave much better at least on the level of feasible solutions.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Yasmine Beck
Martin Schmidt
Johannes Thürauf
Daniel Bienstock
eng
uncontrolled
Bilevel optimization
eng
uncontrolled
Nonconvex lower levels
eng
uncontrolled
Approximate feasibility
eng
uncontrolled
Global optimization
A05
B08
Universität Trier
https://opus4.kobv.de/opus4-trr154/files/484/nearly-feasible-bilevel-preprint.pdf
518
eng
preprint
1
2023-05-11
--
--
Norm-induced Cuts: Optimization with Lipschitzian Black-box Functions
Optimal control problems usually involve constraints which model physical states and their possible transitions. These are represented by ordinary or partial differential equations (ODEs/PDEs) which add a component of infinite dimension to the problem. In recent literature, one method to simulate such ODEs/PDEs are physics-informed neural networks. Typically, neural networks are highly non-linear which makes their addition to optimization problems challenging. Hence, we leverage their often available Lipschitz property on a compact domain. The respective Lipschitz constants have to be computed only once and are accessible thereafter.
We present a method that, based on this property, iteratively adds cuts involving the violation of the constraints by the current incumbent and the Lipschitz constant. Hereby, the “shape” of a cut depends on the norm used. We prove the correctness of the method by showing that it either returns an optimal solution when terminating or creates a sequence with optimal accumulation points. This is complemented by a discussion about the termination in the infeasible case, as well as an analysis of the problem complexity. For the analysis, we show that the lower and upper iteration bound asymptotically coincide when the relative approximation error goes to zero. In the end, we visualize the method on a small example based on a two-dimensional non-convex optimization problem, as well as stress the necessity of having a globally optimal oracle for the sub-problems by another example.
under review
publish
Creative Commons - CC BY - Namensnennung 4.0 International
Adrian Göß
Alexander Martin
Sebastian Pokutta
Kartikey Sharma
eng
uncontrolled
Global Optimization
eng
uncontrolled
Lipschitz Optimization
eng
uncontrolled
Black-box Optimization
eng
uncontrolled
Derivative-free Optimization
Friedrich-Alexander-Universität Erlangen-Nürnberg
Zuse-Institut Berlin (ZIB)
A05
Technische Universität Nürnberg
https://opus4.kobv.de/opus4-trr154/files/518/nic_preprint.pdf