Refine
Year of publication
Keywords
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.
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.
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.
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.
Time-Domain Decomposition for Optimal Control Problems Governed by Semilinear Hyperbolic Systems
(2020)
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
A Bilevel Optimization Approach to Decide the Feasibility of Bookings in the European Gas Market
(2021)
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.
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.
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.
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.
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.
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.