Refine
Year of publication
Keywords
We study network design problems for nonlinear and nonconvex flow models under demand uncertainties. To this end, we apply the concept of adjustable robust optimization to compute a network design that admits a feasible transport for all, possibly infinitely many, demand scenarios within a given uncertainty set. For solving the corresponding adjustable robust mixed-integer nonlinear optimization problem, we show that a given network design is robust feasible, i.e., it admits a feasible transport for all demand uncertainties, if and only if a finite number of worst-case demand scenarios can be routed through the network. We compute these worst-case scenarios by solving polynomially many nonlinear optimization problems. Embedding this result for robust feasibility in an adversarial approach leads to an exact algorithm that computes an optimal robust network design in a finite number of iterations. Since all of the results are valid for general potential-based flows, the approach can be applied to different utility networks such as gas, hydrogen, or water networks. We finally demonstrate the applicability of the method by computing robust gas networks that are protected from future demand fluctuations.
Although modern societies strive towards energy systems that are entirely based on renewable energy carriers, natural gas is still one of the most important energy sources. This became even more obvious in Europe with Russia's 2022 war against the Ukraine and the resulting stop of gas supplies from Russia. Besides that it is very important to use this scarce resource efficiently. To this end, it is also of significant relevance that its transport is organized in the most efficient, i.e., cost- or energy-efficient, way. The corresponding mathematical optimization models have gained a lot of attention in the last decades in different optimization communities. These models are highly nonlinear mixed-integer problems that are constrained by algebraic constraints and partial differential equations (PDEs), which usually leads to models that are not tractable. Hence, simplifications have to be made and in this chapter, we present a commonly accepted finite-dimensional stationary model, i.e., a model in which the steady-state solutions of the PDEs are approximated with algebraic constraints. For more details about the involved PDEs and the treatment of transient descriptions we refer to Hante and Schmidt (2023). The presented finite-dimensional as well as mixed-integer nonlinear and nonconvex model is still highly challenging if it needs to be solved for real-world gas transport networks. Hence, we also review some classic solution approaches from the literature.
We propose a framework that allows to quantitatively analyze the interplay of the different agents involved in gas trade and transport in the context of the European entry-exit system. While previous contributions focus on the case of perfectly competitive buyers and sellers of gas, our novel framework considers the mathematically more challenging case of a strategic and monopolistic gas seller. We present a multilevel framework that is suitable to capture the sequential nature of the decisions taken. We then derive sufficient conditions that allow for reformulating the challenging four-level model as a computationally tractable single-level reformulation. We prove the correctness of this reformulation and use it for solving several test instances to illustrate the applicability of our approach.
The optimal control of gas transport networks was and still is a very important topic for modern economies and societies. Accordingly, a lot of research has been carried out on this topic during the last years and decades. Besides mixed-integer aspects in gas transport network optimization, one of the main challenges is that a physically and technically detailed modeling of transient gas dynamics leads to theoretically and computationally highly demanding models involving nonlinear partial differential equations (PDEs). For further background on the application, historical notes and a detailed discussion of mixed-integer aspects for stationary descriptions we refer to Hante and Schmidt (2023). In this chapter, we focus on the most common modeling approaches concerning transient descriptions, point out the challenges, and summarize important contributions concerning the optimization of the most relevant control parameters for this particular class of problems.
Robust and bilevel optimization share the common feature that they involve a certain multilevel structure. Hence, although they model something rather different when used in practice, they seem to have a similar mathematical structure. In this paper, we analyze the connections between different types of robust problems (strictly robust problems with and without decision-dependence of their uncertainty sets, min-max-regret problems, and two-stage robust problems) as well as of bilevel problems (optimistic problems, pessimistic problems, and robust bilevel problems). It turns out that bilevel optimization seems to be more general in the sense that for most types of robust problems, one can find proper reformulations as bilevel problems but not necessarily the other way around. We hope that these results pave the way for a stronger connection between the two fields - in particular to use both theory and algorithms from one field in the other and vice versa.
Bilevel optimization is a very active field of applied mathematics. The main reason is that bilevel optimization problems can serve as a powerful tool for modeling hierarchical decision making processes. This ability, however, also makes the resulting problems challenging to solve - both in theory and practice. Fortunately, there have been significant algorithmic advances in the field of bilevel optimization so that we can solve much larger and also more complicated problems today compared to what was possible to solve two decades ago. This results in more and more challenging bilevel problems that researchers try to solve today. This survey gives a detailed overview of one of these more challenging classes of bilevel problems: bilevel optimization under uncertainty. We review the classic ways of addressing uncertainties in bilevel optimization using stochastic or robust techniques. Moreover, we highlight that the sources of uncertainty in bilevel optimization are much richer than for usual, i.e., single-level, problems since not only the problem's data can be uncertain but also the (observation of the) decisions of the two players can be subject to uncertainty. We thus also review the field of bilevel optimization under limited observability, the area of problems considering only near-optimal decisions, and discuss intermediate solution concepts between the optimistic and pessimistic cases. Finally, we also review the rich literature on applications studied using uncertain bilevel problems such as in energy, for interdiction games and security applications, in management sciences, and networks.
Bilevel problems are used to model the interaction between two decision makers in which the lower-level problem, the so-called follower's problem, appears as a constraint in the upper-level problem of the so-called leader. One issue in many practical situations is that the follower's problem is not explicitly known by the leader. For such bilevel problems with unknown lower-level model we propose the use of neural networks to learn the follower's optimal response for given decisions of the leader based on available historical data of pairs of leader and follower decisions. Integrating the resulting neural network in a single-level reformulation of the bilevel problem leads to a challenging model with a black-box constraint. We exploit Lipschitz optimization techniques from the literature to solve this reformulation and illustrate the applicability of the proposed method with some preliminary case studies using academic and linear bilevel instances.
We propose an algorithm for solving bilevel problems with mixed-integer convex-quadratic upper level as well as convex-quadratic and continuous lower level. The method is based on a classic branch-and-bound procedure, where branching is performed on the integer constraints and on the complementarity constraints resulting from the KKT reformulation of the lower-level problem. However, instead of branching on constraints as usual, suitably chosen penalty terms are added to the objective function in order to create new subproblems in the tree. We prove the correctness of the method and present its applicability by some first numerical results.
We study network flow interdiction problems with nonlinear and nonconvex flow models. The resulting model is a max-min bilevel optimization problem in which the follower's problem is nonlinear and nonconvex. In this game, the leader attacks a limited number of arcs with the goal to maximize the load shed and the follower aims at minimizing the load shed by solving a transport problem in the interdicted network. We develop an exact algorithm consisting of lower and upper bounding schemes that computes an optimal interdiction under the assumption that the interdicted network remains weakly connected. The main challenge consists of computing valid upper bounds for the maximal load shed, whereas lower bounds can directly be derived from the follower's problem. To compute an upper bound, we propose solving a specific bilevel problem, which is derived from restricting the flexibility of the follower when adjusting the load flow. This bilevel problem still has a nonlinear and nonconvex follower's problem, for which we then prove necessary and sufficient optimality conditions. Consequently, we obtain equivalent single-level reformulations of the specific bilevel model to compute upper bounds. Our numerical results show the applicability of this exact approach using the example of gas networks.
We consider dynamic gas transport optimization problems, which lead to large-scale and nonconvex mixed-integer nonlinear optimization problems (MINLPs) on graphs. Usually, the resulting instances are too challenging to be solved by state-of-the-art MINLP solvers. In this paper, we use graph decompositions to obtain multiple optimization problems on smaller blocks, which can be solved in parallel and which may result in simpler classes of optimization problems since not every block necessarily contains mixed-integer or nonlinear aspects. For achieving feasibility at the interfaces of the several blocks, we employ a tailored consensus-based penalty alternating direction method. Our numerical results show that such decomposition techniques can outperform the baseline approach of just solving the overall MINLP from scratch. However, a complete answer to the question of how to decompose MINLPs on graphs in dependence of the given model is still an open topic for future research.
We present a novel method for mixed-integer optimization problems with multivariate and Lipschitz continuous nonlinearities. In particular, we do not assume that the nonlinear constraints are explicitly given but that we can only evaluate them and that we know their global Lipschitz constants. The algorithm is a successive linear relaxation method in which we alternate between solving a master problem, which is a mixed-integer linear relaxation of the original problem, and a subproblem, which is designed to tighten the linear relaxation of the next master problem by using the Lipschitz information about the respective functions. By doing so, we follow the ideas of Schmidt et al. (2018, 2021) and improve the tackling of multivariate constraints. Although multivariate nonlinearities obviously increase modeling capabilities, their incorporation also significantly increases the computational burden of the proposed algorithm. We prove the correctness of our method and also derive a worst-case iteration bound. Finally, we show the generality of the addressed problem class and the proposed method by illustrating that both bilevel optimization problems with nonconvex and quadratic lower levels as well as nonlinear and mixed-integer models of gas transport can be tackled by our method. We provide the necessary theory for both applications and briefly illustrate the outcomes of the new method when applied to these two problems.
We propose an adaptive optimization algorithm for operating district heating networks in a stationary regime. The behavior of hot water flow in the pipe network is modeled using the incompressible Euler equations and a suitably chosen energy equation. By applying different simplifications to these equations, we derive a catalog of models. Our algorithm is based on this catalog and adaptively controls where in the network which model is used. Moreover, the granularity of the applied discretization is controlled in a similar adaptive manner. By doing so, we are able to obtain optimal solutions at low computational costs that satisfy a prescribed tolerance w.r.t. the most accurate modeling level. To adaptively control the switching between different levels and the adaptation of the discretization grids, we derive error measure formulas and a posteriori error measure estimators. Under reasonable assumptions we prove that the adaptive algorithm terminates after finitely many iterations. Our numerical results show that the algorithm is able to produce solutions for problem instances that have not been solvable before.
It is well known that bilevel optimization problems are hard to solve both in theory and practice. In this paper, we highlight a further computational difficulty when it comes to solving bilevel problems with continuous but nonconvex lower levels. Even if the lower-level problem is solved to ɛ-feasibility regarding its nonlinear constraints for an arbitrarily small but positive ɛ, the obtained bilevel solution as well as its objective value may be arbitrarily far away from the actual bilevel solution and its actual objective value. This result even holds for bilevel problems for which the nonconvex lower level is uniquely solvable, for which the strict complementarity condition holds, for which the feasible set is convex, and for which Slater's constraint qualification is satisfied for all feasible upper-level decisions. Since the consideration of ɛ-feasibility cannot be avoided when solving nonconvex problems to global optimality, our result shows that computational bilevel optimization with continuous and nonconvex lower levels needs to be done with great care. Finally, we illustrate that the nonlinearities in the lower level are the key reason for the observed bad behavior by showing that linear bilevel problems behave much better at least on the level of feasible solutions.
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.
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.
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.