article

A Fully Sequential Elimination Procedure for Indifference-Zone Ranking and Selection with Tight Bounds on Probability of Correct Selection

Operations Research, Volume 62, Issue 4

Pages 926 - 942

https://doi.org/10.1287/opre.2014.1282

Published: 01 August 2014 Publication History

Abstract

<P>We consider the indifference-zone (IZ) formulation of the ranking and selection problem with independent normal samples. In this problem, we must use stochastic simulation to select the best among several noisy simulated systems, with a statistical guarantee on solution quality. Existing IZ procedures sample excessively in problems with many alternatives, in part because loose bounds on probability of correct selection lead them to deliver solution quality much higher than requested. Consequently, existing IZ procedures are seldom considered practical for problems with more than a few hundred alternatives. To overcome this, we present a new sequential elimination IZ procedure, called BIZ (Bayes-inspired indifference zone), whose lower bound on worst-case probability of correct selection in the preference zone is tight in continuous time, and nearly tight in discrete time. To the author's knowledge, this is the first sequential elimination procedure with tight bounds on worst-case preference-zone probability of correct selection for more than two alternatives. Theoretical results for the discrete-time case assume that variances are known and have an integer multiple structure, but the BIZ procedure itself can be used when these assumptions are not met. In numerical experiments, the sampling effort used by BIZ is significantly smaller than that of another leading IZ procedure, the KN procedure, especially on the largest problems tested (2¹⁴ = 16,384 alternatives).</P>

References

[1]

Andradóttir S, Kim SH (2010) Fully sequential procedures for comparing constrained systems via simulation. Naval Res. Logist. 57(5):403-421.

[2]

Bechhofer RE (1954) A single-sample multiple decision procedure for ranking means of normal populations with known variances. Ann. Math. Statist. 25(1):16-39.

[3]

Bechhofer RE, Kiefer J, Sobel M (1968) Sequential Identification and Ranking Procedures (University of Chicago Press, Chicago).

[4]

Bechhofer RE, Santner TJ, Goldsman DM (1995) Design and Analysis of Experiments for Statistical Selection, Screening and Multiple Comparisons (John Wiley & Sons, New York).

[5]

Berger JO (1985) Statistical Decision Theory and Bayesian Analysis, 2nd ed. (Springer-Verlag, New York).

[6]

Branke J, Chick SE, Schmidt C (2007) Selecting a selection procedure. Management Sci. 53(12):1916-1932.

Digital Library

[7]

Chen C, Lee LH (2010) Stochastic Simulation Optimization: An Optimal Computing Budget Allocation (World Scientific Publishing, Singapore).

[8]

Chick SE, Inoue K (2001) New two-stage and sequential procedures for selecting the best simulated system. Oper. Res. 49(5):732-743.

Digital Library

[9]

Chick SE, Branke J, Schmidt C (2010) Sequential sampling to myopically maximize the expected value of information. INFORMS J. Comput. 22(1):71-80.

Digital Library

[10]

Dieker AB, Kim S-H (2012) Selecting the best by comparing simulated systems in a group of three when variances are known and unequal. Laroque C, Himmelspach J, Pasupathy R, Rose O, Uhrmacher AM, eds. Proc. 2012 Winter Simulation Conf. (IEEE, Piscataway, NJ), 490-496.

[11]

Fabian V (1974) Note on Anderson's sequential procedures with triangular boundary. Ann. Statist. 2(1):170-176.

[12]

Frazier P, Powell WB, Dayanik S (2008) A knowledge gradient policy for sequential information collection. SIAM J. Control Optim. 47(5): 2410-2439.

Digital Library

[13]

Frazier P, Powell WB, Dayanik S (2009) The knowledge gradient policy for correlated normal beliefs. INFORMS J. Computing 21(4):599-613.

[14]

Frazier PI, Powell WB (2008) The knowledge-gradient stopping rule for ranking and selection. Mason SJ, Hill RR, Mönch L, Rose O, Jefferson T, Fowler JW, eds. Proc. 2008 Winter Simulation Conf. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 305-312.

[15]

Glynn P, Juneja S (2004) A large deviations perspective on ordinal optimization. Ingalls RG, Rossetti MD, Smith JS, Peters BA, eds. Proc. 2004 Winter Simulation Conf. (IEEE, Piscataway, NJ), 577-585.

