Archive

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.

The facility location problem is a well-known and extensively studied problem in the field of Operations Research, attracting significant attention from researchers and practitioners. In this talk, we specifically address robust facility location problems, which provide a valuable approach to tackle the complexities arising from uncertain demand. We consider a two-stage robust facility location problem on a metric under uncertain demand. The decision-maker needs to decide on the (integral) units of supply for each facility in the first stage to satisfy an uncertain second-stage demand, such that the sum of the first-stage supply cost and the worst-case cost of satisfying the second-stage demand over all scenarios is minimized. The second-stage decisions are only assignment decisions without the possibility of adding recourse supply capacity. This makes our model different from existing work on two-stage robust facility location and set covering problems. We consider an implicit model of uncertainty with an exponential number of demand scenarios specified by an upper bound k on the number of second-stage clients. In an optimal solution, the second-stage assignment decisions depend on the scenario; surprisingly, we show that restricting to a fixed (static) fractional assignment for each potential client irrespective of the scenario gives us an O(log k/log log k)-approximation for the problem. Moreover, the best such static assignment can be computed efficiently, giving us the desired guarantee. Our proposed static assignment policies showcase their effectiveness in achieving strong approximate solutions both theoretically and numerically. Moreover, these policies offer a promising approach to address uncertain demand in diverse facility location scenarios. This is joint work with Vineet Goyal and David Shmoys.

Omar El Housni is an assistant professor at Cornell Tech and in the School of Operations Research and Information Engineering at Cornell University. He is also a Field Member of the Center of Applied Mathematics at Cornell. Omar received a PhD in Operations Research from Columbia University and a BS and MS in Applied Mathematics from Ecole Polytechnique In Paris.  Omar’s research focuses on the design of robust and efficient algorithms for sequential dynamic optimization problems under uncertainty with applications in revenue management, assortment optimization, facility location problems and online matching markets.

Contextual Bandits and more generally, contextual reinforcement learning, studies the problem where the learner relies on revealed contexts, or labels, to adapt learning and optimization strategies. What can we do when those contexts are missing? 

Statistical learning with missing or hidden information is ubiquitous in many theoretical and applied problems. A basic yet fundamental setting is that of mixtures, where each data point is generated by one of several possible (unknown) processes. In this talk, we are interested in the dynamic decision-making version of this problem. At the beginning of each (finite length, typically short) episode, we interact with an MDP drawn from a set of M possible MDPs. The identity of the MDP for each episode -- the context -- is unknown.

We review the basic setting of MDPs and Reinforcement Learning, and explain in that framework why this class of problems is both important and challenging. Then, we outline several of our recent results in this area, as time permits. We first show that without additional assumptions, the problem is statistically hard in the number of different Markov chains: finding an epsilon-optimal policy requires exponentially (in M) many episodes. We then study several special and natural classes of LMDPs. We show how ideas from the method-of-moments, in addition to the principle of optimism, can be applied here to derive new, sample efficient RL algorithms in the presence of latent contexts.

Constantine Caramanis is a Professor in the ECE department of The University of Texas at Austin. He received a PhD in EECS from The Massachusetts Institute of Technology, in the Laboratory for Information and Decision Systems (LIDS), and an AB in Mathematics from Harvard University. His current research interests focus on decision-making in large-scale complex systems, with a focus on statistical learning and optimization.

In many applications, determining optimized solutions that are hedged against uncertainties is mandatory. Classical stochastic optimization approaches, however, may be prone to the disadvantage that the underlying probability distributions are unknown or uncertain themselves. On the other hand, standard robust optimization may lead to conservative results as it generates solutions that are feasible regardless of how uncertainties manifest themselves within predefined uncertainty sets. Distributional robustness (DRO) lies at the interface of robust and stochastic optimization as it robustly protects against uncertain distributions. DRO currently receives increased attention and is considered as an alternative that can lead to less conservative but still uncertainty-protected solutions. In this talk, we will review some approaches in the area of distributional robustness. We will explain some recent developments that use scenario observations to learn more about the uncertain distributions over time, together with best possible protected solutions. The goal is to incorporate new information when it arrives and to improve our solution without resolving the entire robust counterpart. We also present computational results showing that our approach based on online learning leads to a practically efficient solution algorithm for DRO over time. This is joint with K. Aigner, A. Bärmann, K. Braun, F. Liers, S. Pokutta, O. Schneider, K. Sharma, and S. Tschuppik (INFORMS Journal on Optimimization (2023)).

