Season 2: Sep 2023 - Dec 2023

Given a nominal combinatorial optimization problem, we

consider a robust two-stages variant with polyhedral cost uncertainty,

called DDID. In the first stage, DDID selects a subset of uncertain cost

coefficients to be observed, and in the second-stage, DDID selects a

solution to the nominal problem, where the remaining cost coefficients

are still uncertain. Given a compact linear programming formulation for

the nominal problem, we provide a mixed-integer linear programming

(MILP) formulation for DDID. The MILP is compact if the number of

constraints describing the uncertainty polytope other than lower and

upper bounds is constant. In that case, the formulation leads to

polynomial-time algorithms for DDID when the number of possible

observations is polynomially bounded. We extend this formulation to more

general nominal problems through column generation and constraint

generation algorithms. We illustrate our reformulations and algorithms

numerically on the selection problem, the orienteering problem, and the

spanning tree problem.

Link to paper: https://hal.science/hal-04097679/ 

Michael Poss is a senior research fellow at the CNRS, in the LIRMM laboratory. His current research focuses mainly on robust combinatorial optimization. He his the founding managing editor of the Open Journal of Mathematical Optimization (https://ojmo.centre-mersenne.org/).

In this work, we consider two-stage quadratic optimization problems under ellipsoidal uncertainty. In the first stage, one needs to decide upon the values of a subset of optimization variables (control variables). In the second stage, the uncertainty is revealed, and the rest of optimization variables (state variables) are set up as a solution to a known system of possibly non-linear equations. This type of problem occurs, for instance, in optimization for dynamical systems, such as electric power systems as well as gas and water networks. We propose a convergent iterative algorithm to build a sequence of approximately robustly feasible solutions. At each iteration, the algorithm optimizes over a subset of the feasible set and uses affine approximations of the second-stage equations while preserving the non-linearity of other constraints. We implement our approach for AC Optimal Power Flow and demonstrate the performance of our proposed method on Matpower instances. This work focuses on quadratic problems, but the approach is suitable for more general setups.

This topic is based on the following working paper: https://arxiv.org/abs/2104.03107. This is joint work with Bissan Ghaddar from Ivery Business School and Daniel Molzahn from Georgia Tech.

Olga is an assistant professor of optimization at the Econometric Institute of Erasmus University Rotterdam. She develops solution approaches and approximation algorithms for non-linear optimization problems using convex programming. Typical applications for her research are network-based problems, such as optimization of energy, water, and transport systems.  

Robust optimization has become an indispensable tool in tackling uncertainties in optimization. The budgeted uncertainty set introduced by Bertsimas and Sim (2004) is a prevalent approach in this field due to its effectiveness in addressing a host of practical linear optimization problems under uncertainty, though challenges remain in multi-period decision models. In this work, we revisit this approach with a distinct angle: bypassing traditional support boundaries and introducing a robust satisficing model where preferences are conveyed through targets. At the core of our discussion is the cardinal fragility criterion, which evaluates a solution’s vulnerability to input deviations in reaching a target. Our analysis employs a prediction disparity metric rooted in the L1-norm, echoing Bertsimas and Sim (2004), but diverges with its boundary-free support. This fragility construct seamlessly integrates into a multi-attribute robust satisficing model, prioritizing alignment with predetermined attribute targets. By eliminating support constraints, we extend the boundaries of our computational reach. Our approach proficiently handles multiperiod models by employing direct and straightforward formulations, without introducing dual variables or resorting to approximations. Additionally, we present a method to optimize the parameters of the prediction disparity metric using prediction residuals, ensuring the desired confidence profile across various target attainment levels. We conducted two studies: one focusing on portfolio optimization, and the other using simulation to explore if heightened crashing costs can enhance the likelihood of on-time project completion.

Dr. Melvyn Sim is Professor and Provost's Chair at the Department of Analytics & Operations, NUS Business school. His research interests fall broadly under the categories of decision making and optimization under uncertainty with applications ranging from finance, supply chain management, healthcare to engineered systems. He is one of the active proponents of Robust Optimization and Satisficing, and has given keynote seminars at international conferences.  Dr. Sim is currently serving as a Department Editor of MSOM, and as an associate editor for Operations Research, Management Science and INFORMS Journal on Optimization.

Robust optimization is a prominent approach in optimization to deal

with uncertainties in the data of the optimization problem by hedging

against the worst-case realization of the uncertain event. Doing this

usually leads to a multilevel structure of the mathematical

formulation that is very similar to what we are used to consider in

bilevel optimization. Hence, these two fields are closely related

but the study of their combination is still in its infancy.

In this talk, 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).

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.

Short CV

Since 1/2019: Full professor (W3) for “Nonlinear Optimization” at Trier University

4/2014-9/2018: Junior professor (W1) for “Optimization of Energy Systems” at the Friedrich-Alexander-Universität Erlangen-Nürnberg

1/2013: PhD in mathematics at the Leibniz Universität Hannover

10/2008: Diplom in mathematics (minor computer science) at the Leibniz Universität Hannover

Editorial Work

 Since June 2022: Editorial Board member of the Journal of Optimization Theory and Applications

Since May 2022: Editorial Board member of Optimization Letters

Since 2021: Associate Editor of OR Spectrum

 Since 2021: Associate Editor of the EURO Journal on Computational Optimization

Since 2011: Technical Editor of Mathematical Programming Computation 

Awards

Optimization Letters best paper award for the year 2021 

Marguerite Frank Award for the best EJCO paper in 2021

MMOR Best Paper Award 2021

1st price (category: scientific) of the ROADEF/EURO Challenge 2020

Howard Rosenbrock Prize 2020

EURO Excellence in Practice Award 2016

We propose a new global optimization approach for solving nonconvex optimization problems in which the nonconvex components are sums of products of convex functions. A broad class of nonconvex problems can be written in this way, such as concave minimization problems, difference of convex problems, and fractional optimization problems. Our approach exploits two techniques: first, we introduce a new technique, called the Reformulation-Perspectification Technique (RPT), to obtain a convex approximation of the considered nonconvex continuous optimization problem. Next, we develop a spatial Branch and Bound scheme, leveraging RPT, to obtain a global optimal solution. Numerical experiments on four different convex maximization problems, a quadratic constrained quadratic optimization problem, and a dike height optimization problem demonstrate the effectiveness of the proposed approach. In particular, our approach solves more instances to global optimality for the considered problems than BARON and SCIP. Moreover, for problem instances of larger dimension our approach outperforms both BARON and SCIP on computation time for most problem instances, while for smaller dimension BARON overall performs better on computation time.  Finding the worst-case scenario in Robust Optimization is often a nonconvex optimization problem. We therefore discuss how this novel algorithm can be used to solve robust and adaptive nonlinear optimization problems.