November 8-10, 2015

ROBUST OPTIMIZATION

in applied probability

SUMMARY

The aim of this workshop is to bring together leaders whose expertise spans two areas of research: robust optimization & applied probability.

Robust optimization has emerged as a tractable paradigm for analyzing and optimizing models in which certain system parameters are unknown. Alternatively, applied probability has traditionally been a field yielding insights into how systems behave under uncertainty, when the uncertainty is characterized by known random variables. New modeling and optimization challenges, e.g. those coming from data-rich environments and arising in the domain of machine learning, give rise to questions best addressed by combining insights from both domains of robust optimization and applied probability. The aim of this workshop is to bring together leaders whose expertise spans these areas of research, facilitating the transference of ideas, insights, and methodologies to tackle new and exciting problems at the interface of robust optimization and applied probability.
 

ORGANISERS

CONFIRMED SPEAKERS

PROGRAMME

MONDAY November 9

TUESDAY November 10

***************************************************************************************************************************************

ABSTRACTS

Chaitanya Bandi

Tractable Simulation-Optimization: A Robust Optimization Approach

To understand and optimize the performance of a system under uncertainty, the traditional approach consists of positing a probability distribution over the uncertain parameters, and derive information on the system performance and optimize it. When the system’s dynamics are complex, computing the above expression analytically becomes challenging, and simulation becomes the only resort. However, simulation models may take a considerable amount of time for the results to be statistically significant and can often be complex, making it difficult to understand and further optimize key qualitative insights. Motivated by these challenges, we propose a robust optimization approach to analyzing and optimizing the expected performance of stochastic systems characterized by linear dynamics, based on a robust optimization framework. Our approach consists of the following steps: (1) We model uncertainty via polyhedral sets inspired by the limit laws of probability. The size of these sets is characterized by few variability parameters, which controls the degree of conservatism of the model. (2) We then cast the performance analysis problem as a optimization problem, for instance maximizing a given performance measure subject to the system’s dynamics and the parametric uncertainty sets. The output of this optimization can be thought of as a worst case performance measure function of the variability parameters. (3) Instead of computing the expected performance of the system via averaging simulation outputs, we assume the variability parameters follow limiting distributions (derivatives of the normal distribution for light-tailed systems and the stable distribution for heavy-tailed systems) and average the worst case outputs from the optimization over a discretized space over the variability parameters. (4) To optimize the stochastic system, we propose to cast the problem of finding the optimal design input via a robust optimization problem, e.g., minimizing the average or conditional value-at-risk of the worst case performance outputs. This framework allows a significant reduction in the dimension of uncertainty which provides grounds for tractable analyses. We illustrate the tractability and accuracy of our approach by (a) simulating the transient behavior of multi-server feedforward queueing networks, and (b) determining optimal base stock policies of generalized supply chain networks. This is joint work with Dimitris Bertsimas and Nataly Youssef.

Aharon Ben-Tal

Robust Solutions of Uncertain Optimization Problems under Ambiguous Stochastic Data

We show how robust optimization can provide tractable safe approximations to probabilistic constrains (chance constraints) even under partial information (ambiguity) on the random parameters. In particular we address the case where the only available information is on means and dispersion measures. Unlike previous attempts, using the variance as the dispersion measure, here we derive tight approximations using the MAD (mean absolute deviation). The theory is applied to problems in portfolio selection, inventory control and antenna array design.

Erick Delage

The Value of Distribution Information in Distributionally Robust Optimization

Decisions often need to be made with incomplete knowledge about some parameters of the problem. While formulating a stochastic model that captures accurately this knowledge can be a costly task, solving a distributionally robust optimization model that makes use of historical data can provide useful guidance. Unfortunately, one might worry of being misled by distributionally robust solutions and be tempted to invest in the acquisition of more data before committing to a decision. In this work, we propose tractable methods for bounding the value of additional (or more accurate) distribution information in a two-stage linear program with objective uncertainty.

PRESENTATION

David Goldberg

Distributionally robust inventory control when demand is a martingale

