EURO Doctoral Dissertation Award 2019 - Finalists

The three finalists of the 2019 EURO Doctoral Dissertation Award are:

 

 

Elizabeth Rodriquez-Heck, Lehrstuhl für Operations Research, RWTH Aachen University

Linear and quadratic reformulations of nonlinear optimization problems in binary variables

 

The problem of optimizing a multilinear polynomial on binary variables without additional constraints arises in a variety of applications. We are interested in resolution methods based on reformulations of this nonlinear problem into a linear or a quadratic one, an approach that attempts to draw benefit from the existing literature on integer linear and quadratic programming. In the context of linear reformulations, we consider the standard linearization, a well-known reformulation method that consists in introducing an auxiliary variable to represent each higher-degree monomial, where the association of auxiliary variables to monomials is achieved using linear constraints. A first contribution of this thesis is a characterization of cases for which the continuous relaxation of the standard linearization provides integer solutions. Additionally, we define a class of valid inequalities called 2-links modeling interactions between pairs of intersecting monomials. For functions with exactly two nonlinear monomials, we prove that the 2-links together with the standard linearization inequalities completely describe the convex hull of their feasible integer points. Moreover, the 2-link inequalities strengthen the standard linearization and greatly improve resolution times for a class of specially structured problems. A broader definition is considered for quadratic reformulations: a quadratization is a quadratic function depending on the original variables and on a set of auxiliary binary variables, such that, when minimized only over the auxiliary variables, the original multilinear polynomial is recovered. We study several properties of quadratizations such as requiring a small number of auxiliary variables. A notable contribution is the definition of a quadratization for monomials with a positive coefficient using only a logarithmic number of variables, which improves previously published bounds by orders of magnitude. This result is especially interesting because every multilinear polynomial can be quadratized by reformulating its monomials separately. We also consider quadratizations of a different nature defined by splitting each monomial into two subterms to be associated with an auxiliary variable each. Defining such quadratizations using the smallest possible number of variables is an NP-hard problem, for which we define heuristic algorithms that identify sets of variables appearing frequently as a subterm of the original monomials, and substituting each set by the same auxiliary variable. Finally, this thesis presents a comparison of the resolution times of several linear and quadratic reformulations, using a commercial solver, over different classes of instances. Experimental results show that reformulations exploiting the structure of the original nonlinear problems, for example by better modeling interactions between monomials, have best resolution times for many instances.

 

 

Martina Fischetti, Technical University of Denmark and Vattenfall 

Mathematical programming models and algorithims for offshore wind park design

 

Wind power is a fast-evolving field that has attracted a lot of attention and investment in recent decades. Its development into a more mature and competitive market is making cost reduction and maximisation of power generation imperative already in the design phase of new wind farms. Lower costs and increased power generation can be achieved through the use of optimisation tools based on mathematical models. We have therefore introduced Operational Research (OR) methods to identify the optimal location of wind turbines in a given site in order to maximise performance and ultimately profits. In this doctoral dissertation, we developed a new wind farm layout optimiser in close cooperation between the Technical University of Denmark and Vattenfall BA Wind, a leader company in the energy business in North Europe. The position of each turbine in a wind farm and the routing and choice of cabling are extremely important and must be optimised to take into account such various factors as water depths, erosion zones, foundation costs, physical obstacles, cable loss and - most importantly - the wake effect, where one turbine casts a "wind shadow" on other turbines. All these factors can now be fully optimised and have a significant impact on the final layout and business case. The algorithms developed during the PhD are now fully deployed in the company and are used to design all Vattenfall’s offshore wind farms. Due to the promising results obtained in the thesis, a new department of Operation Research and advanced modeling was created in Vattenfall. One of the main contributions of the thesis was a mathematical formalization of the problem, and the development of new models in accordance with the practical needs from the company. The very inter-disciplinary design of offshore wind farm has been fully captured using mathematical models, incorporating the expertise of many different groups of practitioners, and tested on real-life data. The design of wind farms proved to be a very challenging optimization task, mainly due to the large size of practical instances, complex constraints and the stochasticity of the wind. The advanced mathematical models and algorithms designed for the problem has been published in 5 high-level OR journals, as well as 3 book chapters, and numerous conference proceedings. The project received a finalist position or first prize in 6 international awards, including the very prestigious Franz Edelman Award.

 

