A Novel Parallel Adaptive Survivor Selection Framework for Large-Scale Simulation Optimization

Pei, Linda

doi:https://doi.org/10.21985/n2-6vjf-j924

Work

A Novel Parallel Adaptive Survivor Selection Framework for Large-Scale Simulation Optimization

Public

Download PDF

For stochastic simulation optimization in a modern computing era, we introduce a new parallel framework for solving very large-scale problems using a ranking & selection (R&S) approach that simulates all systems or feasible solutions to provide a global statistical guarantee. We propose a parallel adaptive survivor selection (PASS) framework that screens systems through sequential simulation and comparison to an adaptive estimated standard. This estimated standard is a surrogate for an unknown standard with a true value that is learned over time. Rather than adopt family-wise error statements and pairwise-comparisons approaches commonly found in traditional R&S procedures originally designed for a serial processor setting, PASS controls the expected false elimination rate and compares each system marginally to a single estimated standard comprised of aggregated data. In doing so, PASS avoids the curse of multiplicity and many of the computational bottlenecks that prevent other algorithms from scaling up. In a master-worker computing framework, we demonstrate the effectiveness of PASS on realistic problems with more than a million systems, and compare it to other parallel competitors. We develop a mathematical representation of PASS and establish results regarding its small sample and asymptotic behavior. We show that PASS is not only theoretically robust, but also practically efficacious: we analyze how its synchronous implementation ameliorates communication overhead prevalent in parallel environments and prove statistically that it can be combined with other procedures to provide a good selection guarantee.

Creator