Demand forecasting plays an important role in many inventory control problems. To mitigate the potential harms of model misspecification, various forms of distributionally robust optimization have been applied. Although many of these methodologies suffer from the problem of time-inconsistency, the work of Klabjan et al. established a general time-consistent framework for such problems by connecting to the literature on robust Markov decision processes.
Motivated by the fact that many forecasting models exhibit very special structure, as well as a desire to understand the impact of positing different dependency structures, in this paper we formulate and solve a time-consistent distributionally robust multi-stage newsvendor model which naturally unifies and robustifies several inventory models with demand forecasting. In particular, many simple models of demand forecasting have the feature that demand evolves as a martingale (i.e. expected demand tomorrow equals realized demand today). We consider a robust variant of such models, in which the sequence of future demands may be any martingale with given mean and support. Under such a model, past realizations of demand are naturally incorporated into the structure of the uncertainty set going forwards.
We explicitly compute the minimax optimal policy (and worst-case distribution) in closed form, by combining ideas from convex analysis, probability, and dynamic programming. We prove that at optimality the worst-case demand distribution corresponds to the setting in which inventory may become obsolete at a random time, a scenario of practical interest. To gain further insight, we prove weak convergence (as the time horizon grows large) to a simple and intuitive process. We also compare to the analogous setting in which demand is independent across periods (analyzed previously by Shapiro), and identify interesting differences between these models, in the spirit of the price of correlations studied by Agrawal et al.

Varun Gupta

Online stochastic bin packing

In online bin packing, a sequence of items is revealed one-at-a-time and must be packed in a feasible bin (from a collection of infinite bins). The goal is to minimize the number of bins used at the end of the packing horizon, the usual measure of performance being regret against the offline-optimal packing. In the stochastic version of the problem one further assumes that item sizes are i.i.d. samples from an unknown distribution. We will first propose an algorithm that is the first asymptotically optimal algorithm while being truly distribution oblivious. In addition, we present three flavors of robustness guarantees for non-i.i.d. sequences.

Bernd Heidergott (short talk)

Statistics, Applied Probability and the Human Factor

In the past decades we have witnessed a paradigm-shift from scarcity of data to abundance of data. How to deal with this data-revolution that is driven mainly by computer science and statistics? In my opinion the most challenging question is how to marry data science with the wealth of knowledge on models in applied probability. Rather than discarding analytical models and the analysis thereof, I advocate to build a shell around these models to allow for data dependency in a controlled way. Here, the word ``model'' refers to stochastic models describing a phenomenon such as, for example, the stationary throughput in a queuing system. An instance of a stochastic model is obtained by choosing the actual values of parameters defining the underlying dynamics of the model. Parameter insecurity refers to subjective probabilities (inferred by data) and I will argue that behavioral techniques should be incorporated into the analysis, thus bringing the human decision taker into the picture. For an example from queuing theory I will show how the density of the model outcome under parameter insecurity can be evaluated using the technique of nested derivatives and how this allows to jointly address the epistemological and aleatoric insecurity.

Dick den Hertog

Tutorial on robust optimization

This tutorial will provide you a basic understanding of practical robust optimization. Optimization problems in practice often contain parameters that are uncertain, due to e.g. estimation or rounding. The idea of robust optimization is to find a solution that is immune against these uncertainties. The last two decades efficient methods have been developed to find such robust solutions. The underlying idea is to formulate an uncertainty region for the uncertain parameters, and then require that the constraints should hold for all parameter values in this uncertainty region. It can be shown that e.g. for linear programming, for the most important choices of the uncertainty region, the robust optimization problem can be reformulated as linear programming or conic quadratic programming problems, for which very efficient solvers are available nowadays. In this tutorial we restrict ourselves to linear programming; extensions to nonlinear programming are briefly sketched. We will treat the basics of robust linear optimization, and also show the huge value of robust optimization in (dynamic) multistage problems. Attention will also be given to important modelling issues in robust optimization. We also shortly introduce distributionally robust optimization, since several talks in this workshop deal with this topic. Different applications of (adjustable) robust optimization will be given in the tutorial. Robust optimization has already shown its high practical value in many fields: logistics, engineering, finance, medicine, etc. Some state-of-the-art modelling packages have already implemented robust optimization technology.

Sandeep Juneja (short talk)