Mathias Sirvent, FAU Erlangen–Nürnberg

Incorporating differential equations into mixed integer programming for gas transport optimization

 

In this thesis, we present new algorithms for mixed-integer programs with incorporated differential equations and show promising numerical results for our application of gas transport optimization.

Natural gas is one of the most important energy sources. In Germany, a politically intended energy turnaround has stirred up the way of power generation in the last decade and the proportion of natural gas rises slightly in that context and gives priority to questions of gas transport.

In particular, Germany does not have relevant gas fields and mainly Russia, the Netherlands, and Norway deliver the commodity. Consequently, gas transportation through pipelines and its mathematical optimization is a highly active field of research of applied optimization. Such optimization problems involve discrete decisions to switch network elements as valves, control valves, or compressor machines. Moreover, the physical behaviour of natural gas is described by the Euler equations, which are a set of hyperbolic partial differential equations. Thus, when dealing with gas transport optimization, mixed-integer problems constrained by differential equations become relevant.

The challenging part emerges from the discrete aspects and from the differential equations. These equations are given as partial differential equations for transient gas transport optimization or as simplified ordinary differential equations for stationary gas transport optimization.

Mixed-integer programs including differential equations are typically solved by remodeling the differential equations to obtain an a-priori mixed-integer nonlinear or linear surrogate model. These remodeling steps are often subject to various simplification steps that are necessary to transform the differential equations into analytical functions. Our first challenge is to omit these simplification steps and develop general algorithms without relying on analytical functions. Moreover, we want to use the algorithms to solve stationary gas transport optimization problems that are constrained by ordinary differential equations. Furthermore, transient gas transport optimization often leads to huge mathematical programs after remodeling. In general, these problems cannot be solved when the size of the networks are of practical size. Our second challenge is to find formulations and corresponding algorithms that are able to tackle transient gas transport optimization problems. Note that the first challenge seeks for general algorithms that are then used for stationary gas transport optimization, whereas the second challenge is tailored to the application of transient gas transport optimization.

Our roadmap to cope with the challenges is inspired by two guidelines. We want to decompose our problems and we want to use mixed-integer linear programs. The simple reason for the first point is that decomposing problems into smaller ones has a successful history and is common sense for solving big problems. Second, mixed-integer linear programs underwent an enormous amount of research in the last decades. Consequently, fast, stable, robust, and reliable solvers as Gurobi, Cplex, or Scip are available and we use these solvers, in our case Gurobi, as a workhorse.

For the first challenge, we consider the case where the constraint functions of the differential equations are not given analytically. In general, a typical solution approach transforms the differential equations to linear constraints. The new global algorithms in this thesis do not rely on this transformation and can work with less information about the underlying differential equation constraints. We build up a new hierarchy of assumptions that restricts the knowledge about the nonlinear functions to a variable extent. Depending on the assumptions, we develop three new global decomposition algorithms that decompose the difficult constraints, i.e., we rely on our first guideline. In an iterative process, mixed-integer linear programs and small nonlinear programs are solved alternately and the correct and finite terminations of the algorithms are proven. Specifically, we build upon relaxation strategies that are motivated by developments in the field of (mixed-integer) (non)linear programming and Lipschitz optimization. As a result, mixed-integer linear programs according to our second guideline are obtained. We prove correct and finite terminations and clarify the limitations of our approaches. Note that the presented framework is a general approach for mixed-integer programs with differential equations. In particular, we consider stationary gas transport optimization and show promising numerical results for the real-world gas network of Greece.

Additionally, we consider the second challenge of transient gas transport optimization. We use an instantaneous control algorithm and adapt it to the Euler equations for the first time. Specifically, we decompose the problem into single time steps and present new discretization techniques that ensure the mixed-integer linear program property for the occurring problems. In other words, we build upon our guidelines again. Finally, we show promising numerical results that illustrate the applicability of the approach.



Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 International License and the GNU Free Documentation License (unversioned, with no invariant sections, front-cover texts, or back-cover texts).

Privacy Policy.

EURO-Online login

 

Sign Up for e-Newsletter

 

EURO Publications