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 - 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 - 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 - 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 - 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 - 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 - 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 - 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 -