SCORE allocations for bi-objective ranking and selection. Feldman, G. & Hunter, S. R. Under review for ACM Transactions on Modeling and Simulation, 2016.
SCORE allocations for bi-objective ranking and selection [link]Link  SCORE allocations for bi-objective ranking and selection [link]Paper  SCORE allocations for bi-objective ranking and selection [link]Paper  abstract   bibtex   
Consider the context of multi-objective optimization via simulation (MOOvS), that is, multi-objective optimization problems in which the objective functions are known only through dependent Monte Carlo estimators. The solution to this problem is a non-dominated (Pareto) set. We consider the special case of MOOvS on finite sets with two objectives, called bi-objective ranking and selection (R&S). We exploit the special structure of this problem to derive (1) the asymptotically optimal simulation budget allocation, which we characterize as the solution to a bi-level optimization problem, and (2) an easily-implementable SCORE (Sampling Criteria for Optimization using Rate Estimators) sampling framework that approximates the optimal allocation when the number of design points, or systems, is large. Notably, our allocations account for dependence between the objectives and balance the probabilities associated with two types of misclassification error: misclassification by exclusion (MCE), in which a Pareto system is estimated as non-Pareto, and misclassification by inclusion (MCI), in which a non-Pareto system is estimated as Pareto. Like much of the R&S literature, our focus is on the case in which the simulation observations are bivariate normal. Toward (2) and assuming normality, we show that in a certain asymptotic regime, the optimal allocations to non-Pareto systems in (1) are inversely proportional to a single intuitive measure called the score. Perhaps surprisingly, in this asymptotic regime, the optimal allocation exclusively controls for MCI events. We also provide an iterative algorithm that repeatedly estimates the score to determine how the available simulation budget should be expended across the competing systems. Our numerical experience with the resulting SCORE framework is promising. For problems of up to ten thousand systems, we are able to identify the optimal allocation to negligible error within a few seconds on a personal computer.
@article{2016felhun,
	Year = {2016},
	Author = {G. Feldman and S. R. Hunter},
	Title = {{SCORE} allocations for bi-objective ranking and selection},
	journal = {Under review for ACM Transactions on Modeling and Simulation},
	howpublished = {Under review for ACM Transactions on Modeling and Simulation},
	doi = {},
	url_Link = {http://www.optimization-online.org/DB_HTML/2016/06/5469.html},
	url_Paper = {http://www.optimization-online.org/DB_HTML/2016/06/5469.html},
	url = {http://www.optimization-online.org/DB_HTML/2016/06/5469.html},
	keywords = {ranking and selection, optimal allocation, multi-objective simulation optimization},
	abstract = {Consider the context of multi-objective optimization via simulation (MOOvS), that is, multi-objective optimization problems in which the objective functions are known only through dependent Monte Carlo estimators. The solution to this problem is a non-dominated (Pareto) set. We consider the special case of MOOvS on finite sets with two objectives, called bi-objective ranking and selection (R&S). We exploit the special structure of this problem to derive (1) the asymptotically optimal simulation budget allocation, which we characterize as the solution to a bi-level optimization problem, and (2) an easily-implementable SCORE (Sampling Criteria for Optimization using Rate Estimators) sampling framework that approximates the optimal allocation when the number of design points, or systems, is large. Notably, our allocations account for dependence between the objectives and balance the probabilities associated with two types of misclassification error: misclassification by exclusion (MCE), in which a Pareto system is estimated as non-Pareto, and misclassification by inclusion (MCI), in which a non-Pareto system is estimated as Pareto. Like much of the R&S literature, our focus is on the case in which the simulation observations are bivariate normal. Toward (2) and assuming normality, we show that in a certain asymptotic regime, the optimal allocations to non-Pareto systems in (1) are inversely proportional to a single intuitive measure called the score. Perhaps surprisingly, in this asymptotic regime, the optimal allocation exclusively controls for MCI events. We also provide an iterative algorithm that repeatedly estimates the score to determine how the available simulation budget should be expended across the competing systems. Our numerical experience with the resulting SCORE framework is promising. For problems of up to ten thousand systems, we are able to identify the optimal allocation to negligible error within a few seconds on a personal computer.},
	keywords = {ranking and selection, multi-objective simulation optimization},
	addendum = {Submitted May 31, 2016.}}

Downloads: 0