Selecting the best population using large deviations and multi-armed bandit methods

Consider the problem of finding a population amongst many with the smallest mean when these means are unknown but population samples can be generated. Typically, by selecting a population with the smallest sample mean, it can be shown that the false selection probability decays at an exponential rate. Lately researchers have sought algorithms that guarantee that this probability is restricted to a small d in order log(1/d) computational time by estimating the associated large deviations rate function via simulation. We show that such guarantees are misleading. Enroute, we identify the large deviations principle followed by the empirically estimated large deviations rate function that may also be of independent interest. Further, we show a negative result that when populations have unbounded support, any policy that asymptotically identifies the correct population with probability at least 1-d for each problem instance requires more than O(log(1/d)) samples in making such a determination in any problem instance. This suggests that some restrictions are essential on populations to devise O(log(1/d)) algorithms with 1-d correctness guarantees. We note that under restriction on population moments, such methods are easily designed. Further, under similar restrictions, sequential methods from multi-armed bandit literature can also be adapted to devise such algorithms.

Nathan Kallus

Robust SAA and the Statistics of DRO

The sample average approximation (SAA) is the standard approach to data-driven optimization. While it enjoys computational tractability and asymptotic convergence guarantees, it is known to produce unstable results and to lack strong, general finite-sample guarantees. We study a robustification of SAA via distributionally robust optimization (DRO) with respect to confidence regions of goodness-of-fit (GoF) tests and explore its computational and statistical properties. We develop theory that intimately links guarantees and convergence of data-driven DRO to newly developed statistical properties of GoF tests. This, along with considerations of computational tractability, guides our choice of tests in formulating DRO depending on the problem case and leads us to develop a novel test for multivariate distributions that, when used in DRO, offers tractable optimization with both finite-sample and asymptotic guarantees. Our theory also allows us to analyze existing data-driven DRO approaches and our statistical testing perspective suggests ways these can be improved in practice via applied statistical tools like the bootstrap. Examples from inventory management and portfolio allocation demonstrate that this approach produces solutions that are stable and perform well even with little data, while at the same time converging as more data becomes available.

Ton de Kok

t.b.a.

Ger Koole

Robust optimization for integrated call center planning

We consider a multi-period staffing problem in a single-shift call center. The call center handles inbound calls, as well as some alternative back-office jobs. The call arrival process is assumed to follow a doubly non-stationary stochastic process with a random mean arrival rate. The inbound calls have to be handled as quickly as possible, while the back-office jobs, such as answering emails, may be delayed to some extent. The staffing problem is modeled as a generalized newsboy-type model under an expected cost criterion. Two different solution approaches are considered. First, by discretization of the underlying probability distribution, we explicitly formulate the expected cost newsboy-type formulation as a stochastic program. Second, we develop a robust programming formulation.

Daniel Kuhn

Data-Driven Distributionally Robust Optimization Using the Wasserstein Metric

We consider stochastic programs where the distribution of the uncertain parameters is only observable through a finite training dataset. Using the Wasserstein metric, we construct a ball in the space of (multivariate and non-discrete) probability distributions centered at the uniform distribution on the training samples, and we seek decisions that perform best in view of the worst-case distribution within this Wasserstein ball. The state-of-the-art methods for solving the resulting distributionally robust optimization problems rely on global optimization techniques, which quickly become computationally excruciating. In this paper we demonstrate that, under mild assumptions, the distributionally robust optimization problems over Wasserstein balls can in fact be reformulated as finite convex programs - in many interesting cases even as tractable linear programs. Leveraging recent measure concentration results, we also show that their solutions enjoy powerful finite-sample performance guarantees. Our theoretical results are exemplified in mean-risk portfolio optimization, uncertainty quantification and machine learning.

Henry Lam (short talk)

t.b.a.

Melvyn Sim

A Practically Efficient Framework for Distributionally Robust Optimization with Recourse

