Stochastically Constrained Ranking and Selection via SCORE
Abstract
Consider the context of constrained Simulation Optimization (SO); that is, optimization problems where the objective and constraint functions are known through dependent Monte Carlo estimators. For solving such problems on large finite spaces , we provide an easily implemented sampling framework called SCORE (Sampling Criteria for Optimization using Rate Estimators) that approximates the optimal simulation budget allocation. We develop a general theory, but, like much of the existing literature on ranking and selection, our focus is on SO problems where the distribution of the simulation observations is Gaussian. We first characterize the nature of the optimal simulation budget as a bi-level optimization problem. We then show that under a certain asymptotic limit, the solution to the bi-level optimization problem becomes surprisingly tractable and is expressed through a single intuitive measure, the score . We provide an iterative SO algorithm that repeatedly estimates the score and determines how the available simulation budget should be expended across contending systems. Numerical experience with the algorithm resulting from the proposed sampling approximation is very encouraging—in numerous examples of constrained SO problems having 1,000 to 10,000 systems, the optimal allocation is identified to negligible error within a few seconds to 1 minute on a typical laptop computer. Corresponding times to solve the full bi-level optimization problem range from tens of minutes to several hours.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 13, 2014
- Source ID
- 10.1145/2630066
Entities
People
- Chun-hung Chen
- Loo Hay Lee
- Nugroho A. Pujowidianto
- Raghu Pasupathy
- Susan R. Hunter
Organizations
- Cornell University
- Division of Civil, Mechanical & Manufacturing Innovation
- George Mason University
- National Institutes of Health
- National Science and Technology Council
- National University of Singapore
- Office of Naval Research
- United States Department of Energy
- Virginia Tech