Solving Large-Scale Fixed-Budget Ranking and Selection Problems

L. Jeff Hong (), Guangxin Jiang () and Ying Zhong ()
Additional contact information
L. Jeff Hong: School of Management and School of Data Science, Fudan University, Shanghai 200433, China
Guangxin Jiang: School of Management, Harbin Institute of Technology, Harbin 150001, China
Ying Zhong: School of Management and Economics, University of Electronic Science and Technology of China, Chengdu 611731, China

INFORMS Journal on Computing, 2022, vol. 34, issue 6, 2930-2949

Abstract: In recent years, with the rapid development of computing technology, developing parallel procedures to solve large-scale ranking and selection (R&S) problems has attracted a lot of research attention. In this paper, we take fixed-budget R&S procedure as an example to investigate potential issues of developing parallel procedures. We argue that to measure the performance of a fixed-budget R&S procedure in solving large-scale problems, it is important to quantify the minimal growth rate of the total sampling budget such that as the number of alternatives increases, the probability of correct selection (PCS) would not decrease to zero. We call such a growth rate of the total sampling budget the rate for maintaining correct selection (RMCS). We show that a tight lower bound for the RMCS of a broad class of existing fixed-budget procedures is in the order of k log k , where k is the number of alternatives. Then, we propose a new type of fixed-budget procedure, namely the fixed-budget knockout-tournament ( F B K T ) procedure. We prove that, in terms of the RMCS, our procedure outperforms existing fixed-budget procedures and achieves the optimal order, that is, the order of k . Moreover, we demonstrate that our procedure can be easily implemented in parallel computing environments with almost no nonparallelizable calculations. Last, a comprehensive numerical study shows that our procedure is indeed suitable for solving large-scale problems in parallel computing environments.

Keywords: ranking and selection; fixed-budget; parallel computing; rate analysis (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1221 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:6:p:2930-2949

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().