EURO Doctoral Dissertation Award 2022 - Finalists

The four finalists of the 2022 EURO Doctoral Dissertation Award are:

 

Picture: Jérôme De Boeck, Daniel Rehfeldt, Yves Crama (Chair), Johannes Thürauf and Michael Kahr

 

 

Jérôme De Boeck, Université de Fribourg/Université libre de Bruxelles

From vertical to horizontal structures: New optimization challenges in electricity markets

 

The use of electricity in our society has dramatically evolved over the past decades as well as the way we address problems related to the electricity supply chain. The electricity supply chain consists of several components: production, trading, distribution, and consumption. From a general perspective, the electricity supply chain is shifting from a vertical to a horizontal structure due to new decision mechanisms. This thesis studies several evolving problems in the electricity supply chain.

The first two problems studied are Bidding Problems (BPs) related to the introduction of Deregulated Electricity Markets (DEM). Such markets have been introduced to avoid dominant positions from producers and decrease the price of electricity as much as possible for the end consumer. Nevertheless, electricity producers face increasing uncertainty in such markets, having to plan the electricity production before knowing if it will be sold and without knowing the selling price. Bidding Problems (BPs) in DEM from the perspective of a GC have been widely studied with very strong hypotheses. They are most often formulated as bilevel optimization problems with the bidding GC as leader and the market operator of the DEM as follower. Only small instances our solved with state-of-the-art methods.

The first BP studied considers the Price Coupling of Regions (PCR) introduced in Europe consisting of coupling several DEM. A bilevel formulation that integrates transmission constraints between markets is proposed. KKT conditions are used to reformulate the problem into a non-linear single level formulation. A discretization of optimal bidding prices considering PCR is presented leading to a MILP formulation. New valid inequalities are proposed reducing significantly the LP gap of previous formulations. Two heuristic methods are proposed as well, including a general method for MILPs containing Special Ordered Sets of type 1. Numerical results focus on illustrating the highly negative impact of simplifying market mechanisms of BPs as done in price-taker formulations or ignoring transmission constraints in PCR.

The second BP considered uncertainty over competitor bids (SBP). We prove the problem to be NP-hard and introduce a novel dynamic programming (DP) framework for SBP. This framework is adapted to solve SBP for fixed bidding quantities. Instances of considerably larger size than in previous studies are solved to optimality in comparison to state-of-the-art methods. Furthermore, a DP polynomial algorithm is proposed which computes an upper bound on the SBP considered. A heuristic method is proposed as well, providing solutions under 1% of optimality in numerical experiments.

A third problem considers trading electricity with Micro-Grids (MGs). MGs are composed of several households which are partially autonomous regarding their electricity production. A Contract Proposition Problem is studied in which a GC must propose contracts to MGs which will select the contract at their best advantage. This problem is formulated as a bilevel optimization problem containing binary variables at the second level, formulations for which no general reformulation technique exists. We propose a novel heuristic reformulation technique lifting the classical optimistic assumption of bilevel formulations and providing a single level formulation. Numerical results illustrate our method provides near-optimal results.

The last problem studied in this thesis is the Minimum Margin Problem (MMP) consisting of assigning electricity consumers to power generators in a local transmission network. The goal is to maximize the minimum margin of the generators to prevent blackout situations. A hop constraint is considered to limit the number of edges between customers and their generators. We model this problem on layered graphs and introduce novel preprocessing techniques for layered graphs reducing their size by 50%. Our model solves instances of considerably larger size than state-of-the-art methods.

 

Daniel Rehfeldt, Zuse Insitute Berlin

Faster algorithms for Steiner tree and related problems: From theory to practice

 

The Steiner tree problem in graphs (SPG) is one of the most studied problems in combinatorial optimization. Many applications can be modeled as SPG or closely related problems. In the last decade, the SPG has seen impressive theoretical advancements. However, the state of the art in (practical) exact SPG solution, set in a series of milestone papers by Polzin and Vahdati Daneshmand, has remained largely unchallenged for almost 20 years. While the DIMACS Challenge 2014 and the PACE Challenge 2018 brought renewed interest in the exact solution of SPGs, even the best new solvers fall far short of reaching the longtime state of the art.

This thesis seeks to advance exact SPG solution once again. Since many practical applications are modeled not as pure SPGs, but rather as closely related problems, we also aim to combine SPG advancements with improvements in the exact solution of such related problems. Initially, we establish a broad theoretical basis to guide the subsequent algorithmic developments. We provide various new theoretical results for SPG and well-known relatives, such as the maximum-weight connected subgraph problem. These results include the strength of linear programming relaxations, polyhedral descriptions, and complexity results. Next, we introduce many new algorithmic components such as reduction techniques, cutting planes, graph transformations, and heuristics—both for SPG and related problems. Many of these methods and techniques are provably stronger than previous results from the literature. For example, we introduce a new reduction concept that is strictly stronger than the well-known and widely used bottleneck Steiner distance.

The individual components are combined in an exact branch-and-cut algorithm. Notably, all problem classes can be handled by a single branch- and-cut kernel. As a result, we obtain an exact solver for SPG and 14 related problems. The new solver is on each of the 15 problem classes faster than all other solvers from the literature (including problem- specific ones), often by orders of magnitude. In particular, the new solver outperforms the long-reigning, but non-public, state-of-the-art SPG solver by Polzin and Vahdati Daneshmand. Even geometric Steiner tree problems can be solved much faster than previously possible when the new solver is combined with the full Steiner tree generation provided by the software GeoSteiner. Finally, with our new solver, many benchmark instances from the literature for several problem classes can be solved for the first time to optimality—some containing millions of edges. These problem classes include the SPG, the prize-collecting Steiner tree problem, and the maximum-weight connected subgraph problem. Even several Euclidean Steiner tree problems from the 11th DIMACS Challenge that could previously not be solved after one week of computation by the leading geometric Steiner tree solver GeoSteiner can now be solved for the first time—within three minutes.

