Frans de Ruiter has been selected as the recipient of the 2017 INFORMS Optimization Society Student Paper Prize for his paper “Duality in Two-Stage Adaptive Linear Optimization: Faster Computation and Stronger Bounds,” INFORMS Journal on Computing 28(3) 500–511, 2016, co-authored with Dimitris Bertsimas.
This paper considers a two-stage adaptive robust optimization problem with linear constraints and objectives and the uncertainty modeled using a polyhedral uncertainty set. This is an important problem that arises in many applications including unit-commitment, supply chain design, facility location and capacity planning. The paper considers an equivalent dual formulation for the problem which turns out to be another two-stage adaptive robust optimization problem with a duality between the constraints of the problem and the constraints defining the uncertainty set. A key contribution of this paper is to prove an equivalence between the affine policy approximations of the primal and dual problems. Affine policies have been widely considered as an approximation for the two-stage problem that is intractable in general. The results in this paper allows to compute an optimal affine policy using either primal or dual formulation whichever leads to faster computations. The paper presents empirical evidence where the dual formulation provides a significant speedup in computing affine policies in the context of lot-sizing and facility location problems. In addition, the paper also presents insights on when the dualized formulation leads to faster computations.
Honorable Mention
Will Ma (MIT), for his paper "Improvements and Generalizations of Stochastic Knapsack and Markovian Bandits Approximation Algorithms."
Selection Committee
Vineet Goyal (chair), Kiavash Kianfar, Javier Peña, Ermin Wei.