We develop a modular and tractable framework to obtain approximate and possibly exact solutions to a distributionally robust optimization problem with recourse, where we minimize the worst-case expected cost over an ambiguity set of probability distributions. Such a framework has numerous management inspired applications including, among other things, improving healthcare services and reducing inventory costs. In characterizing uncertainty, we adopt the ambiguity set proposed by Wiesemann et al. (2014) and show that by restricting the recourse decision functions to those with affine dependency on the actual and auxiliary random variables, we can improve the solutions of distributionally robust optimization problems with recourse. Using an algebraic modeling package we have developed, we illustrate how our approach can be used to obtain high quality solutions to a class of appointment scheduling problems. This is a joint work with Dimitris Bertsimas and Meilin Zhang.

Gideon Weiss (short talk)

Transient control of queueing networks, using continuous linear programs

Optimal control of a queueing network over a finite time horizon is an intractable task and can only be achieved approximately.  We will survey two approaches:  Controlling the fluid approximation of the network and using a stochastic maximum pressure policy to track the fluid solution (following results of Nazarathy-Weiss), and formulation the problem as a robust optimization problem (following results of Bertsimas-Nasarabaldi-Paschallidis).  In either case this involves a centralized solution of a separated continuous linear program (SCLP).  We will describe that nature of the exact solution of this SCLP, and explain how the nature of the exact solution of the SCLP will help in implementing the optimal control.  This supports using a simplex type algorithm to solve the SCLP (following Weiss and Shindin).

PRESENTATION

Ralf Werner (short talk)

Consistent uncertainty sets and consistent robust estimators

In statistics one is interested in the asymptotical properties of point estimators. From this perspective we provide a fresh look at robust estimators obtained as solutions to robust optimization problems.
For this purpose we introduce the notion of a consistent uncertainty set. We illustrate that - together with continuity of the solution in the problem parameters - this is the right notion to obtain strong consistency of the robust estimator.

 

PRACTICAL INFORMATION

●      Venue

Eurandom, Mathematics and Computer Science Dept, TU Eindhoven,

De Groene Loper 5, 5612 AZ  EINDHOVEN,  The Netherlands

Eurandom is located on the campus of Eindhoven University of Technology, in the Metaforum building (4th floor)

. The university is located at 10 minutes walking distance from Eindhoven main railway station (take the exit north side and walk towards the tall building on the right with the sign TU/e).
Accessibility TU/e campus and map.

●      Registration

Registration is closed.

●      Accommodation

For invited spekaers, we will take care of accommodation. Other attendees will have to make their own arrangements.

We have a preferred hotel, which can be booked at special rates. Please email Patty Koorn for instructions on how to make use of this special offer.

For other hotels around the university, please see: Hotels (please note: prices listed are "best available"). 

More hotel options can be found on the webpages of the Tourist Information Eindhoven, Postbus 7, 5600 AA Eindhoven.

●      Travel

For those arriving by plane, there is a convenient direct train connection between Amsterdam Schiphol airport and Eindhoven. This trip will take about one and a half hour. For more detailed information, please consult the NS travel information pages or see Eurandom web page location.

Many low cost carriers also fly to Eindhoven Airport. There is a bus connection to the Eindhoven central railway station from the airport. (Bus route number 401) For details on departure times consult http://www.9292ov.nl

The University  can be reached easily by car from the highways leading to Eindhoven (for details, see our route descriptions or consult our map with highway connections.

●      Conference facilities : Conference room, Metaforum Building  MF11&12

The meeting-room is equipped with a data projector, an overhead projector, a projection screen and a blackboard. Please note that speakers and participants making an oral presentation are kindly requested to bring their own laptop or their presentation on a memory stick.

●      Conference Secretariat

Upon arrival, participants should register with the workshop officer, and collect their name badges. The workshop officer will be present for the duration of the conference, taking care of the administrative aspects and the day-to-day running of the conference: registration, issuing certificates and receipts, etc.

●      Cancellation

Should you need to cancel your participation, please contact Patty Koorn, the Workshop Officer.

●      Contact

Mrs. Patty Koorn, Workshop Officer, Eurandom/TU Eindhoven, koorn@eurandom.tue.nl

SPONSORS

The organisers acknowledge the financial support/sponsorship of:

Last updated 12-11-15,
by PK

 P.O. Box 513, 5600 MB Eindhoven, The Netherlands
tel. +31 40 2478100  
  e-mail: info@eurandom.tue.nl