The software developed for this thesis, named SCIP-Jack, has been made freely available with source code for academic use (https://scipjack.zib.de/). Already a previous and significantly slower version of SCIP-Jack obtained top rankings in all tracks of the PACE Challenge 2018. Finally, SCIP-Jack is heavily used in several industrial projects, for example, at Open Grid Europe, one of Europe's largest transmission systems operators. Keywords

 

Johannes Thürauf, Trier University

Feasibility for Maximal Uncertainty Sets in Robust Optimization with Application to Gas Networks

Robust optimization is a popular approach to protect an optimization problem against uncertain data within a user-specified set of scenarios, the so-called uncertainty set. In many cases, the choice of the uncertainty set is driven by the application. In general, it can be elusive to assume that the exact “size” of the uncertainty set can be specified prior to the optimization process. Overly large sized uncertainty sets can lead to infeasible robust optimization problems. To avoid robust infeasibility due to the choice of the uncertainty set, it is useful to know the maximal “size” of a given uncertainty set such that feasibility of the robust optimization problem is still guaranteed. We study maximal uncertainty sets that guarantee robust feasibility for general mixed-integer linear problems (MIPs) and in the context of gas networks in this cumulative dissertation.

For general MIPs, we consider a specific notion for the maximal size of a given uncertainty set: the radius of robust feasibility (RRF). We introduce and study the RRF for MIPs under common assumptions from the literature and then extend the RRF to include “safe” variables and constraint, i.e., variables and constraints that are not affected by uncertainties. We further develop methods for computing the RRF of linear and mixed-integer linear problems with safe variables and constraints and successfully apply them to instances of the MIPLIB 2017 library. Based on our results, we propose a framework to integrate choosing the size of a given uncertainty set in the optimization process, which provides decision makers with a new tool to avoid too conservative robust solutions, i.e., to control the price of robustness, by adjusting the size of the uncertainty set.

Moreover, we study the two-stage robust problems of deciding the feasibility of a booking as well as of computing maximal technical capacities within the European entry-exit gas market system. A booking is a capacity-right contract for which the transmission system operator has to guarantee that every balanced load flow below the booking can be transported through the network. Maximal technical capacities bound these bookings and, thus, describe maximal bookable capacities. Except for some technical subtleties, these robust problems lead to deciding the feasibility as well as solving a specific two-stage robust nonlinear optimization problem. The main goal of this problem consists of computing a maximal uncertainty set of balanced load flows so that each of these load flows can be transported through the network. We study this problem algorithmically with focus on nonlinear models of gas transport. For deciding the feasibility of a booking, we develop a polynomial-time algorithm for single-cycle networks consisting of pipes. We further prove that deciding the feasibility of a booking is coNP-hard in general pipe-only networks. For active networks including compressors and control valves, we develop a bilevel model to decide the feasibility of bookings, in which the lower level is nonlinear and nonconvex. Under the assumption that no compressor or valve is part of a cycle, we derive several single-level reformulations of this problem.

Based on the results for bookings, we provide results for computing maximal technical capacities in tree-shaped networks. These results enable us to solve a multilevel model of the European entry-exit gas market system from the literature for tree-shaped networks and a nonlinear flow model. This is the first time that the considered market model has been solved for a real-world sized passive network and a nonlinear gas flow model.

Finally, we note that the results for bookings and technical capacities can also contribute to other potential-based network problems, which we demonstrate by computing a robust diameter selection for tree-shaped hydrogen networks with demand uncertainties.

 

Michael Kahr, University of Vienna

Mathematical optimization for social network analysis: Influence maximization and community detection

 

Online social networks have become crucial communication channels recently. Millions of people participate in such networks including entities with commercial interests such as companies. The latter increasingly incorporate campaigns promoted via social networks into their marketing mix. Fundamental problems that arise in quantitative social network analysis in the context of (viral) marketing include (i) the identification of influential network nodes that may trigger a large information propagation cascade referred to as influence propagation, and (ii) the identification of homogeneous communities referred to as community detection. In this thesis, we address the aforementioned problems that are naturally subject to uncertainty regarding the input data. Reasons include that the strength of social ties and the homogeneity of individuals can only be roughly quantified by empirical observations. In particular we study three problems from the domain of influence propagation and one community detection problem. The focus is on the development of solution algorithms that allow to obtain optimal solutions or at least worst-case gaps to optimal solutions with methods from mathematical optimization. We thereby contrast with the majority of the related literature in which heuristic methods are used. The proposed algorithms employ techniques from mixed integer (non-)linear programming including column generation and (generalized) Benders decomposition that are both embedded into a branch-and-cut framework. We also employ a Frank-Wolfe type solution algorithm for solving quadratic programs. Most of the proposed algorithms are accompanied by heuristics. The performance of the proposed algorithms is evaluated in extensive computational experiments on artificial and on real-world social network graphs from the literature as well as on new instances that we obtained via the developer interface of Twitter. Besides, several managerial insights are derived. The aforementioned uncertain input data is tackled with methods from stochastic optimization and robust optimization. Particularly regarding the latter domain, we propose and formally study a robust version of the standard quadratic problem that we use for a seemingly novel application, namely, community detection. Here, an uncertain (possibly indefinite) quadratic form is maximized over the unit simplex. We show that the copositive relaxation gap is equal to the minimax gap under some mild conditions on the curvature of uncertainty sets that are widely used in the related literature. We further derive conditions under which the robust version of the problem reduces to a traditional standard quadratic problem. Finally, concluding remarks are given including future research avenues.



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