[16]

Goldsman D, Kim SH, Marshall WS, Nelson BL (2002) Ranking and selection for steady-state simulation: Procedures and perspectives. INFORMS J. Comput. 14(1):2-19.

[17]

Gupta SS, Miescke KJ (1996) Bayesian look ahead one-stage sampling allocations for selection of the best population. J. Statist. Planning and Inference 54(2):229-244.

[18]

Hartmann M (1991) An improvement on Paulson's procedure for selecting the population with the largest mean from k normal populations with a common unknown variance. Sequential Anal. 10(1-2):1-16.

[19]

Hartmann M (1988) An improvement on Paulson's sequential ranking procedure. Sequential Anal. 7(4):363-372.

[20]

Hong J (2006) Fully sequential indifference-zone selection procedures with variance-dependent sampling. Naval Res. Logist. 53(5): 464-476.

[21]

Kim S-H, Dieker AB (2011) Selecting the best by comparing simulated systems in a group of three. Jain S, Creasey RR, Himmelspach J, White KP, Fu M, eds. (IEEE, Piscataway, NJ), 3987-3997.

[22]

Kim S-H, Nelson BL (2001) A fully sequential procedure for indifference-zone selection in simulation. ACM Trans. Model. Comput. Simul. 11(3):251-273.

Digital Library

[23]

Kim SH, Nelson BL (2006) Selecting the best system. Henderson SG, Nelson BL, eds. Handbook in Operations Research and Management Science: Simulation (Elsevier, Amsterdam), 501-534.

[24]

Kim SH, Nelson BL (2007) Recent advances in ranking and selection. Henderson SG, Biller B, Hsieh M-H, Shortle J, Tew JD, Barton RR, eds. Proc. 2007 Winter Simulation Conf. (IEEE, Piscataway, NJ), 162-172.

[25]

Kleijnen JPC, van Beers W, van Nieuwenhuyse I (2010) Constrained optimization in expensive simulation: Novel approach. Eur. J. Oper. Res. 202(1):164-174.

[26]

Malone GJ, Kim S-H, Goldsman D, Batur D (2005) Performance of variance updating ranking and selection procedures. Kuhl ME, Steiger NM, Armstrong FB, Joines JA, eds. Proc. 2005 Winter Simulation Conf. (IEEE, Piscataway, NJ), 825-832.

[27]

Nelson B, Swann J, Goldsman D, Song W (2001) Simple procedures for selecting the best simulated system when the number of alternatives is large. Oper. Res. 49(6):950-963.

Digital Library

[28]

Nelson BL, Banerjee S (2001) Selecting a good system: Procedures and inference. IIE Trans. 33(3):149-166.

[29]

Pasupathy R, Henderson SG (2006) A testbed of simulation-optimization problems. Perrone LF, Wieland FP, Liu J, Lawson BG, Nicol DM, Fujimoto RM, eds. Proc. 2006 Winter Simulation Conf. (IEEE, Piscataway, NJ), 255-263.

[30]

Paulson E (1964) A sequential procedure for selecting the population with the largest mean from k normal populations. Ann. Math. Statist. 35(1):174-180.

[31]

Paulson E (1994) Sequential procedures for selecting the best one of k Koopman-Darmois populations. Sequential Anal. 13(3):207-220.

[32]

Rinott Y (1978) On two-stage selection procedures and related probability-inequalities. Comm. Statist.-Theory and Methods 7(8):799-811.

[33]

Swisher JR, Jacobson SH, Yücesan E (2003) Discrete-event simulation optimization using ranking, selection, and multiple comparison procedures: A survey. ACM Trans. Modeling Comput. Simulation 13(2): 134-154.

Digital Library

[34]

Wang H, Kim S-H (2013) Reducing the conservativeness of fully sequential indifference-zone procedures. IEEE Trans. Automatatic Control 58(6):1613-1619.

Cited By

Chen XZhang YXie GZhang J(2024)A Uniform Error Bound for Stochastic Kriging: Properties and Implications on Simulation Experimental DesignACM Transactions on Modeling and Computer Simulation10.1145/368205935:1(1-43)Online publication date: 25-Nov-2024
https://dl.acm.org/doi/10.1145/3682059
Zhang HZheng ZLavaei JRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)Stochastic L♮-convex function minimizationProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3541257(13004-13018)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3541257
Ma SHenderson S(2019)Predicting the Simulation Budget in Ranking and Selection ProceduresACM Transactions on Modeling and Computer Simulation10.1145/332371529:3(1-25)Online publication date: 18-Jun-2019
https://dl.acm.org/doi/10.1145/3323715
Show More Cited By

Recommendations

A Fully Sequential Elimination Procedure for Indifference-Zone Ranking and Selection with Tight Bounds on Probability of Correct Selection

We consider the indifference-zone IZ formulation of the ranking and selection problem with independent normal samples. In this problem, we must use stochastic simulation to select the best among several noisy simulated systems, with a statistical ...
A Fully Sequential Elimination Procedure for Indifference-Zone Ranking and Selection with Tight Bounds on Probability of Correct Selection

We consider the indifference-zone IZ formulation of the ranking and selection problem with independent normal samples. In this problem, we must use stochastic simulation to select the best among several noisy simulated systems, with a statistical ...
A multi-objective selection procedure of determining a Pareto set

Ranking and selection (R&S) procedures have been widely studied and applied in determining the required sample size (i.e., the number of replications or batches) for selecting the best system or a subset containing the best system from a set of k ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Operations Research

Operations Research Volume 62, Issue 4

August 2014

263 pages

ISSN:0030-364X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 August 2014

Accepted: 01 February 2014

Received: 01 September 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen XZhang YXie GZhang J(2024)A Uniform Error Bound for Stochastic Kriging: Properties and Implications on Simulation Experimental DesignACM Transactions on Modeling and Computer Simulation10.1145/368205935:1(1-43)Online publication date: 25-Nov-2024
https://dl.acm.org/doi/10.1145/3682059
Zhang HZheng ZLavaei JRanzato MBeygelzimer ADauphin YLiang PVaughan J(2021)Stochastic L♮-convex function minimizationProceedings of the 35th International Conference on Neural Information Processing Systems10.5555/3540261.3541257(13004-13018)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.5555/3540261.3541257
Ma SHenderson S(2019)Predicting the Simulation Budget in Ranking and Selection ProceduresACM Transactions on Modeling and Computer Simulation10.1145/332371529:3(1-25)Online publication date: 18-Jun-2019
https://dl.acm.org/doi/10.1145/3323715
Wu DZhou EJohansson BJain S(2018)Provably improving the optimal computing budget allocation algorithmProceedings of the 2018 Winter Simulation Conference10.5555/3320516.3320748(1921-1932)Online publication date: 9-Dec-2018
https://dl.acm.org/doi/10.5555/3320516.3320748
Peng YChen CChong EFu MJohansson BJain S(2018)A review of static and dynamic optimization for ranking and selectionProceedings of the 2018 Winter Simulation Conference10.5555/3320516.3320747(1909-1920)Online publication date: 9-Dec-2018
https://dl.acm.org/doi/10.5555/3320516.3320747
Eckman DHenderson SJohansson BJain S(2018)Guarantees on the probability of good selectionProceedings of the 2018 Winter Simulation Conference10.5555/3320516.3320567(351-365)Online publication date: 9-Dec-2018
https://dl.acm.org/doi/10.5555/3320516.3320567
Eckman DHenderson S(2018)Reusing Search Data in Ranking and SelectionACM Transactions on Modeling and Computer Simulation10.1145/317050328:3(1-15)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3170503
Ma SHenderson S(2017)An efficient fully sequential selection procedure guaranteeing probably approximately correct selectionProceedings of the 2017 Winter Simulation Conference10.5555/3242181.3242368(1-12)Online publication date: 3-Dec-2017
https://dl.acm.org/doi/10.5555/3242181.3242368
Jin XLi HLee LChew E(2017)Optimal computing budget allocation via sampling based unbiased approximationProceedings of the 2017 Winter Simulation Conference10.5555/3242181.3242359(1-9)Online publication date: 3-Dec-2017
https://dl.acm.org/doi/10.5555/3242181.3242359
Liu WGao SLee L(2017)A multi-objective perspective on robust ranking and selectionProceedings of the 2017 Winter Simulation Conference10.5555/3242181.3242358(1-12)Online publication date: 3-Dec-2017
https://dl.acm.org/doi/10.5555/3242181.3242358
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents