Closed-form sampling laws for stochastically constrained simulation optimization on large finite sets

Closed-form sampling laws for stochastically constrained simulation optimization on large finite sets. Pujowidianto, N. A., Hunter, S. R., Pasupathy, R., Lee, L. H., & Chen, C. In Laroque, C., Himmelspach, J., Pasupathy, R., Rose, O., & Uhrmacher, A. M., editors, Proceedings of the 2012 Winter Simulation Conference, pages 168–177, Piscataway, NJ, 2012. Institute of Electrical and Electronics Engineers, Inc.. Finalist, Winter Simulation Conference Best Theoretical Paper Award.

Paper doi abstract bibtex 16 downloads

Consider the context of constrained simulation optimization (SO), i.e., optimization problems where the objective function and constraints are known through a Monte Carlo simulation, with corresponding estimators possibly dependent. We identify the nature of sampling plans that characterize efficient algorithms, particularly in large countable spaces. We show that in a certain asymptotic sense, the optimal sampling characterization, that is, the sampling budget for each system that guarantees optimal convergence rates, depends on a single easily estimable quantity called the score. This result provides a useful and easily implementable sampling allocation that approximates the optimal allocation, which is otherwise intractable due to it being the solution to a difficult bilevel optimization problem. Our results point to a simple sequential algorithm for efficiently solving large-scale constrained simulation optimization problems on finite sets.

@inproceedings{2012pujhunetalWSC,
	Year = {2012},
	Author = {N. A. Pujowidianto and S. R. Hunter and R. Pasupathy and L. H. Lee and {C.-H.} Chen},
	Title = {Closed-form sampling laws for stochastically constrained simulation optimization on large finite sets},
	Booktitle = {Proceedings of the 2012 Winter Simulation Conference},
	Editor = {C. Laroque and J. Himmelspach and R. Pasupathy and O. Rose and A. M. Uhrmacher},
	Publisher = {Institute of Electrical and Electronics Engineers, Inc.},
	Address = {Piscataway, NJ},
	Pages = {168--177},
	doi = {10.1109/WSC.2012.6465141},
	url_Paper = {http://web.ics.purdue.edu/~hunter63/PAPERS/2012pujhunetalWSC.pdf},
	abstract = {Consider the context of constrained simulation optimization (SO), i.e., optimization problems where the objective function and constraints are known through a Monte Carlo simulation, with corresponding estimators possibly dependent. We identify the nature of sampling plans that characterize efficient algorithms, particularly in large countable spaces. We show that in a certain asymptotic sense, the optimal sampling characterization, that is, the sampling budget for each system that guarantees optimal convergence rates, depends on a single easily estimable quantity called the score. This result provides a useful and easily implementable sampling allocation that approximates the optimal allocation, which is otherwise intractable due to it being the solution to a difficult bilevel optimization problem. Our results point to a simple sequential algorithm for efficiently solving large-scale constrained simulation optimization problems on finite sets.},
	keywords = {simulation optimization > single-objective > stochastically constrained > ranking and selection},
	bibbase_note = {<span style="color: green">Finalist, Winter Simulation Conference Best Theoretical Paper Award.</span>}}

Downloads: 16