More Web Proxy on the site http://driver.im/

research-article

Public Access

Reusing Search Data in Ranking and Selection: What Could Possibly Go Wrong?

Authors:

David J. Eckman,

Shane G. HendersonAuthors Info & Claims

ACM Transactions on Modeling and Computer Simulation (TOMACS), Volume 28, Issue 3

Article No.: 18, Pages 1 - 15

https://doi.org/10.1145/3170503

Published: 06 July 2018 Publication History

Abstract

It is tempting to reuse replications taken during a simulation optimization search as input to a ranking-and-selection procedure. However, even when the random inputs used to generate replications are identically distributed and independent within and across systems, we show that for searches that use the observed performance of explored systems to identify new systems, the replications are conditionally dependent given the sequence of returned systems. Through simulation experiments, we demonstrate that reusing the replications taken during search in selection and subset-selection procedures can result in probabilities of correct and good selection well below the guaranteed levels. Based on these negative findings, we call into question the guarantees of established ranking-and-selection procedures that reuse search data. We also rigorously define guarantees for ranking-and-selection procedures after search and discuss how procedures that only provide guarantees in the preference zone are ill-suited to this setting.

References

[1]

Mohamed A. Ahmed and Talal M. Alkhamis. 2002. Simulation-based optimization using simulated annealing with ranking and selection. Computers and Operations Research 29, 4 (2002), 387--402.

[2]

Robert E. Bechhofer. 1954. A single-sample multiple decision procedure for ranking means of normal populations with known variances. Annals of Mathematical Statistics 25, 1 (1954), 16--39.

[3]

Robert E. Bechhofer, Thomas J. Santner, and David M. Goldsman. 1995. Design and Analysis of Experiments for Statistical Selection, Screening, and Multiple Comparisons. Wiley, New York.

[4]

Justin Boesel, Barry L. Nelson, and Nobuaki Ishii. 2003a. A framework for simulation-optimization software. IIE Transactions 35, 3 (2003), 221--229.

[5]

Justin Boesel, Barry L. Nelson, and Seong-Hee Kim. 2003b. Using ranking and selection to “clean up” after simulation optimization. Operations Research 51, 5 (2003), 814--825.

Digital Library

[6]

Edward J. Dudewicz and Siddhartha R. Dalal. 1975. Allocation of observations in ranking and selection with unequal variances. The Indian Journal of Statistics 37, 1 (1975), 28--78.

[7]

Eyal Even-Dar, Shie Mannor, and Yishay Mansour. 2006. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research 7, June (2006), 1079--1105.

Digital Library

[8]

Mingbin Feng and Jeremy Staum. 2017. Green simulation: Reusing the output of repeated experiments. ACM Transactions on Modeling and Computer Simulation 27, 4 (2017), 23:1--23:28.

Digital Library

[9]

Peter Frazier. 2014. A fully sequential elimination procedure for indifference-zone ranking and selection with tight bounds on probability of correct selection. Operations Research 62, 4 (2014), 926--942.

Digital Library

[10]

Michael Fu. 2015. Handbook of Simulation Optimization, Vol. 216. Springer, New York.

Digital Library

[11]

Peter Glynn and Sandeep Juneja. 2015. Selecting the best system, large deviations, and multi-armed bandits. Preprint arXiv:1507.04565v2. http://arxiv.org/abs/1507.04564v2.

[12]

Shanti S. Gupta. 1965. On some multiple decision (selection and ranking) rules. Technometrics 7, 2 (1965), 225--245.

[13]

Shane G. Henderson and Barry L. Nelson (Eds.). 2006. Handbooks in Operations Research and Management Science: Simulation, Vol. 13. Elsevier, Amsterdam.

[14]

L. Jeff Hong and Barry L. Nelson. 2007. Selecting the best system when systems are revealed sequentially. IIE Transactions 39, 7 (2007), 723--734.

[15]

Susan R. Hunter and Raghu Pasupathy. 2010. Large-deviation sampling laws for constrained simulation optimization on finite sets. In Proceedings of the 2010 Winter Simulation Conference. 995--1002.

