TY - INPR A1 - Groß, Martin A1 - Gupta, Anupam A1 - Kumar, Amit A1 - Matuschke, Jannik A1 - Schmidt, Daniel R. A1 - Schmidt, Melanie A1 - Verschae, José T1 - A Local-Search Algorithm for Steiner Forest N2 - In the Steiner Forest problem, we are given a graph and a collection of source-sink pairs, and the goal is to find a subgraph of minimum total length such that all pairs are connected. The problem is APX-Hard and can be 2 -approximated by, e.g., the elegant primal-dual algorithm of Agrawal, Klein, and Ravi from 1995. We give a local-search-based constant-factor approximati on for the problem. Local search brings in new techniques to an area that has for long not seen any improv ements and might be a step towards a combinatorial algorithm for the more general survivable n etwork design problem. Moreover, local search was an essential tool to tackle the dynamic MST/Stein er Tree problem, whereas dynamic Steiner Forest is still wide open. It is easy to see that any constant factor local search algori thm requires steps that add/drop many edges together. We propose natural local moves which, at each step , either (a) add a shortest path in the current graph and then drop a bunch of inessential edges, or (b) add a s et of edges to the current solution. This second type of moves is motivated by the potential function w e use to measure progress, combining the cost of the solution with a penalty for each connected compon ent. Our carefully-chosen local moves and potential function work in tandem to eliminate bad local min ima that arise when using more traditional local moves. Our analysis first considers the case where the local optimum is a single tree, and shows optimality w.r.t. moves that add a single edge (and drop a set of edges) is enough to bound the locality gap. For the general case, we show how to “project” the optimal solution o nto the different trees of the local optimum without incurring too much cost (and this argument uses opti mality w.r.t. both kinds of moves), followed by a tree-by-tree argument. We hope both the potential funct ion, and our analysis techniques will be useful to develop and analyze local-search algorithms in ot her contexts. Y1 - 2017 ER - TY - JOUR A1 - Groß, Martin A1 - Marc E., Pfetsch A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Skutella, Martin T1 - Algorithmic Results for Potential-Based Flows: Easy and Hard Cases N2 - Potential-based flows are an extension of classical network flows in which the flow on an arc is determined by the difference of the potentials of its incident nodes. Such flows are unique and arise, for example, in energy networks. Two important algorithmic problems are to determine whether there exists a feasible flow and to maximize the flow between two designated nodes. We show that these problems can be solved for the single source and sink case by reducing the network to a single arc. However, if we additionally consider switches that allow to force the flow to 0 and decouple the potentials, these problems are NP-hard. Nevertheless, for particular series-parallel networks, one can use algorithms for the subset sum problem. Moreover, applying network presolving based on generalized series-parallel structures allows to significantly reduce the size of realistic energy networks. KW - Potential networks KW - Potential-based flows KW - Maximum flow problem KW - Series-parallel graphs KW - Network reduction Y1 - 2017 U6 - https://doi.org/10.1002/net.21865 VL - 73 IS - 3 SP - 303 EP - 324 ET - Networks ER - TY - JOUR A1 - Grimm, Veronika A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Weibelzahl, Martin A1 - Zöttl, Gregor T1 - Transmission and generation investment in electricity markets: The effects of market splitting and network fee regimes JF - European Journal of Operational Research N2 - 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. KW - Electricity market modeling KW - Mixed-integer nonlinear optimization KW - Multilevel programming KW - Network expansion KW - Transmission management Y1 - 2016 U6 - https://doi.org/10.1016/j.ejor.2016.03.044 VL - 254 IS - 2 SP - 493 EP - 509 ER - TY - JOUR A1 - Gugat, Martin A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Sirvent, Mathias A1 - Wintergerst, David T1 - Towards Simulation Based Mixed-Integer Optimization with Differential Equations JF - Networks N2 - 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. KW - Mixed-Integer Optimization KW - Simulation Based Optimization KW - Optimization with Differential Equations KW - Decomposition Method KW - Gas Transport Networks Y1 - 2018 U6 - https://doi.org/10.1002/net.21812 ER - TY - JOUR A1 - Gugat, Martin A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Sirvent, Mathias A1 - Wintergerst, David T1 - MIP-Based Instantaneous Control of Mixed-Integer PDE-Constrained Gas Transport Problems JF - Computational Optimization and Applications N2 - 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. KW - Mixed-integer optimal control KW - Instantaneous control KW - Partial differential equations on graphs KW - Gas networks KW - Mixed-integer linear optimization Y1 - 2017 U6 - https://doi.org/10.1007/s10589-017-9970-1 VL - 70 IS - 1 SP - 267 EP - 294 ER - TY - JOUR A1 - Krug, Richard A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems with Mixed Two-Point Boundary Conditions JF - Control and Cybernetics N2 - In this article, we continue our work (Krug et al., 2021) on time-domain decomposition of optimal control problems for systems of semilinear hyperbolic equations in that we now consider mixed two-point boundary value problems and provide an in-depth well-posedness analysis. The more general boundary conditions significantly enlarge the scope of applications, e.g., to hyperbolic problems on metric graphs with cycles. We design an iterative method based on the optimality systems that can be interpreted as a decomposition method for the original optimal control problem into virtual control problems on smaller time domains. KW - Time-domain decomposition KW - Optimal control KW - Semilinear hyperbolic systems KW - Convergence Y1 - 2021 ER - TY - JOUR A1 - Krug, Richard A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems JF - SIAM Journal on Control and Optimization N2 - 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. KW - Time-domain decomposition KW - Optimal control KW - Semilinear hyperbolic systems KW - Convergence KW - A posteriori error estimates Y1 - 2020 ER - TY - JOUR A1 - Hante, Falk A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Challenges in optimal control problems for gas and fluid flow in networks of pipes and canals: From modeling to industrial applications N2 - 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. KW - Networks KW - pipes KW - optimal control KW - Euler and St. Venant equations KW - hierarchy of models Y1 - 2016 ER - TY - JOUR A1 - Domschke, Pia A1 - Groß, Martin A1 - Hiller, Benjamin A1 - Hante, Falk A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Mathematische Modellierung, Simulation und Optimierung von Gastransportnetzwerken JF - gwf-gas/erdgas Y1 - 2015 VL - 11 SP - 880 EP - 885 ER - TY - JOUR A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Sirvent, Mathias T1 - Nonoverlapping Domain Decomposition for Optimal Control Problems governed by Semilinear Models for Gas Flow in Networks N2 - 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. KW - Optimal control, Gas networks, Euler's equation, Semilinear PDE, Nonoverlapping domain decomposition Y1 - 2017 VL - 46 IS - 3 SP - 191 EP - 225 PB - Control and Cybernetics ER - TY - JOUR A1 - Reuß, Markus A1 - Welder, Lara A1 - Thürauf, Johannes A1 - Linßen, Jochen A1 - Grube, Thomas A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Stolten, Detlef A1 - Robinius, Martin T1 - Modeling Hydrogen Networks for Future Energy Systems: A Comparison of Linear and Nonlinear Approaches JF - International Journal of Hydrogen Energy N2 - 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. Y1 - 2019 U6 - https://doi.org/10.1016/j.ijhydene.2019.10.080 ER - TY - INPR A1 - Aigner, Kevin-Martin A1 - Schaumann, Peter A1 - von Loeper, Freimut A1 - Martin, Alexander A1 - Schmidt, Volker A1 - Liers, Frauke T1 - Robust DC Optimal Power Flow with Modeling of Solar Power Supply Uncertainty via R-Vine Copulas N2 - 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. KW - chance constrained programming KW - optimal power flow KW - robust optimization KW - conditional uncertainty set KW - R-vine copula Y1 - ER - TY - INPR A1 - Schmidt, Martin A1 - Hiller, Benjamin A1 - Koch, Thorsten A1 - Pfetsch, Marc A1 - Geißler, Björn A1 - Henrion, René A1 - Joormann, Imke A1 - Martin, Alexander A1 - Morsi, Antonio A1 - Römisch, Werner A1 - Schewe, Lars A1 - Schultz, Rüdiger A1 - Steinbach, Marc C. T1 - Capacity Evaluation for Large-Scale Gas Networks N2 - 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. Y1 - 2019 ER - TY - JOUR A1 - Gatzert, Nadine A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Seith, Benjamin A1 - Vogl, Nikolai T1 - Portfolio Optimization with Irreversible Long-Term Investments in Renewable Energy under Policy Risk: A Mixed-Integer Multistage Stochastic Model and a Moving-Horizon Approach JF - European Journal of Operational Research N2 - 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. KW - Mixed-integer optimization KW - Multistage stochastic optimization KW - Portfolio optimization KW - Illiquid investments KW - Policy risk Y1 - 2019 ER - TY - JOUR A1 - Robinius, Martin A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Stolten, Detlef A1 - Thürauf, Johannes A1 - Welder, Lara T1 - Robust Optimal Discrete Arc Sizing for Tree-Shaped Potential Networks JF - Computational Optimization and Applications N2 - We consider the problem of discrete arc sizing for tree-shaped potential networks with respect to infinitely many demand scenarios. This means that the arc sizes need to be feasible for an infinite set of scenarios. The problem can be seen as a strictly robust counterpart of a single-scenario network design problem, which is shown to be NP-complete even on trees. In order to obtain a tractable problem, we introduce a method for generating a finite scenario set such that optimality of a sizing for this finite set implies the sizing's optimality for the originally given infinite set of scenarios. We further prove that the size of the finite scenario set is quadratically bounded above in the number of nodes of the underlying tree and that it can be computed in polynomial time. The resulting problem can then be solved as a standard mixed-integer linear optimization problem. Finally, we show the applicability of our theoretical results by computing globally optimal arc sizes for a realistic hydrogen transport network of Eastern Germany. KW - Discrete arc sizing KW - Mixed-integer linear optimization KW - Potential networks KW - Scenario generation KW - Robust optimization Y1 - 2018 U6 - https://doi.org/10.1007/s10589-019-00085-x IS - 73(3) SP - 791 EP - 819 ER - TY - INPR A1 - Krug, Richard A1 - Leugering, Günter A1 - Martin, Alexander A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - A Consensus-Based Alternating Direction Method for Mixed-Integer and PDE-Constrained Gas Transport Problems N2 - 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. KW - Gas transport networks KW - Mixed-integer nonlinear optimization KW - Alternating direction methods KW - Graph decomposition KW - Penalty methods Y1 - 2022 ER - TY - INPR A1 - Grübel, Julia A1 - Huber, Olivier A1 - Hümbs, Lukas A1 - Klimm, Max A1 - Schmidt, Martin A1 - Schwartz, Alexandra T1 - Nonconvex Equilibrium Models for Energy Markets: Exploiting Price Information to Determine the Existence of an Equilibrium N2 - Motivated by examples from the energy sector, we consider market equilibrium problems (MEPs) involving players with nonconvex strategy spaces or objective functions, where the latter are assumed to be linear in market prices. We propose an algorithm that determines if an equilibrium of such an MEP exists and that computes an equilibrium in case of existence. Three key prerequisites have to be met. First, appropriate bounds on market prices have to be derived from necessary optimality conditions of some players. Second, a technical assumption is required for those prices that are not uniquely determined by the derived bounds. Third, nonconvex optimization problems have to be solved to global optimality. We test the algorithm on well-known instances from the power and gas literature that meet these three prerequisites. There, nonconvexities arise from considering the transmission system operator as an additional player besides producers and consumers who, e.g., switches lines or faces nonlinear physical laws. Our numerical results indicate that equilibria often exist, especially for the case of continuous nonconvexities in the context of gas market problems. KW - Energy markets KW - Nonconvex games KW - Existence KW - Equilibrium computation KW - Perfect competition Y1 - 2021 ER - TY - INPR A1 - De Santis, Marianna A1 - de Vries, Sven A1 - Schmidt, Martin A1 - Winkel, Lukas T1 - A Penalty Branch-and-Bound Method for Mixed-Binary Linear Complementarity Problems N2 - Linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations but also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, almost no tailored algorithms are known besides reformulations of the problem that allow to apply general-purpose mixed-integer linear programming solvers. In this paper, we present, theoretically analyze, enhance, and test a novel branch-and-bound method for MILCPs. The main property of this method is that we do not ``branch'' on constraints as usual but by adding suitably chosen penalty terms to the objective function. By doing so, we can either provably compute an MILCP solution if one exists or compute an approximate solution that minimizes an infeasibility measure combining integrality and complementarity conditions. We enhance the method by MILCP-tailored valid inequalities, node selection strategies, branching rules, and warmstarting techniques. The resulting algorithm is shown to clearly outperform two benchmark approaches from the literature. KW - Mixed-Integer Programming KW - Linear Complementarity Problems KW - Mixed-Integer Linear Complementarity Problems KW - Branch-and-Bound KW - Penalty Methods Y1 - 2021 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Manns, Julian A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - Presolving Linear Bilevel Optimization Problems JF - EURO Journal on Computational Optimization N2 - Linear bilevel optimization problems are known to be strongly NP-hard and the computational techniques to solve these problems are often motivated by techniques from single-level mixed-integer optimization. Thus, during the last years and decades many branch-and-bound methods, cutting planes, or heuristics have been proposed. On the other hand, there is almost no literature on presolving linear bilevel problems although presolve is a very important ingredient in state-of-the-art mixed-integer optimization solvers. In this paper, we carry over standard presolve techniques from single-level optimization to bilevel problems and show that this needs to be done with great caution since a naive application of well-known techniques does often not lead to correctly presolved bilevel models. Our numerical study shows that presolve can also be very beneficial for bilevel problems but also highlights that these methods have a more heterogeneous effect on the solution process compared to what is known from single-level optimization. As a side result, our numerical experiments reveal that there is an urgent need for better and more heterogeneous test instance libraries to further propel the field of computational bilevel optimization. KW - Linear Bilevel Optimization KW - Presolve KW - Computational Analysis Y1 - 2021 U6 - https://doi.org/10.1016/j.ejco.2021.100020 IS - 9 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Labbé, Martine A1 - Ljubić, Ivana A1 - Schmidt, Martin T1 - A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization JF - EURO Journal on Computational Optimization N2 - Bilevel optimization is a field of mathematical programming in which some variables are constrained to be the solution of another optimization problem. As a consequence, bilevel optimization is able to model hierarchical decision processes. This is appealing for modeling real-world problems, but it also makes the resulting optimization models hard to solve in theory and practice. The scientific interest in computational bilevel optimization increased a lot over the last decade and is still growing. Independent of whether the bilevel problem itself contains integer variables or not, many state-of-the-art solution approaches for bilevel optimization make use of techniques that originate from mixed-integer programming. These techniques include branch-and-bound methods, cutting planes and, thus, branch-and-cut approaches, or problem-specific decomposition methods. In this survey article, we review bilevel-tailored approaches that exploit these mixed-integer programming techniques to solve bilevel optimization problems. To this end, we first consider bilevel problems with convex or, in particular, linear lower-level problems. The discussed solution methods in this field stem from original works from the 1980's but, on the other hand, are still actively researched today. Second, we review modern algorithmic approaches to solve mixed-integer bilevel problems that contain integrality constraints in the lower level. Moreover, we also briefly discuss the area of mixed-integer nonlinear bilevel problems. Third, we devote some attention to more specific fields such as pricing or interdiction models that genuinely contain bilinear and thus nonconvex aspects. Finally, we sketch a list of open questions from the areas of algorithmic and computational bilevel optimization, which may lead to interesting future research that will further propel this fascinating and active field of research. KW - Bilevel optimization KW - Mixed-integer programming KW - Applications KW - Branch-and-bound KW - Branch-and-cut Y1 - 2021 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Labbé, Martine A1 - Schmidt, Martin A1 - Plein, Fränk T1 - Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality JF - Optimization Letters N2 - Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker (KKT) conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem’s optimality conditions. While in mixed-integer single-level optimization branch-and-cut has proven to be a powerful extension of branch-and-bound, in linear bilevel optimization not too many bilevel-tailored valid inequalities exist. In this paper, we briefly review existing cuts for linear bilevel problems and introduce a new valid inequality that exploits the strong duality condition of the lower level. We further discuss strengthened variants of the inequality that can be derived from McCormick envelopes. In a computational study, we show that the new valid inequalities can help to close the optimality gap very effectively on a large test set of linear bilevel instances. Y1 - 2020 IS - 15 SP - 1027 EP - 1040 ER - TY - JOUR A1 - Böttger, Tom A1 - Grimm, Veronika A1 - Kleinert, Thomas A1 - Schmidt, Martin T1 - The Cost of Decoupling Trade and Transport in the European Entry-Exit Gas Market with Linear Physics Modeling JF - European Journal of Operational Research N2 - 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. KW - Entry-Exit Gas Market KW - Gas Market Design KW - Multilevel Optimization KW - Robust Optimization Y1 - 2020 ER - TY - INPR A1 - Grimm, Veronika A1 - Nowak, Daniel A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schwartz, Alexandra A1 - Zöttl, Gregor T1 - A Tractable Multi-Leader Multi-Follower Peak-Load-Pricing Model with Strategic Interaction N2 - 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. KW - Game theory KW - Nash-Cournot equilibria KW - Multi-leader multi-follower game KW - Peak-load pricing Y1 - 2020 U6 - https://doi.org/10.1007/s10107-021-01708-0 ER - TY - INPR A1 - Biefel, Christian A1 - Liers, Frauke A1 - Rolfes, Jan A1 - Schmidt, Martin T1 - Affinely Adjustable Robust Linear Complementarity Problems N2 - 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. KW - Linear Complementarity Problems KW - Adjustable Robustness KW - Robust Optimization KW - Existence KW - Uniqueness Y1 - 2020 ER - TY - JOUR A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Thürauf, Johannes T1 - Global Optimization for the Multilevel European Gas Market System with Nonlinear Flow Models on Trees JF - Journal of Global Optimization N2 - 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. Y1 - 2020 U6 - https://doi.org/10.1007/s10898-021-01099-8 ER - TY - INPR A1 - Kleinert, Thomas A1 - Schmidt, Martin T1 - Why there is no need to use a big-M in linear bilevel optimization: A computational study of two ready-to-use approaches N2 - 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. KW - Bilevel optimization KW - Big-M KW - SOS-1 KW - Valid inequalities KW - Computational analysis Y1 - 2020 ER - TY - INPR A1 - Gabriel, Steven A. A1 - Leal, Marina A1 - Schmidt, Martin T1 - On Linear Bilevel Optimization Problems with Complementarity-Constrained Lower Levels N2 - 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. KW - Bilevel optimization KW - Linear programs with complementarity constraints KW - Linear complementarity problems KW - Reformulations KW - Spatial price equilibria Y1 - 2020 ER - TY - JOUR A1 - Beck, Yasmine A1 - Schmidt, Martin T1 - A Robust Approach for Modeling Limited Observability in Bilevel Optimization JF - Operations Research Letters N2 - Many applications of bilevel optimization contain a leader facing a follower whose reaction deviates from the one expected by the leader due to some kind of bounded rationality. We consider bilinear bilevel problems with follower's response uncertainty due to limited observability regarding the leader's decision and exploit robust optimization to model the decision making of the follower. We show that the robust counterpart of the lower level allows to tackle the problem via the lower level's KKT conditions. KW - Bilevel optimization KW - Robust optimization KW - Bounded rationality KW - Limited observability KW - Reformulations Y1 - 2021 IS - 49(5) SP - 752 EP - 758 ER - TY - JOUR A1 - Plein, Fränk A1 - Thürauf, Johannes A1 - Labbé, Martine A1 - Schmidt, Martin T1 - A Bilevel Optimization Approach to Decide the Feasibility of Bookings in the European Gas Market JF - Mathematical Methods of Operations Research N2 - The European gas market is organized as a so-called entry-exit system with the main goal to decouple transport and trading. To this end, gas traders and the transmission system operator (TSO) sign so-called booking contracts that grant capacity rights to traders to inject or withdraw gas at certain nodes up to this capacity. On a day-ahead basis, traders then nominate the actual amount of gas within the previously booked capacities. By signing a booking contract, the TSO guarantees that all nominations within the booking bounds can be transported through the network. This results in a highly challenging mathematical problem. Using potential-based flows to model stationary gas physics, feasible bookings on passive networks, i.e., networks without controllable elements, have been characterized in the recent literature. In this paper, we consider networks with linearly modeled active elements such as compressors or control valves. Since these active elements allow the TSO to control the gas flow, the single-level approaches for passive networks from the literature are no longer applicable. We thus present a bilevel model to decide the feasibility of bookings in networks with active elements. While this model is well-defined for general active networks, we focus on the class of networks for which active elements do not lie on cycles. This assumption allows us to reformulate the original bilevel model such that the lower-level problem is linear for every given upper-level decision. Consequently, we derive several single-level reformulations for this case. Besides the classic Karush-Kuhn-Tucker reformulation, we obtain three problem-specific optimal-value-function reformulations. The latter also lead to novel characterizations of feasible bookings in networks with active elements that do not lie on cycles. We compare the performance of our methods by a case study based on data from the GasLib. KW - Gas networks KW - Bilevel optimization KW - European entry-exit market KW - Bookings KW - Active elements Y1 - 2021 U6 - https://doi.org/10.1007/s00186-021-00752-y ER - TY - INPR A1 - Heitsch, Holger A1 - Henrion, René A1 - Kleinert, Thomas A1 - Schmidt, Martin T1 - On Convex Lower-Level Black-Box Constraints in Bilevel Optimization with an Application to Gas Market Models with Chance Constraints N2 - Bilevel optimization is an increasingly important tool to model hierarchical decision making. However, the ability of modeling such settings makes bilevel problems hard to solve in theory and practice. In this paper, we add on the general difficulty of this class of problems by further incorporating convex black-box constraints in the lower level. For this setup, we develop a cutting-plane algorithm that computes approximate bilevel-feasible points. We apply this method to a bilevel model of the European gas market in which we use a joint chance constraint to model uncertain loads. Since the chance constraint is not available in closed form, this fits into the black-box setting studied before. For the applied model, we use further problem-specific insights to derive bounds on the objective value of the bilevel problem. By doing so, we are able to show that we solve the application problem to approximate global optimality. In our numerical case study we are thus able to evaluate the welfare sensitivity in dependence of the achieved safety level of uncertain load coverage. KW - Bilevel optimization KW - Black-box constraints KW - Chance constraints KW - Cutting planes KW - European gas market Y1 - 2021 ER - TY - JOUR A1 - Schmidt, Martin A1 - Sirvent, Mathias A1 - Wollner, Winnifried T1 - A Decomposition Method for MINLPs with Lipschitz Continuous Nonlinearities JF - Mathematical Programming N2 - 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. KW - Mixed-Integer Nonlinear Optimization, Lipschitz Optimization, Inexact Function Evaluations, Decomposition Methods, Gas Networks Y1 - 2017 IS - 178(1) SP - 449 EP - 483 ER - TY - JOUR A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Computing Feasible Points for Binary MINLPs with MPECs JF - Mathematical Programming Computation N2 - Nonconvex mixed-binary nonlinear optimization problems frequently appear in practice and are typically extremely hard to solve. In this paper we discuss a class of primal heuristics that are based on a reformulation of the problem as a mathematical program with equilibrium constraints. We then use different regularization schemes for this class of problems and use an iterative solution procedure for solving series of regularized problems. In the case of success, these procedures result in a feasible solution of the original mixed-binary nonlinear problem. Since we rely on local nonlinear programming solvers the resulting method is fast and we further improve its reliability by additional algorithmic techniques. We show the strength of our method by an extensive computational study on 662 MINLPLib2 instances, where our methods are able to produce feasible solutions for 60% of all instances in at most 10s. KW - Mixed-Integer Nonlinear Optimization KW - MINLP KW - MPEC KW - Complementarity Constraints KW - Primal Heuristic Y1 - 2016 IS - 11(1) SP - 95 EP - 118 ER - TY - JOUR A1 - Schmidt, Martin A1 - Aßmann, Denis A1 - Burlacu, Robert A1 - Humpola, Jesco A1 - Joormann, Imke A1 - Kanelakis, Nikolaos A1 - Koch, Thorsten A1 - Oucherif, Djamal A1 - Pfetsch, Marc E. A1 - Schewe, Lars A1 - Schwarz, Robert A1 - Sirvent, Mathias T1 - GasLib – A Library of Gas Network Instances JF - Data N2 - 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. KW - Gas Transport KW - Networks KW - Problem Instances KW - Mixed-Integer Nonlinear Optimization KW - GasLib Y1 - 2017 U6 - https://doi.org/10.3390/data2040040 VL - 4 IS - 2 ER - TY - JOUR A1 - Hante, Falk A1 - Schmidt, Martin T1 - Complementarity-Based Nonlinear Programming Techniques for Optimal Mixing in Gas Networks JF - EURO Journal on Computational Optimization N2 - We consider nonlinear and nonsmooth mixing aspects in gas transport optimization problems. As mixed-integer reformulations of pooling-type mixing models already render small-size instances computationally intractable, we investigate the applicability of smooth nonlinear programming techniques for equivalent complementarity-based reformulations. Based on recent results for remodeling piecewise affine constraints using an inverse parametric quadratic programming approach, we show that classical stationarity concepts are meaningful for the resulting complementarity-based reformulation of the mixing equations. Further, we investigate in a numerical study the performance of this reformulation compared to a more compact complementarity-based one that does not feature such beneficial regularity properties. All computations are performed on publicly available data of real-world size problem instances from steady-state gas transport. KW - Gas transport networks KW - Mixing KW - Inverse parametric quadratic programming KW - Complementarity constraints KW - MPCC Y1 - 2017 IS - 7(3) SP - 299 EP - 323 ER - TY - JOUR A1 - Krebs, Vanessa A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Uniqueness and Multiplicity of Market Equilibria on DC Power Flow Networks JF - European Journal on Operations Research N2 - We consider uniqueness and multiplicity of market equilibria in a short-run setup where traded quantities of electricity are transported through a capacitated network in which power flows have to satisfy the classical lossless DC approximation. The firms face fluctuating demand and decide on their production, which is constrained by given capacities. Today, uniqueness of such market outcomes are especially important in more complicated multilevel models for measuring market (in)efficiency. Thus, our findings are important prerequisites for such studies. We show that market equilibria are unique on tree networks under mild assumptions and we also present a priori conditions under which equilibria are unique on cycle networks. On general networks, uniqueness fails to hold and we present simple examples for which multiple equilibria exist. However, we prove a posteriori criteria for the uniqueness of a given solution and characterize situations in which multiple solutions exist. KW - Market Equilibria KW - Uniqueness KW - Multiplicity KW - Networks KW - DC Power Flow Y1 - 2017 IS - 271(1) SP - 165 EP - 178 ER - TY - JOUR A1 - Geißler, Björn A1 - Morsi, Antonio A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Solving Highly Detailed Gas Transport MINLPs: Block Separability and Penalty Alternating Direction Methods JF - INFORMS Journal on Computing N2 - Detailed modeling of gas transport problems leads to nonlinear and nonconvex mixed-integer optimization or feasibility models (MINLPs) because both the incorporation of discrete controls of the network as well as accurate physical and technical modeling is required in order to achieve practical solutions. Hence, ignoring certain parts of the physics model is not valid for practice. In the present contribution we extend an approach based on linear relaxations of the underlying nonlinearities by tailored model reformulation techniques yielding block-separable MINLPs. This combination of techniques allows us to apply a penalty alternating direction method and thus to solve highly detailed MINLPs for large-scale real-world instances. The practical strength of the proposed method is demonstrated by a computational study in which we apply the method to instances from steady-state gas transport including both pooling effects with respect to the mixing of gases of different composition and a highly detailed compressor station model. Y1 - 2016 IS - 30(2) SP - 309 EP - 323 ER - TY - JOUR A1 - Geißler, Björn A1 - Morsi, Antonio A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps JF - SIAM Journal on Optimization N2 - Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only few works considering their theoretical properties. We show that feasibility pumps can be seen as alternating direction methods applied to special reformulations of the original problem, inheriting the convergence theory of these methods. Moreover, we propose a novel penalty framework that encompasses this alternating direction method, which allows us to refrain from random perturbations that are applied in standard versions of feasibility pumps in case of failure. We present a convergence theory for the new penalty based alternating direction method and compare the new variant of the feasibility pump with existing versions in an extensive numerical study for mixed-integer linear and nonlinear problems. Y1 - 2017 U6 - https://doi.org/10.1137/16M1069687 VL - 27 IS - 3 SP - 1611 EP - 1636 ER - TY - JOUR A1 - Grimm, Veronika A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - Uniqueness of Market Equilibrium on a Network: A Peak-Load Pricing Approach JF - European Journal of Operational Research N2 - In this paper we analyze peak-load pricing in the presence of network constraints. In our setup, firms facing fluctuating demand decide on the size and location of production facilities. They make production decisions constrained by the invested capacities, taking into account that market prices reflect scarce transmission capacities. We state general conditions for existence and uniqueness of the market equilibrium and provide a characterization of equilibrium investment and production. The presented analysis covers the cases of perfect competition and monopoly - the case of strategic firms is approximated by a conjectural variations approach. Our result is a prerequisite for analyzing regulatory policy options with computational multilevel equilibrium models, since uniqueness of the equilibrium at lower levels is of key importance when solving these models. Thus, our paper contributes to an evolving strand of literature that analyzes regulatory policy based on computational multilevel equilibrium models and aims at taking into account individual objectives of various agents, among them not only generators and customers but also, e.g., the regulator deciding on network expansion. KW - Pricing KW - Peak-Load Pricing KW - Networks KW - Uniqueness Y1 - 2017 U6 - https://doi.org/10.1016/j.ejor.2017.03.036 VL - 261 IS - 3 SP - 971 EP - 983 ER - TY - JOUR A1 - Geißler, Björn A1 - Morsi, Antonio A1 - Schewe, Lars A1 - Schmidt, Martin T1 - Solving Power-Constrained Gas Transportation Problems using an MIP-based Alternating Direction Method JF - Computers & Chemical Engineering N2 - We present a solution algorithm for problems from steady-state gas transport optimization. Due to nonlinear and nonconvex physics and engineering models as well as discrete controllability of active network devices, these problems lead to difficult nonconvex mixed-integer nonlinear optimization models. The proposed method is based on mixed-integer linear techniques using piecewise linear relaxations of the nonlinearities and a tailored alternating direction method. Most other publications in the field of gas transport optimization only consider pressure and flow as main physical quantities. In this work, we additionally incorporate heat power supplies and demands as well as a mixing model for different gas qualities. We demonstrate the capabilities of our method on Germany's largest transport networks and hereby present numerical results on the largest instances that were ever reported in the literature for this problem class. Y1 - 2016 U6 - https://doi.org/10.1016/j.compchemeng.2015.07.005 VL - 82 IS - 2 SP - 303 EP - 317 ER - TY - INPR A1 - Beck, Yasmine A1 - Ljubic, Ivana A1 - Schmidt, Martin T1 - A Survey on Bilevel Optimization Under Uncertainty N2 - 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. KW - Bilevel optimization KW - Optimization under uncertainty KW - Bounded rationality KW - Survey Y1 - 2022 ER - TY - INPR A1 - Molan, Ioana A1 - Schmidt, Martin T1 - Using Neural Networks to Solve Linear Bilevel Problems with Unknown Lower Level N2 - 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. KW - Bilevel optimization KW - Unknown follower problems KW - Neural networks KW - Lipschitz optimization Y1 - 2022 ER - TY - INPR A1 - Horländer, Andreas A1 - Schmidt, Martin T1 - A Penalty Branch-and-Bound Method for Mixed-Integer Quadratic Bilevel Problems N2 - 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. KW - Bilevel optimization KW - Branch-and-bound KW - Penalty methods KW - Mixed-integer optimization Y1 - 2022 ER - TY - INPR A1 - Hante, Falk A1 - Krug, Richard A1 - Schmidt, Martin T1 - Time-Domain Decomposition for Mixed-Integer Optimal Control Problems N2 - We consider mixed-integer optimal control problems, whose optimality conditions involve global combinatorial optimization aspects for the corresponding Hamiltonian pointwise in time. We propose a time-domain decomposition, which makes this problem class accessible for mixed-integer programming using parallel-in-time direct discretizations. The approach is based on a decomposition of the optimality system and the interpretation of the resulting subproblems as suitably chosen mixed-integer optimal control problems on subintervals in time. An iterative procedure then ensures continuity of the states at the boundaries of the subintervals via co-state information encoded in virtual controls. We prove convergence of this iterative scheme for discrete-continuous linear-quadratic problems and present numerical results both for linear-quadratic as well as nonlinear problems. KW - Mixed-integer optimal control problems KW - Time-domain decomposition KW - Mixed-integer nonlinear optimization KW - Convergence Y1 - 2021 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Grimm, Veronika A1 - Schmidt, Martin T1 - Outer Approximation for Global Optimization of Mixed-Integer Quadratic Bilevel Problems JF - Mathematical Programming (Series B) N2 - 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. KW - Bilevel optimization KW - Outer approximation KW - Quadratic programming KW - Convex mixed-integer nonlinear optimization Y1 - 2019 ER - TY - JOUR A1 - Grimm, Veronika A1 - Kleinert, Thomas A1 - Liers, Frauke A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - Optimal Price Zones of Electricity Markets: A Mixed-Integer Multilevel Model and Global Solution Approaches JF - Optimization Methods and Software N2 - Mathematical modeling of market design issues in liberalized electricity markets often leads to mixed-integer nonlinear multilevel optimization problems for which no general-purpose solvers exist and which are intractable in general. In this work, we consider the problem of splitting a market area into a given number of price zones such that the resulting market design yields welfare-optimal outcomes. This problem leads to a challenging multilevel model that contains a graph-partitioning problem with multi-commodity flow connectivity constraints and nonlinearities due to proper economic modeling. Furthermore, it has highly symmetric solutions. We develop different problem-tailored solution approaches. In particular, we present an extended KKT transformation approach as well as a generalized Benders approach that both yield globally optimal solutions. These methods, enhanced with techniques such as symmetry breaking and primal heuristics, are evaluated in detail on academic as well as on realistic instances. It turns out that our approaches lead to effective solution methods for the difficult optimization tasks presented here, where the problem-specific generalized Benders approach performs considerably better than the methods based on KKT transformation. KW - Multilevel Optimization KW - Mixed-Integer Nonlinear Optimization KW - Graph Partitioning KW - Generalized Benders Decomposition KW - Electricity Market Design} Y1 - 2017 IS - 34(2) SP - 406 EP - 436 ER - TY - JOUR A1 - Grimm, Veronika A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - A Multilevel Model of the European Entry-Exit Gas Market JF - Mathematical Methods of Operations Research N2 - In entry-exit gas markets as they are currently implemented in Europe, network constraints do not affect market interaction beyond the technical capacities determined by the TSO that restrict the quantities individual firms can trade at the market. It is an up to now unanswered question to what extent existing network capacity remains unused in an entry-exit design and to what extent feasible adjustments of the market design could alleviate inefficiencies. In this paper, we offer a four-level modeling framework that is capable of analyzing these issues and provide some first results on the model structure. In order to decouple gas trading from network congestion management, the TSO is required to determine technical capacities and corresponding booking fees at every entry and exit node up front. Firms book those capacities, which gives them the right to charge or discharge an amount of gas at a certain node up to this capacity in every scenario. Beyond these technical capacities and the resulting bookings, gas trade is unaffected by network constraints. The technical capacities have to ensure that transportation of traded quantities is always feasible. We assume that the TSO is regulated and determines technical capacities, fees, and transportation costs under a welfare objective. As a first step we moreover assume perfect competition among gas traders and show that the booking and nomination decisions can be analyzed in a single level. We prove that this aggregated model has a unique solution. We also show that the TSO's decisions can be subsumed in one level as well. If so, the model boils down to a mixed-integer nonlinear bilevel problem with robust aspects. In addition, we provide a first-best benchmark that allows to assess welfare losses that occur in an entry-exit system. Our approach provides a generic framework to analyze various aspects in the context of semi-liberalized gas markets. Therefore, we finally discuss and provide guidance on how to include several important aspects into the approach, such as network and production capacity investment, uncertain data, market power, and intra-day trading. KW - Entry-Exit System KW - Gas Market KW - Multilevel Modeling Y1 - 2017 IS - 89(2) SP - 223 EP - 255 ER - TY - JOUR A1 - Kramer, Anja A1 - Krebs, Vanessa A1 - Schmidt, Martin T1 - Strictly and Γ-Robust Counterparts of Electricity Market Models: Perfect Competition and Nash-Cournot Equilibria JF - Operations Research Perspectives N2 - 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. KW - Robust optimization KW - Linear complementarity problems KW - Electricity market equilibrium models KW - Perfect competition KW - Nash-Cournot competition Y1 - 2018 IS - 89(2) SP - 100197 ER - TY - JOUR A1 - Hojny, Christopher A1 - Joormann, Imke A1 - Lüthen, Hendrik A1 - Schmidt, Martin T1 - Mixed-Integer Programming Techniques for the Connected Max-k-Cut Problem JF - Mathematical Programming Computation N2 - 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. KW - Max-cut KW - Connectivity KW - Branch-and-cut KW - Mixed-integer programming Y1 - 2018 ER - TY - JOUR A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Thürauf, Johannes T1 - Structural Properties of Feasible Bookings in the European Entry-Exit Gas Market System JF - 4OR N2 - 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. KW - Gas networks KW - Booking KW - Entry-exit system KW - Convexity KW - Flow models Y1 - 2018 U6 - https://doi.org/10.1007/s10288-019-00411-3 IS - 18 SP - 197 EP - 218 ER - TY - JOUR A1 - Ambrosius, Mirjam A1 - Grimm, Veronika A1 - Kleinert, Thomas A1 - Liers, Frauke A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - Endogenous Price Zones and Investment Incentives in Electricity Markets: An Application of Multilevel Optimization with Graph Partitioning JF - Energy Economics N2 - 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. KW - Electricity Markets KW - Price Zones KW - Investment Incentives KW - Multilevel Optimization KW - Graph Partitioning Y1 - 2018 IS - 92 ER - TY - JOUR A1 - Hante, Falk M. A1 - Schmidt, Martin T1 - Convergence of Finite-Dimensional Approximations for Mixed-Integer Optimization with Differential Equations JF - Control and Cybernetics N2 - 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. KW - Optimization with differential equations KW - Optimal value function KW - Lipschitz continuity KW - Parametric optimization KW - Mixed-integer nonlinear programming Y1 - 2018 ER - TY - JOUR A1 - Labbé, Martine A1 - Plein, Fränk A1 - Schmidt, Martin T1 - Bookings in the European Gas Market: Characterisation of Feasibility and Computational Complexity Results JF - Optimization and Engineering N2 - 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. KW - Gas networks KW - Booking KW - Nomination KW - Computational complexity KW - Trees Y1 - 2018 IS - 21(1) SP - 305 EP - 334 ER - TY - JOUR A1 - Krebs, Vanessa A1 - Schmidt, Martin T1 - Γ-Robust Linear Complementarity Problems JF - Optimization Methods and Software N2 - 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. KW - Linear complementarity problems KW - Robust optimization KW - Optimization under uncertainty KW - Γ-robustness KW - Tractable counterparts Y1 - 2019 ER - TY - JOUR A1 - Krug, Richard A1 - Mehrmann, Volker A1 - Schmidt, Martin T1 - Nonlinear Optimization of District Heating Networks JF - Optimization and Engineering N2 - 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. KW - District heating networks KW - Nonlinear optimization KW - Euler equations KW - Differential-algebraic equations KW - Complementarity constraints Y1 - 2019 IS - 22(2) SP - 783 EP - 819 ER - TY - INPR A1 - Krebs, Vanessa A1 - Müller, Michael A1 - Schmidt, Martin T1 - Γ-Robust Linear Complementarity Problems with Ellipsoidal Uncertainty Sets T2 - International Transactions in Operational Research N2 - 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. KW - Robust optimization KW - Linear complementarity problems KW - Ellipsoidal uncertainty sets KW - Traffic equilibrium problems Y1 - 2019 IS - 29(1) SP - 417 EP - 441 ER - TY - JOUR A1 - Labbé, Martine A1 - Plein, Fränk A1 - Schmidt, Martin A1 - Thürauf, Johannes T1 - Deciding Feasibility of a Booking in the European Gas Market on a Cycle is in P for the Case of Passive Networks JF - Networks N2 - 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. KW - Gas networks KW - European entry-exit market KW - Bookings KW - Potential-based flows KW - Computational complexity Y1 - 2019 U6 - https://doi.org/10.1007/s00186-021-00752-y VL - 78 IS - 2 SP - 128 EP - 152 ER - TY - JOUR A1 - Egerer, Jonas A1 - Grimm, Veronika A1 - Kleinert, Thomas A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - The Impact of Neighboring Markets on Renewable Locations, Transmission Expansion, and Generation Investment JF - European Journal of Operational Research N2 - 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. KW - Neighboring Markets KW - Renewables KW - Network Expansion KW - Multilevel Optimization KW - Benders Decomposition Y1 - 2019 ER - TY - JOUR A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Thürauf, Johannes T1 - Computing Technical Capacities in the European Entry-Exit Gas Market is NP-Hard JF - Annals of Operations Research N2 - 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. KW - European Entry-Exit Gas Market KW - Technical Capacities KW - Potential-Based Flows KW - Computational Complexity KW - NP-Hardness Y1 - 2020 U6 - https://doi.org/10.1007/s10479-020-03725-2 IS - 295 SP - 337 EP - 362 ER - TY - JOUR A1 - Çelebi, Emre A1 - Krebs, Vanessa A1 - Schmidt, Martin T1 - Γ-Robust Electricity Market Equilibrium Models with Transmission and Generation Investments JF - Energy Systems N2 - 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. KW - Robust optimization KW - Robust market equilibria KW - Electricity market equilibrium models KW - Transmission and generation investment KW - Perfect competition Y1 - 2020 ER - TY - JOUR A1 - Gabriel, Steven A. A1 - Leal, Marina A1 - Schmidt, Martin T1 - Solving Binary-Constrained Mixed Complementarity Problems Using Continuous Reformulations JF - Computers & Operations Research N2 - 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. KW - Binary-constrained mixed complementarity problems KW - Mixed-integer optimization KW - Continuous reformulations KW - Spatial price equilibrium problems Y1 - 2020 ER - TY - JOUR A1 - Roland, Marius A1 - Schmidt, Martin T1 - Mixed-Integer Nonlinear Optimization for District Heating Network Expansion JF - at - Automatisierungstechnik N2 - 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. KW - District heating networks KW - Network expansion KW - Mixed-integer nonlinear optimization Y1 - 2020 ER - TY - JOUR A1 - Grimm, Veronika A1 - Grübel, Julia A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - Nonconvex Equilibrium Models for Gas Market Analysis: Failure of Standard Techniques and Alternative Modeling Approaches JF - European Journal on Operational Research N2 - This paper provides a first approach to assess gas market interaction on a network with nonconvex flow models. In the simplest possible setup that adequately reflects gas transport and market interaction, we elaborate on the relation of the solution of a simultaneous competitive gas market game, its corresponding mixed nonlinear complementarity problem (MNCP), and a first-best benchmark. We provide conditions under which the solution of the simultaneous game is also the solution of the corresponding MNCP. However, equilibria cannot be determined by the MNCP as the transmission system operator's (TSO’s) first-order conditions are insufficient, which goes back to nonconvexities of the gas flow model. This also implies that the welfare maximization problem may have multiple solutions that sometimes do not even coincide with any of the market equilibria. Our analysis shows that, even in the absence of strategic firms, market interaction fails to implement desirable outcomes from a welfare perspective due to the TSO’s incentive structure. We conclude that the technical environment calls for a market design that commits the TSO to a welfare objective through regulation and propose a design where the market solution corresponds to a welfare maximum and vice versa. KW - Natural Gas Markets KW - Nonconvex Equilibrium Models KW - Uniqueness KW - Multiplicity KW - Fundamental Welfare Theorems Y1 - 2017 IS - 273(3) SP - 1097 EP - 1108 ER - TY - JOUR A1 - Krebs, Vanessa A1 - Schmidt, Martin T1 - Uniqueness of Market Equilibria on Networks with Transport Costs JF - Operations Research Perspectives N2 - We study the existence and uniqueness of equilibria for perfectly competitive markets in capacitated transport networks. The model under consideration is rather general so that it captures basic aspects of related models in, e.g., gas or electricity networks. We formulate the market equilibrium model as a mixed complementarity problem and show the equivalence to a welfare maximization problem. Using the latter we prove uniqueness of the resulting equilibrium for piecewise linear and symmetric transport costs under additional mild assumptions. Moreover, we show the necessity of these assumptions by illustrating examples that possess multiple solutions if our assumptions are violated. KW - Market Equilibria KW - Networks KW - Transport Costs KW - Uniqueness KW - Perfect Competition Y1 - 2017 IS - 5 SP - 169 EP - 173 ER - TY - JOUR A1 - Mehrmann, Volker A1 - Schmidt, Martin A1 - Stolwijk, Jeroen J. T1 - Model and Discretization Error Adaptivity within Stationary Gas Transport Optimization JF - Vietnam Journal of Mathematics N2 - The minimization of operation costs for natural gas transport networks is studied. Based on a recently developed model hierarchy ranging from detailed models of instationary partial differential equations with temperature dependence to highly simplified algebraic equations, modeling and discretization error estimates are presented to control the overall error in an optimization method for stationary and isothermal gas flows. The error control is realized by switching to more detailed models or finer discretizations if necessary to guarantee that a prescribed model and discretization error tolerance is satisfied in the end. We prove convergence of the adaptively controlled optimization method and illustrate the new approach with numerical examples. KW - Gas network optimization KW - Isothermal stationary Euler equations KW - Model hierarchy KW - Adaptive error control KW - Marking strategy Y1 - 2017 IS - 46(4) SP - 779 EP - 801 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Schmidt, Martin T1 - Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method JF - INFORMS Journal on Computing N2 - 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. KW - Bilevel optimization KW - Mixed-integer bilevel optimization KW - Stationary points KW - Penalty methods KW - Alternating direction methods Y1 - 2019 U6 - https://doi.org/10.1287/ijoc.2019.0945 IS - 33 (1) SP - 198 EP - 215 ER - TY - JOUR A1 - Grübel, Julia A1 - Kleinert, Thomas A1 - Krebs, Vanessa A1 - Orlinskaya, Galina A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Thürauf, Johannes T1 - On Electricity Market Equilibria with Storage: Modeling, Uniqueness, and a Distributed ADMM JF - Computers & Operations Research N2 - 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. Y1 - 2019 U6 - https://doi.org/10.1016/j.cor.2019.104783 IS - 114 ER - TY - INPR A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Weninger, Dieter T1 - A Decomposition Heuristic for Mixed-Integer Supply Chain Problems T2 - Operations Research Letters N2 - 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. KW - Supply chain KW - Mixed-integer optimization KW - Decomposition KW - Penalty method KW - Alternating direction methods Y1 - 2019 IS - 48(3) SP - 225 EP - 232 ER - TY - INPR A1 - Kleinert, Thomas A1 - Labbé, Martine A1 - Plein, Fränk A1 - Schmidt, Martin T1 - There's No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization T2 - Operations Research N2 - 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. KW - Bilevel optimization KW - Mathematical programs with complementarity constraints (MPCC) KW - Bounding polyhedra KW - Big-M KW - Hardness Y1 - 2019 IS - 68(6) SP - 1716 EP - 1721 ER - TY - JOUR A1 - Grimm, Veronika A1 - Orlinskaya, Galina A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - Optimal Design of Retailer-Prosumer Electricity Tariffs Using Bilevel Optimization JF - Computers & Operations Research N2 - 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. KW - Electricity tariffs KW - Pricing KW - Bilevel optimization KW - Mixed-integer optimization KW - Tariff design Y1 - 2019 IS - 114 ER - TY - JOUR A1 - Hauschild, Sarah-Alexa A1 - Marheineke, Nicole A1 - Mehrmann, Volker A1 - Mohring, Jan A1 - Badlyan, Arbi Moses A1 - Rein, Markus A1 - Schmidt, Martin T1 - Port-Hamiltonian modeling of district heating networks JF - Progress in Differential Algebraic Equations II (edited by Reis T., Grundel S., and Schöps S). Differential-Algebraic Equations Forum N2 - 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. KW - Partial differential equations on networks KW - Port-Hamiltonian model framework KW - Energy-based formulation KW - District heating network KW - Thermodynamic fluid flow Y1 - 2019 ER - TY - JOUR A1 - Kleinert, Thomas A1 - Schmidt, Martin T1 - Global Optimization of Multilevel Electricity Market Models Including Network Design and Graph Partitioning JF - Discrete Optimization N2 - We consider the combination of a network design and graph partitioning model in a multilevel framework for determining the optimal network expansion and the optimal zonal configuration of zonal pricing electricity markets, which is an extension of the model discussed in [25] that does not include a network design problem. The two classical discrete optimization problems of network design and graph partitioning together with nonlinearities due to economic modeling yield extremely challenging mixed-integer nonlinear multilevel models for which we develop two problem-tailored solution techniques. The first approach relies on an equivalent bilevel formulation and a standard KKT transformation thereof including novel primal-dual bound tightening techniques, whereas the second is a tailored generalized Benders decomposition. For the latter, we strengthen the Benders cuts of [25] by using the structure of the newly introduced network design subproblem. We prove for both methods that they yield global optimal solutions. Afterward, we compare the approaches in a numerical study and show that the tailored Benders approach clearly outperforms the standard KKT transformation. Finally, we present a case study that illustrates the economic effects that are captured in our model. KW - Network design KW - Graph partitioning KW - Multilevel optimization KW - Mixed-integer optimization KW - Electricity market design Y1 - 2018 IS - 33 SP - 43 EP - 69 ER - TY - JOUR A1 - Schmidt, Martin A1 - Sirvent, Mathias A1 - Wollner, Winnifried T1 - The Cost of Not Knowing Enough: Mixed-Integer Optimization with Implicit Lipschitz Nonlinearities JF - Optimization Letters N2 - 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. KW - Mixed-Integer Nonlinear Optimization, Global Optimization, Lipschitz Optimization, Gas Networks Y1 - 2018 ER - TY - JOUR A1 - Schewe, Lars A1 - Schmidt, Martin T1 - The Impact of Potential-Based Physics Models on Pricing in Energy Networks JF - Central European Journal of Operations Research N2 - Pricing of access to energy networks is an important issue in liberalized energy sectors because of the natural monopoly character of the underlying transport infrastructures. We introduce a general pricing framework for potential-based energy flows in arbitrarily structured transport networks. In different specifications of our general pricing model we discuss first- and second-best pricing results and compare different pricing outcomes of potential-free and potential-based energy flow models. Our results show that considering nonlinear laws of physics leads to significantly different pricing results on networks and that these differences can only be seen in sufficiently complex, e.g., cyclic, networks as they can be found in real-world situations. KW - Energy Networks KW - Pricing KW - Gas Networks KW - Electricity Networks Y1 - 2018 IS - 28(3) SP - 1003 EP - 1029 ER - TY - INPR A1 - Grimm, Veronika A1 - Hintermüller, Michael A1 - Huber, Olivier A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Zöttl, Gregor T1 - A PDE-Constrained Generalized Nash Equilibrium Approach for Modeling Gas Markets with Transport N2 - We investigate a class of generalized Nash equilibrium problems (GNEPs) in which the objectives of the individuals are interdependent and the shared constraint consists of a system of partial differential equations. This setup is motivated by the modeling of strategic interactions of competing firms, which explicitly take into account the dynamics of transporting a commodity, such as natural gas, through a network. We establish the existence of a variational equilibrium of the GNEP. In the case of symmetric firms, we identify an equivalent optimization problem. We use this model to numerically explore the impact of linepacking, that is the use of the network as a temporary storage device. In particular, we study the firms' decisions under various linepacking abilities and analyze which market participants benefit from it. Y1 - ER - TY - INPR A1 - Hante, Falk M. A1 - Schmidt, Martin T1 - Gas Transport Network Optimization: Mixed-Integer Nonlinear Models N2 - 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. KW - Gas networks KW - Mixed-integer nonlinear optimization KW - Mixed-integer linear optimization KW - Nonlinear optimization Y1 - 2023 ER - TY - GEN A1 - Beck, Yasmine A1 - Schmidt, Martin T1 - A Gentle and Incomplete Introduction to Bilevel Optimization N2 - These are lecture notes on bilevel optimization. The class of bilevel optimization problems is formally introduced and motivated using examples from different fields. Afterward, the main focus is on how to solve linear and mixed-integer linear bilevel optimization problems. To this end, we first consider various single-level reformulations of bilevel optimization problems with linear or convex follower problems, discuss geometric properties of linear bilevel problems, and study different algorithms for solving linear bilevel problems. Finally, we consider mixed-integer linear bilevel problems, discuss the main obstacles for deriving exact as well as effective solution methods, and derive a branch-and-bound method for solving these problems. KW - Bilevel Optimization KW - Lecture Notes Y1 - 2021 ER - TY - INPR A1 - Cattaruzza, Diego A1 - Labbé, Martine A1 - Petris, Matteo A1 - Roland, Marius A1 - Schmidt, Martin T1 - Exact and Heuristic Solution Techniques for Mixed-Integer Quantile Minimization Problems N2 - We consider mixed-integer linear quantile minimization problems that yield large-scale problems that are very hard to solve for real-world instances. We motivate the study of this problem class by two important real-world problems: a maintenance planning problem for electricity networks and a quantile-based variant of the classic portfolio optimization problem. For these problems, we develop valid inequalities and present an overlapping alternating direction method. Moreover, we discuss an adaptive scenario clustering method for which we prove that it terminates after a finite number of iterations with a global optimal solution. We study the computational impact of all presented techniques and finally show that their combination leads to an overall method that can solve the maintenance planning problem on large-scale real-world instances provided by the ROADEF challenge 2020 and that they also lead to significant improvements when solving a quantile-version of the classic portfolio optimization problem. KW - Quantile Minimization KW - Value-at-Risk (VaR) KW - Mixed-Integer Optimization KW - Valid Inequalities KW - Adaptive Clustering Y1 - 2021 ER - TY - INPR A1 - Grimm, Veronika A1 - Grübel, Julia A1 - Schmidt, Martin A1 - Schwartz, Alexandra A1 - Wiertz, Ann-Kathrin A1 - Zöttl, Gregor T1 - On a Tractable Single-Level Reformulation of a Multilevel Model of the European Entry-Exit Gas Market with Market Power N2 - We propose a framework that allows to quantitatively analyze the interplay of the different agents involved in gas trade and transport in the context of the European entry-exit system. While previous contributions focus on the case of perfectly competitive buyers and sellers of gas, our novel framework considers the mathematically more challenging case of a strategic and monopolistic gas seller. We present a multilevel framework that is suitable to capture the sequential nature of the decisions taken. We then derive sufficient conditions that allow for reformulating the challenging four-level model as a computationally tractable single-level reformulation. We prove the correctness of this reformulation and use it for solving several test instances to illustrate the applicability of our approach. KW - Multilevel optimization KW - Reformulations KW - Gas markets KW - Market power Y1 - 2023 ER - TY - INPR A1 - Schmidt, Martin A1 - Thürauf, Johannes T1 - An Exact Method for Nonlinear Network Flow Interdiction Problems N2 - 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. KW - Interdiction Games KW - Bilevel Optimization KW - Potential-Based Flows KW - Mixed-Integer Nonlinear Optimization Y1 - 2022 ER - TY - INPR A1 - Grübel, Julia A1 - Krug, Richard A1 - Schmidt, Martin A1 - Wollner, Winnifried T1 - A Successive Linear Relaxation Method for MINLPs with Multivariate Lipschitz Continuous Nonlinearities N2 - 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. KW - Mixed-Integer Nonlinear Optimization KW - Global Optimization KW - Lipschitz Optimization KW - Bilevel Optimization KW - Gas Networks Y1 - 2022 ER - TY - INPR A1 - Hante, Falk M. A1 - Schmidt, Martin T1 - Gas Transport Network Optimization: PDE-Constrained Models N2 - 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. KW - Gas networks KW - Partial differential equations KW - Optimal control KW - PDE-constrained optimization KW - Modeling Y1 - 2023 ER - TY - INPR A1 - Beck, Yasmine A1 - Ljubic, Ivana A1 - Schmidt, Martin T1 - Exact Methods for Discrete Γ-Robust Interdiction Problems with an Application to the Bilevel Knapsack Problem N2 - Developing solution methods for discrete bilevel problems is known to be a challenging task - even if all parameters of the problem are exactly known. Many real-world applications of bilevel optimization, however, involve data uncertainty. We study discrete min-max problems with a follower who faces uncertainties regarding the parameters of the lower-level problem. Adopting a Γ-robust approach, we present an extended formulation and a multi-follower formulation to model this type of problem. For both settings, we provide a generic branch-and-cut framework. Specifically, we investigate interdiction problems with a monotone Γ-robust follower and we derive problem-tailored cuts, which extend existing techniques that have been proposed for the deterministic case. For the Γ-robust knapsack interdiction problem, we computationally evaluate and compare the performance of the proposed algorithms for both modeling approaches. KW - Bilevel optimization KW - Robust optimization KW - Knapsack interdiction KW - Mixed-integer programming KW - Branch-and-Cut Y1 - 2021 ER - TY - INPR A1 - Hannes, Dänschel A1 - Volker, Mehrmann A1 - Roland, Marius A1 - Schmidt, Martin T1 - Adaptive Nonlinear Optimization of District Heating Networks Based on Model and Discretization Catalogs N2 - 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. KW - District heating networks KW - Adaptive methods KW - Nonlinear optimization Y1 - 2022 ER - TY - INPR A1 - Beck, Yasmine A1 - Schmidt, Martin A1 - Thürauf, Johannes A1 - Bienstock, Daniel T1 - On a Computationally Ill-Behaved Bilevel Problem with a Continuous and Nonconvex Lower Level N2 - 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. KW - Bilevel optimization KW - Nonconvex lower levels KW - Approximate feasibility KW - Global optimization Y1 - 2022 ER - TY - INPR A1 - Goerigk, Marc A1 - Kurtz, Jannis A1 - Schmidt, Martin A1 - Thürauf, Johannes T1 - Connections and Reformulations between Robust and Bilevel Optimization N2 - Robust and bilevel optimization share the common feature that they involve a certain multilevel structure. Hence, although they model something rather different when used in practice, they seem to have a similar mathematical structure. In this paper, we analyze the connections between different types of robust problems (strictly robust problems with and without decision-dependence of their uncertainty sets, min-max-regret problems, and two-stage robust problems) as well as of bilevel problems (optimistic problems, pessimistic problems, and robust bilevel problems). It turns out that bilevel optimization seems to be more general in the sense that for most types of robust problems, one can find proper reformulations as bilevel problems but not necessarily the other way around. We hope that these results pave the way for a stronger connection between the two fields - in particular to use both theory and algorithms from one field in the other and vice versa. KW - Bilevel optimization KW - Robust optimization KW - Reformulations Y1 - 2023 ER - TY - INPR A1 - Thürauf, Johannes A1 - Grübel, Julia A1 - Schmidt, Martin T1 - Adjustable Robust Nonlinear Network Design under Demand Uncertainties N2 - We study network design problems for nonlinear and nonconvex flow models under demand uncertainties. To this end, we apply the concept of adjustable robust optimization to compute a network design that admits a feasible transport for all, possibly infinitely many, demand scenarios within a given uncertainty set. For solving the corresponding adjustable robust mixed-integer nonlinear optimization problem, we show that a given network design is robust feasible, i.e., it admits a feasible transport for all demand uncertainties, if and only if a finite number of worst-case demand scenarios can be routed through the network. We compute these worst-case scenarios by solving polynomially many nonlinear optimization problems. Embedding this result for robust feasibility in an adversarial approach leads to an exact algorithm that computes an optimal robust network design in a finite number of iterations. Since all of the results are valid for general potential-based flows, the approach can be applied to different utility networks such as gas, hydrogen, or water networks. We finally demonstrate the applicability of the method by computing robust gas networks that are protected from future demand fluctuations. KW - Robust Optimization KW - Nonlinear Flows KW - Potential-based Networks KW - Demand Uncertainties KW - Mixed-integer Nonlinear Optimization Y1 - 2024 ER -