Frauke studied mathematics at the University of Cologne and obtained her doctoral degree in computer science in 2004. After research stays in Rome and in Paris, she headed a DFG-funded Emmy Noether Junior Research Group in Cologne. In 2010, she obtained her Habilitation and became professor in Applied Mathematics in the Department of Mathematics at the Friedrich-Alexander Universität Erlangen-Nürnberg in 2012. Her research is in optimization under uncertainty, including combinatorial, mixed-integer and nonlinear aspects. Integrating knowledge from data analysis is of high interest. She has coordinated the European Graduate College MINOA (Marie-Curie ITN, 2018-2021) and is Principal Investigator in the Collaborative Reseach Centers CRC 1411 and CRC/TRR 154. Since 04/2023, she is spokesperson of the CTC/TRR 154.

Robust optimization typically follows a worst-case perspective, where a single scenario may determine the objective value of a given solution. Accordingly, it is a challenging task to reduce the size of an uncertainty set without changing the resulting objective value too much. On the other hand, robust optimization problems with many scenarios tend to be hard to solve, in particular for two-stage problems. Hence, a reduced uncertainty set may be central to find solutions in reasonable time. We propose scenario reduction methods that give guarantees on the performance of the resulting robust solution. Scenario reduction problems for one- and two-stage robust optimization are framed as optimization problems that only depend on the uncertainty set and not on the underlying decision making problem. Experimental results indicate that objective values for the reduced uncertainty sets are closely correlated to original objective values, resulting in better solutions than when using general-purpose clustering methods such as K-means.

Authors: Marc Goerigk and Mohammad Khosravi

Marc Goerigk is Professor for Business Decisions and Data Science at the University of Passau. His research focuses mainly on robust decision making for  combinatorial problems, in particular regarding aspects of complexity and making the best use of data. Marc holds a PhD in mathematics from the University of Göttingen. Before joining his colleagues in Passau, he was Professor at the University of Siegen, lecturer at Lancaster University and post-doctoral researcher at the University of Kaiserslautern.

We consider the problem of learning classification trees that are robust to distribution shifts between training and testing/deployment data. This problem arises frequently in high stakes settings such as public health and social work where data is often collected using self-reported surveys which are highly sensitive to e.g., the framing of the questions, the time when and place where the survey is conducted, and the level of comfort the interviewee has in sharing information with the interviewer. We propose a method for learning optimal robust classification trees based on mixed-integer robust optimization technology. In particular, we demonstrate that the problem of learning an optimal robust tree can be cast as a single-stage mixed-integer robust optimization problem with a highly nonlinear and discontinuous objective. We reformulate this problem equivalently as a two-stage linear robust optimization problem for which we devise a tailored solution procedure based on constraint generation. We evaluate the performance of our approach on numerous publicly available datasets, and compare the performance to a regularized, non-robust optimal tree. We show an increase of up to 14.16% in worst-case accuracy and of up to 4.72% in average-case accuracy across several datasets and distribution shifts from using our robust solution in comparison to the non-robust one.

Phebe Vayanos is an Associate Professor of Industrial & Systems Engineering and Computer Science at the University of Southern California. She is also an Associate Director of CAIS, the Center for Artificial Intelligence in Society at USC. Her research is focused on Operations Research and Artificial Intelligence and in particular on optimization and machine learning. Her work is motivated by problems that are important for social good, such as those arising in public housing allocation, public health, and biodiversity conservation. Prior to joining USC, she was lecturer in the Operations Research and Statistics Group at the MIT Sloan School of Management, and a postdoctoral research associate in the Operations Research Center at MIT. She holds a PhD degree in Operations Research and an MEng degree in Electrical & Electronic Engineering, both from Imperial College London. She is a recipient of the NSF CAREER award and the INFORMS Diversity, Equity, and Inclusion Ambassador Program Award. 

In this talk an algorithm for maximizing a convex function over a convex feasible set (a common problem in Robust Analysis) is proposed. The algorithm consists of two phases: in phase 1 a feasible starting point is obtained that is used in a Gradient Descent algorithm in phase 2. The main contribution of the paper is connected to phase 1; five different methods are used to approximate the original NP-hard problem of maximizing a convex function (MCF) by a tractable convex optimization problem. All the methods use the minimizer of the convex objective function in their construction. The performance of the overall algorithm is tested on a wide variety of MCF problems, demonstrating its efficiency.