Digital Library

[16]

Seong-Hee Kim and Barry L. Nelson. 2001. A fully sequential procedure for indifference-zone selection in simulation. ACM Transactions on Modeling and Computer Simulation (TOMACS) 11, 3 (2001), 251--273.

Digital Library

[17]

Seong-Hee Kim and Barry L. Nelson. 2006a. On the asymptotic validity of fully sequential selection procedures for steady-state simulation. Operations Research 54, 3 (2006), 475--488.

Digital Library

[18]

Seong-Hee Kim and Barry L. Nelson. 2006b. Selecting the best system. In Simulation, edited by Shane G. Henderson and Barry L. Nelson, Handbooks in Operations Research and Management Sscience, Vol. 13. Elsevier, Amsterdam.

[19]

Barry L. Nelson and Frank Matejcik. 1995. Using common random numbers for indifference-zone selection and multiple comparisons in simulation. Management Science 41, 12 (1995), 1935--1945.

[20]

Barry L. Nelson, Julie Swann, David Goldsman, and Wheyming Song. 2001. Simple procedures for selecting the best simulated system when the number of alternatives is large. Operations Research 49, 6 (2001), 950--963.

Digital Library

[21]

Sigurdur Olafsson. 1999. Iterative ranking-and-selection for large-scale optimization. In Proceedings of the 1999 Winter Simulation Conference. 479--485.

Digital Library

[22]

Juta Pichitlamken and Barry L. Nelson. 2001. Selection-of-the-best procedures for optimization via simulation. In Proceedings of the 2001 Winter Simulation Conference. 401--407.

Digital Library

[23]

Juta Pichitlamken and Barry L. Nelson. 2003. A combined procedure for optimization via simulation. ACM Transactions on Modeling and Computer Simulation 13, 2 (2003), 155--179.

Digital Library

[24]

Juta Pichitlamken, Barry L. Nelson, and L. Jeff Hong. 2006. A sequential procedure for neighborhood selection-of-the-best in optimization via simulation. European Journal of Operational Research 173, 1 (2006), 283--298.

[25]

Yosef Rinott. 1978. On two-stage selection procedures and related probability inequalities. Communications in Statistics—Theory and Methods 7, 8 (1978), 799--811.

[26]

Todd A. Sriver, James W. Chrissis, and Mark A. Abramson. 2009. Pattern search ranking and selection algorithms for mixed variable simulation-based optimization. European Journal of Operations Research 198, 3 (2009), 878--890.

[27]

Paul van der Laan. 1992. Subset selection of an almost best treatment. Biometrical Journal 34, 6 (1992), 647--656.

Cited By

Ball RBranke JMeisel S(2024)Re-use of samples in stochastic annealingComputers & Operations Research10.1016/j.cor.2024.106543164(106543)Online publication date: Apr-2024
https://doi.org/10.1016/j.cor.2024.106543
Lin YZhou E(2023)Reusing Historical Observations in Natural Policy GradientProceedings of the Winter Simulation Conference10.5555/3643142.3643398(3071-3081)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3643142.3643398
Lin YZhou E(2023)Reusing Historical Observations in Natural Policy Gradient2023 Winter Simulation Conference (WSC)10.1109/WSC60868.2023.10407512(3071-3081)Online publication date: 10-Dec-2023
https://doi.org/10.1109/WSC60868.2023.10407512
Show More Cited By

Index Terms

Reusing Search Data in Ranking and Selection: What Could Possibly Go Wrong?
1. Computing methodologies
  1. Modeling and simulation
    1. Simulation evaluation

Recommendations

Replicated Computations Results (RCR) Report for “Reusing Search Data in Ranking and Selection: What Could Possibly Go Wrong?”

“Reusing Search Data in Ranking and Selection: What Could Possibly Go Wrong?” [2] by Eckman and Henderson rigorously defines the statistical guarantees for ranking-and-selection (R8S) procedures after random search, and points out that the simulation ...
Discrete-event simulation optimization using ranking, selection, and multiple comparison procedures: A survey

