SPS Past Prize Winners

Celebrating excellence in Stochastic Programming—discover the past prize events that recognized outstanding contributions and achievements in the field.

2016: COSP Student Paper Prize Awards

First Prize: Algo Carè (University of Brescia)
Scenario Min-Max Optimization and the Risk of Empirical Costs, SIAM Journal on Optimization, 25(4):2061-2080, 2015.

Advisors: S. Garatti and M. C. Campi

Abstract: Many decision problems can be formulated as the problem of minimising a convex cost function that also depends on an uncertain variable. In this talk, we take a data-based worst-case approach to deal with uncertainty, and we minimise the maximum of the cost functions corresponding to some previously observed instances of the uncertain variable. We call these instances scenarios, and the solution to this optimisation problem is the scenario solution. The empirical costs are defined as the cost values that the scenario solution incurs for the various scenarios that have been used in optimisation. The risk of an empirical cost is defined as the probability that the empirical cost will be exceeded “tomorrow”, i.e., when a new instance of the uncertain variable will be experienced. In this work it is proven that the vector of the risks of the empirical costs has an ordered Dirichlet distribution independently of the distribution of the uncertainty. By virtue of this result, one can construct a probability box for the distribution of tomorrow’s cost, without making any assumption on the specific distribution of the uncertainty and without resorting to new observations.

Runner-up (in alphabetical order):

Tsvetan Asamov (Rutgers University)
Time-consistent approximations of risk-averse multistage stochastic optimization problems, Mathematical Programming, 153(2):459–493, 2015.

Advisor: Andrzej Ruszczyński

Abstract: In this paper we study the concept of time consistency as it relates to multi-stage risk-averse stochastic optimization problems on finite scenario trees. We use dynamic time-consistent formulations to approximate problems having a single coherent risk measure applied to the aggregated costs over all time periods. The dual representation of coherent risk measures is used to create a time-consistent cutting plane algorithm. Additionally, we also develop methods for the construction of universal time-consistent upper bounds. The performance of the proposed techniques is tested using monthly return data for the components of the Dow Jones Industrial Average. Our numerical results indicate that the resulting dynamic formulations yield close approximations to the original problem.

Runner-up (in alphabetical order):

Ward Romeijnders (University of Groningen)
A Convex Approximation for Two-Stage Mixed-Integer Recourse Models with a Uniform Error Bound, SIAM Journal on Optimization, 26(1):426–447, 2016.

Advisors: M.H. van der Vlerk and W.K. Klein Haneveld

Abstract: We develop a convex approximation for two-stage mixed-integer recourse models and we derive an error bound for this approximation that depends on the total variations of the probability density functions of the random variables in the model. We show that the error bound converges to zero if all these total variations converge to zero. Our convex approximation is a generalization of the one in Romeijnders et al. ("Total variation bounds on the expectation of periodic functions with applications to recourse approximations", Mathematical Programming, (2014), DOI: 10.1007/s10107-014-0829-2.) restricted to totally unimodular integer recourse models. For this special case it has the best worst-case error bound possible. As main building blocks in the derivation of the error bound we generalize the asymptotic periodicity results of Gomory ("Some polyhedra related to combinatorial problems", Linear Algebra and Its Applications, 2 (1969), pp. 451–558.) for pure integer programs to the mixed-integer case, and we use new total variation error bounds on the expectation of periodic functions.

Prize Committee: Nilay Noyan (chair), Andy Philpott, and Suvrajeet Sen