A convergent algorithm for ranking and selection with censored observations

Abstract

We consider a problem of Ranking and Selection in the presence of Censored Observations (R&S-CO). An observation within the interval defined by lower and upper limits is observed at the actual value, whereas an observation outside the interval takes the closer limit value. The censored sample average is thus a biased estimator for the true mean performance of each alternative. The goal of R&S-CO is to efficiently find the best alternative in terms of the true mean. We first derive the censored variable’s mean and variance in terms of the mean and variance of the uncensored variable and the lower and upper limits, and then develop a sequential sampling algorithm. Under mild conditions, we prove that the algorithm is consistent, in the sense that the best can be identified almost surely, as the sampling budget goes to infinity. Moreover, we show that the asymptotic allocation converges to the optimal static allocation derived by the large deviations theory. Extensive numerical experiments are conducted to investigate the finite-budget performance, the asymptotic allocation, and the robustness of the algorithm.

KEYWORDS:

• Ranking and selection
• censored observations
• sequential sampling
• consistency
• asymptotic allocation

Acknowledgments

We thank the editors and anonymous reviewers for valuable comments.

Additional information

Funding

This paper is supported by the National Natural Science Foundation of China under grant numbers 71971176 and the Fundamental Research Funds for the Central Universities under grant number JBK2103010.

Notes on contributors

Haitao Liu

Haitao Liu received his BE and MS degrees in industrial engineering and management science from Sichuan University, China, in 2015 and 2018. He is currently working towards a PhD degree in the Department of Industrial Systems Engineering and Management at National University of Singapore. His research interests include simulation optimization and statistical learning.

Hui Xiao

Hui Xiao received his PhD degree in the Department of Industrial Systems Engineering and Management at National University of Singapore. Currently, he is a professor in the School of Statistics, Southwestern University of Finance and Economics, China. His research is devoted to simulation optimization, large-scale optimization and reliability modeling and optimization.

Loo Hay Lee

Loo Hay Lee received his PhD degree in engineering science from Harvard University, USA, in 1997. He currently is a professor in the Department of Industrial Systems Engineering and Management at National University of Singapore. His research interests include logistics, vehicle routing, supply chain modeling, and simulation-based optimization.

Ek Peng Chew

Ek Peng Chew received his PhD degree in industrial engineering from Georgia Institute of Technology, USA. He currently is a professor in the Department of Industrial Systems Engineering and Management at the National University of Singapore. His research areas are in port logistics and maritime transportation, simulation optimization and inventory management.