Aharon Ben-Tal is a Professor of Operations Research at the Technion – Israel Institute of Technology.  He received his Ph.D. in Applied Mathematics from Northwestern University in 1973.  He has been a Visiting Professor at the University of Michigan, University of Copenhagen, Delft University of Technology, MIT and CWI Amsterdam, Columbia and NYU.  His interests are in Continuous Optimization, particularly nonsmooth and large-scale problems, conic and robust optimization, as well as convex and nonsmooth analysis. In recent years the focus of his research is on optimization problems affected by uncertainty; he is one if the founders of the Robust Optimization methodology to address these problems. In the last 20 years he has devoted much effort to engineering applications of optimization methodology and computational schemes. Some of the algorithms developed in the MINERVA Optimization Center are in use by Industry (Medical Imaging, Aerospace). He has published more than 135 papers in professional journals and co-authored three books.   Prof. Ben-Tal was Dean of the Faculty of Industrial Engineering and Management at the Technion (1989-1992) and (2011-2014). He served in the editorial board of all major OR/Optimization journals. He gave numerous plenary and keynote lectures in international conferences.

In 2007 Professor Ben-Tal was awarded the EURO Gold Medal - the highest distinction of Operations Research within Europe.

In 2009 he was named Fellow of INFORMS.

In 2015 he was named Fellow of SIAM.

In 2016 he was awarded by INFORMS the Khachiyan Prize for Lifetime Achievement in the area of Optimization.

In 2017, the Operation Research Society of Israel (ORSIS) awarded him the Lifetime Achievement Prize.

As of February 2023 his work has over 33,000 citations (Google scholar).

Classical approaches in robust optimization (RO) involve out-of-the-box uncertainty sets such as norm, budget or polyhedral sets. Apart from leveraging available data to cross-validate hyperparameters, out-of-the-box uncertainty sets seldom incorporate distributional information, so they inherently do not capture the real-world behavior of uncertain parameters.

Distributionally Robust Optimization (DRO), by contrast, satisfies constraints in expectation among a class of underlying distributions.  We propose a new type of uncertainty set motivated by information theory, which incorporates the probability distributions directly. Initial computational tests with our approach yield reductions in the maximum and mean violation as compared to classical RO and DRO. We apply this novel uncertainty set in a real-world setting of the Hartford Hospital's Bone and Joint Institute to optimize the patient census while considering the uncertainty in the rest times of patients after surgery. We generate a timetable for surgeons that reduces the monthly census by up to 10%, outperforming both out-of-the-box uncertainty sets and DRO. (Joint work with Benjamin Boucher, MIT).

Dimitris Bertsimas is the Boeing Professor of Operations Research and the Associate Dean of Business Analytics at the Massachusetts Institute of Technology. He is a member of the US National Academy of Engineering, an INFORMS fellow, recipient of the John von Neumann Theory Prize, the Frederick W. Lanchester Prize, the Erlang Prize, finalist of the Franz Edelman Prize four times, and the INFORMS President’s Award, among many other research and teaching awards, supervisor of 88 completed and 25 current doctoral theses, editor of the INFORMS Journal on Optimization, co-author of seven textbooks and co-founder of ten analytics companies and two foundations. 

When a firm selects an assortment of products to offer to customers, it uses a choice model to anticipate their probability of purchasing each product. In practice, the estimation of these models is subject to statistical errors, which may lead to significantly suboptimal assortment decisions. Recent work has addressed this issue using robust optimization, where the true parameter values are assumed unknown and the firm chooses an assortment that maximizes its worst-case expected revenues over an uncertainty set of likely parameter values, thus mitigating estimation errors. In this talk, we introduce the concept of randomization into the robust assortment optimization literature. We show that the standard approach of deterministically selecting a single assortment to offer is not always optimal in the robust assortment optimization problem. Instead, the firm can improve its worst-case expected revenues by selecting an assortment randomly according to a prudently designed probability distribution. We demonstrate this potential benefit of randomization both theoretically in an abstract problem formulation as well as empirically across three popular choice models: the multinomial logit model, the Markov chain model, and the preference ranking model. We show how an optimal randomization strategy can be determined exactly and heuristically. Besides the superior in-sample performance of randomized assortments, we demonstrate improved out-of-sample performance in a data- driven setting that combines estimation with optimization. Our results suggest that more general versions of the assortment optimization problem—incorporating business constraints, more flexible choice models and/or more general uncertainty sets—tend to be more receptive to the benefits of randomization.

Wolfram Wiesemann is Professor of Analytics & Operations as well as the head of the Analytics, Marketing & Operations department at Imperial College Business School. His research interests evolve around decision-making under uncertainty, with applications to supply chain management, healthcare and energy. Wolfram is an elected member of the boards of the Mathematical Optimization Society and the Stochastic Programming Society, and he serves as an area editor for Operations Research Letters as well as an associate editor for Mathematical Programming, Operations Research, Manufacturing & Service Operations Management and SIAM Journal on Optimization.