Nagaraj and Pasupathy win 2nd place in the INFORMS Computing Society (ICS) Student Paper competition

11-07-2014

Kalyani Nagaraj and Raghu Pasupathy paper, 'Stochastically Constrained Simulation Optimization on Integer-Ordered Spaces:  The cgR-SPLINE Algorithm", wins second place in the Annual INFORMS Computing Society (ICS) Student paper competition. To learn more about the competion, please go here.

Brief description of the paper:

The paper presents cgR-SPLINE, a multistart algorithm that extends R-SPLINE, a local simulation optimization (SO) solver for integer spaces, to the stochastically constrained and global context. Solutions with binding stochastic constraints, often encountered in optimization problems enforcing performance level thresholds, renders the implementation of naive sample average approximation inconsistent. cgR-SPLINE, on the other hand, guarantees consistency through strategic constraint relaxation and a probabilistic comparison of solutions returned by random restarts of the modified local solver. The presence of stochastic constraints appears to weaken the general convergence rate of cgR-SPLINE from the light-tailed convergence rate associated with the unconstrained context to a sub-exponential rate. An exploration-exploitation characterization of the error probabilities demonstrates that cgR-SPLINE achieves the fastest convergence rate when the number of multistarts is proportional to the simulation budget per multistart -- contrary to the continuous context where much less exploration has been prescribed. The paper also presents heuristics on choosing constraint relaxations and solution reporting that demonstrate good finite-time performance of cgR-SPLINE while retaining its asymptotic properties.