Multi-objective ranking and selection: Optimal sampling laws and tractable approximations via SCORE

Multi-objective ranking and selection: Optimal sampling laws and tractable approximations via SCORE. Applegate, E. A., Feldman, G., Hunter, S. R., & Pasupathy, R. Journal of Simulation, 14(1):21–40, 2020. Recipient of the KD Tocher Medal, 2019-2020, The Operational Research Society.

Paper doi abstract bibtex

Consider the multi-objective ranking and selection (MORS) problem in which we select the Pareto-optimal set from a finite set of systems evaluated on three or more stochastic objectives. Solving this problem is difficult because we must determine how to allocate a simulation budget among the systems to minimize the probability that any systems are misclassified. Toward determining such a simulation budget allocation, we characterize the exact asymptotically optimal sample allocation that maximizes the misclassification-probability decay rate, and we provide an implementable allocation called MO-SCORE. The MO-SCORE allocation has three salient features: (a) it simultaneously controls the probabilities of misclassification by exclusion and inclusion; (b) it uses a fast dimension-sweep algorithm to identify phantom Pareto systems crucial for computational efficiency; and (c) it models dependence between the objectives. The MO-SCORE allocation is fast and accurate for problems with three objectives or a small number of systems. For problems with four or more objectives and a large number of systems, where modeling dependence has diminishing returns relative to computational speed, we propose independent MO-SCORE (iMO-SCORE). Our numerical experience is extensive and promising: MO-SCORE and iMO-SCORE successfully solve MORS problems involving several thousand systems in three and four objectives.

@article{2020appfeletal,
	Year = {2020},
	Author = {E. A. Applegate and G. Feldman and S. R. Hunter and R. Pasupathy},
	Title = {Multi-objective ranking and selection: {O}ptimal sampling laws and tractable approximations via {SCORE}},
	journal = {Journal of Simulation},
	volume = {14},
	number = {1},
	pages = {21--40},
	doi = {10.1080/17477778.2019.1633891},
	url_Paper = {http://web.ics.purdue.edu/~hunter63/PAPERS/pre2019appfeletal.pdf},
	abstract = {Consider the multi-objective ranking and selection (MORS) problem in which we select the Pareto-optimal set from a finite set of systems evaluated on three or more stochastic objectives. Solving this problem is difficult because we must determine how to allocate a simulation budget among the systems to minimize the probability that any systems are misclassified. Toward determining such a simulation budget allocation, we characterize the exact asymptotically optimal sample allocation that maximizes the misclassification-probability decay rate, and we provide an implementable allocation called MO-SCORE. The MO-SCORE allocation has three salient features: (a) it simultaneously controls the probabilities of misclassification by exclusion and inclusion;  (b) it uses a fast dimension-sweep algorithm to identify phantom Pareto systems crucial for computational efficiency; and (c) it models dependence between the objectives. The MO-SCORE allocation is fast and accurate for problems with three objectives or a small number of systems. For problems with four or more objectives and a large number of systems, where modeling dependence has diminishing returns relative to computational speed, we propose independent MO-SCORE (iMO-SCORE). Our numerical experience is extensive and promising: MO-SCORE and iMO-SCORE successfully solve MORS problems involving several thousand systems in three and four objectives.},
	keywords = {simulation optimization > multi-objective > ranking and selection},
	bibbase_note = {<span style="color: green">Recipient of the KD Tocher Medal, 2019-2020, The Operational Research Society.</span>}}

Downloads: 0