Knockout-Tournament Procedures for Large-Scale Ranking and Selection in Parallel Computing Environments

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

Operations Research, 2022, vol. 70, issue 1, 432-453

Abstract: On one hand, large-scale ranking and selection (R&S) problems require a large amount of computation. On the other hand, parallel computing environments that provide a large capacity for computation are becoming prevalent today, and they are accessible by ordinary users. Therefore, solving large-scale R&S problems in parallel computing environments has emerged as an important research topic in recent years. However, directly implementing traditional stagewise procedures and fully sequential procedures in parallel computing environments may encounter problems because either the procedures require too many simulation observations or the procedures’ selection structures induce too many comparisons and too frequent communications among the processors. In this paper, inspired by the knockout-tournament arrangement of tennis Grand Slam tournaments, we develop new R&S procedures to solve large-scale problems in parallel computing environments. We show that no matter whether the variances of the alternatives are known or not, our procedures can theoretically achieve the lowest growth rate on the expected total sample size with respect to the number of alternatives and thus, are optimal in rate. Moreover, common random numbers can be easily adopted in our procedures to further reduce the total sample size. Meanwhile, the comparison time in our procedures is negligible compared with the simulation time, and our procedures barely request for communications among the processors.

Keywords: Simulation; ranking and selection; parallel computing; optimal in rate (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.2065 (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:oropre:v:70:y:2022:i:1:p:432-453

Access Statistics for this article

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