Search

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

We present a market model of a liberalized aviation market with independent decision makers. The model consists of a hierarchical, trilevel optimization problem where perfectly competitive budget-constrained airports decide (in the first level) on optimal runway capacity extensions and airport charges by anticipating long-term fleet investment and medium-term aircraft scheduling decisions taken by a set of imperfectly competitive airlines (in the second level). Both airports and airlines anticipate the short-term outcome of a perfectly competitive ticket market (in the third level). We compare our trilevel model to an integrated single-level (benchmark) model in which investments, scheduling, and market-clearing decisions are simultaneously taken by a welfare-maximizing social planner. Using a simple six airports example from the literature, we illustrate the inefficiency of long-run investments in both runway capacity and aircraft fleet which may be observed in aviation markets with imperfectly competitive airlines.

In this paper, we study the transient optimization of gas networks, focusing in particular on maximizing the storage capacity of the network. We include nonlinear gas physics and active elements such as valves and compressors, which due to their switching lead to discrete decisions. The former is described by a model derived from the Euler equations that is given by a coupled system of nonlinear parabolic partial differential equations ( $${\text{PDEs}}$$ ). We tackle the resulting mathematical optimization problem by a first-discretize-then-optimize approach. To this end, we introduce a new discretization of the underlying system of parabolic $${\text{PDEs}}$$ and prove well-posedness for the resulting nonlinear discretized system. Endowed with this discretization, we model the problem of maximizing the storage capacity as a non-convex mixed-integer nonlinear problem ( $${\text{MINLP}}$$ ). For the numerical solution of the $${\text{MINLP}}$$ , we algorithmically extend a well-known relaxation approach that has already been used very successfully in the field of stationary gas network optimization. This method allows us to solve the problem to global optimality by iteratively solving a series of mixed-integer problems. Finally, we present two case studies that illustrate the applicability of our approach.

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 many 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 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 study the transient optimization of gas transport networks including both discrete controls due to switching of controllable elements and nonlinear fluid dynamics described by the system of isothermal Euler equations, which are partial differential equations in time and 1-dimensional space. This combination leads to mixed-integer optimization problems subject to nonlinear hyperbolic partial differential equations on a graph. We propose an instantaneous control approach in which suitable Euler discretizations yield systems of ordinary differential equations on a graph. This networked system of ordinary differential equations is shown to be well-posed and affine-linear solutions of these systems are derived analytically. As a consequence, finite-dimensional mixed-integer linear optimization problems are obtained for every time step that can be solved to global optimality using general-purpose solvers. We illustrate our approach in practice by presenting numerical results on a realistic gas transport network.

The article summarizes the findings of my Ph.D. thesis finished in 2018; see (Sirvent, Incorporating differential equations into mixed-integer programming for gas transport optimization. FAU University Press, Erlangen, 2018). For this report, we specifically focus on one of the three new global decomposition algorithms, which is used to solve stationary gas transport optimization problems with ordinary differential equations. Moreover, we refer to the promising numerical results for the Greek natural gas transport network.

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 (extensible markup language) format. In this paper, we explain this format and present the instances that are available in the library.