An important use for discrete-event simulation models lies in comparing and contrasting competing design alternatives without incurring any physical costs. This article presents a survey of the literature for two widely used classes of statistical ...
Selecting the best stochastic system for large scale problems in DEDS

We consider the problem of selecting the stochastic system with the best expected performance measure, when the number of alternative systems is large. We consider the case of discrete event dynamic systems (DEDS) where the standard clock simulation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Modeling and Computer Simulation

ACM Transactions on Modeling and Computer Simulation Volume 28, Issue 3

July 2018

151 pages

ISSN:1049-3301

EISSN:1558-1195

DOI:10.1145/3236631

Editor:
Adelinde M. Uhrmacher
University of Rostock, Germany

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication Notes

Badge change: Article originally badged under Version 1.0 guidelines https://www.acm.org/publications/policies/artifact-review-badging

Publication History

Published: 06 July 2018

Accepted: 01 November 2017

Revised: 01 August 2017

Received: 01 October 2016

Published in TOMACS Volume 28, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Results Reproduced / v1.1

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
283
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)9

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ball RBranke JMeisel S(2024)Re-use of samples in stochastic annealingComputers & Operations Research10.1016/j.cor.2024.106543164(106543)Online publication date: Apr-2024
https://doi.org/10.1016/j.cor.2024.106543
Lin YZhou E(2023)Reusing Historical Observations in Natural Policy GradientProceedings of the Winter Simulation Conference10.5555/3643142.3643398(3071-3081)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3643142.3643398
Lin YZhou E(2023)Reusing Historical Observations in Natural Policy Gradient2023 Winter Simulation Conference (WSC)10.1109/WSC60868.2023.10407512(3071-3081)Online publication date: 10-Dec-2023
https://doi.org/10.1109/WSC60868.2023.10407512
Yerima WIkechukwu ODang KAbdallah A(2023)Fault-Tolerant Spiking Neural Network Mapping Algorithm and Architecture to 3D-NoC-Based Neuromorphic SystemsIEEE Access10.1109/ACCESS.2023.3278802(1-1)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3278802
Eckman DHenderson S(2021)Fixed-Confidence, Fixed-Tolerance Guarantees for Ranking-and-Selection ProceduresACM Transactions on Modeling and Computer Simulation10.1145/343275431:2(1-33)Online publication date: 10-Feb-2021
https://dl.acm.org/doi/10.1145/3432754
Hong LFan WLuo J(2021)Review on ranking and selection: A new perspectiveFrontiers of Engineering Management10.1007/s42524-021-0152-68:3(321-343)Online publication date: 29-Mar-2021
https://doi.org/10.1007/s42524-021-0152-6
Nelson BPei LNelson BPei L(2021)Simulation Optimization and SensitivityFoundations and Methods of Stochastic Simulation10.1007/978-3-030-86194-0_9(231-285)Online publication date: 27-Aug-2021
https://doi.org/10.1007/978-3-030-86194-0_9
Liu TZhou E(2020)Simulation optimization by reusing past replicationsProceedings of the Winter Simulation Conference10.5555/3466184.3466521(2923-2934)Online publication date: 14-Dec-2020
https://dl.acm.org/doi/10.5555/3466184.3466521
Emami N(2020)Disregarded solution spaces: A proposed approach to draw connections between computationally generated solution spaces and actual built case studiesInternational Journal of Architectural Computing10.1177/147807712096992819:3(273-290)Online publication date: 21-Nov-2020
https://doi.org/10.1177/1478077120969928
Liu TZhou E(2020)Simulation Optimization by Reusing Past Replications: Don’t Be Afraid of Dependence2020 Winter Simulation Conference (WSC)10.1109/WSC48552.2020.9384032(2923-2934)Online publication date: 14-Dec-2020
https://doi.org/10.1109/WSC48552.2020.9384032
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents