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

article

Fully Sequential Procedures for Large-Scale Ranking-and-Selection Problems in Parallel Computing Environments

Authors:

Barry L. Nelson,

Yang WuAuthors Info & Claims

Operations Research, Volume 63, Issue 5

Pages 1177 - 1194

Published: 01 October 2015 Publication History

Abstract

Fully sequential ranking-and-selection R&S procedures to find the best from a finite set of simulated alternatives are often designed to be implemented on a single processor. However, parallel computing environments, such as multi-core personal computers and many-core servers, are becoming ubiquitous and easily accessible for ordinary users. In this paper, we propose two types of fully sequential procedures that can be used in parallel computing environments. We call them vector-filling procedures and asymptotic parallel selection procedures, respectively. Extensive numerical experiments show that the proposed procedures can take advantage of multiple parallel processors and solve large-scale R&S problems.

References

[1]

Amdahl G (1967) Validity of the single processor approach to achieving large-scale computing capabilities. AFIPS Conf. Proc., Vol. 30 (ACM, New York), 483-485.

[2]

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

[3]

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

[4]

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

Digital Library

[5]

Buzacott JA, Shanthikumar JG (1993) Stochastic Models of Manufacturing Systems (Prentice Hall, Englewood Cliffs, NJ).

[6]

Cario MC, Nelson BL (1998) Numerical methods for fitting and simulating autoregressive-to-anything processes. INFORMS J. Comput. 10(1):72-81.

Digital Library

[7]

Chen EJ (2005) Using parallel and distributed computing to increase the capability of selection procedures. Proc. 2005 Winter Simulation Conf. (IEEE, Washington, DC), 723-731.

[8]

Chen C-H, Lin J, Yücesan E, Chick SE (2000) Simulation budget allocation for further enhancing the efficiency of ordinal optimization. Discrete Event Dynamic Systems 10:251-270.

Digital Library

[9]

Chick SE, Frazier PI (2012) Sequential sampling with economics of selection procedures. Management Sci. 58(3):550-569.

Digital Library

[10]

Chick SE, Gans N (2009) Economic analysis of simulation selection problems. Management Sci. 55(3):421-437.

Digital Library

[11]

Chick SE, Inoue K (2001a) New procedures to select the best simulated system using common random numbers. Management Sci. 47(8):1133-1149.

Digital Library

[12]

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

Digital Library

[13]

Durrett R (2004) Probability: Theory and Examples, 3rd ed. (Duxbury Press, Pacific Grove, CA).

[14]

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

[15]

Foster I (1995) Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering (Addison-Wesley, Reading, MA).

[16]

Fujimoto RM (1990) Parallel discrete event simulation. Commun. ACM 33:30-53.

Digital Library

[17]

Fujimoto RM, Malik AW, Park AJ (2010) Parallel and distributed simulation in the cloud. SCS Model. Simulation Magazine 1:1-10.

[18]

Glynn PW, Heidelberger P (1991) Analysis of parallel replicated simulations under a completion time constraint. ACM Trans. Model. Comput. Simulation 1:3-23.

Digital Library

[19]

Heidelberger P (1988) Discrete event simulation and parallel processing: statistical properties. SIAM J. Sci. Statist. Comput. 6:1114-1132.

[20]

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

[21]

Hong LJ, Nelson BL (2005) The tradeoff between sampling and switching: New sequential procedures for indifference-zone selection. IIE Trans. 37:623-634.

[22]

Hong LJ, Nelson BL (2007) Selecting the best system when systems are revealed sequentially. IIE Trans. 39:723-734.

[23]

Hong LJ, Nelson BL (2009) A brief introduction to optimization via simulation. Proc. 2009 Winter Simulation Conf. (IEEE, Washington, DC), 75-85.

[24]

Hsieh M, Glynn PW (2009) New estimators for parallel steady-state simulations. Proc. 2009 Winter Simulation Conf. (IEEE, Washington, DC), 469-474.

[25]

Kim S-H, Nelson BL (2001) A fully sequential procedure for indifferencezone selection in simulation. ACM Trans. Modeling Comput. Simulation 11:251-273.

Digital Library

[26]

Kim S-H, Nelson BL (2006a) On the asymptotic validity of fully sequential selection procedures for steady-state simulation. Oper. Res. 54(3):475-488.

Digital Library

[27]

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

[28]

Kim S-H, Nelson BL, Wilson JR (2005) Some almost-sure convergence properties useful in sequential analysis. Sequential Anal. 24(4): 411-419.

[29]

Luo J, Hong LJ (2011) Large-scale ranking and selection using cloud computing. Proc. 2011 Winter Simulation Conf. (IEEE, Washington, DC), 4051-4061.

[30]

Misra J (1986) Distributed discrete-event simulation. ACM Comput. Surveys 18:39-65.

Digital Library

[31]

Nelson BL, 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

[32]

Ni EC, Hunter SR, Henderson SG (2013) Ranking and selection in a high performance computing environment. Proc. 2013 Winter Simulation Conf. (IEEE, Washington, DC), 833-845.

[33]

Pichitlamken J, Nelson BL, Hong LJ (2006) A sequential procedure for neighborhood selection-of-the-best in optimization via simulation. Eur. J. Oper. Res. 173:283-298.

[34]

Pinedo ML (2008) Scheduling: Theory, Algorithms, and Systems, 3rd ed. (Springer, New York).

[35]

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

[36]

Silvay LME, Buyya R (1999) Parallel programming models and paradigms. High Performance Cluster Computing: Programming and Applications (Prentice Hall, Upper Saddle River, NJ), 4-27.

[37]

Stein C (1945) A two-sample test for a linear hypothesis whose power is independent of the variance. Ann. Math. Statist. 16:243-258.

[38]

Whitt W (2002) Stochastic-Process Limits, Springer Series in Operations Research (Springer, New York).

[39]

Xu J, Nelson BL, Hong LJ (2010) Industrial strength COMPASS: A comprehensive algorithm and software for optinization via simulation. ACM Trans. Modeling Comput. Simulation 20:1-29.

Digital Library

[40]

Yücesan E, Luo Y-C, Chen CH, Lee I (2001) Distributed web-based simulation experiments for optimization. Simulation Practice Theory 9:73-90.

Cited By

Wu DWang YZhou E(2024)Data-Driven Ranking and Selection Under Input UncertaintyOperations Research10.1287/opre.2022.237572:2(781-795)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/opre.2022.2375
Li HLam HPeng Y(2024)Efficient Learning for Clustering and Optimizing Context-Dependent DesignsOperations Research10.1287/opre.2022.236872:2(617-638)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/opre.2022.2368
Pei LNelson BHunter S(2024)Parallel Adaptive Survivor SelectionOperations Research10.1287/opre.2022.234372:1(336-354)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/opre.2022.2343
Show More Cited By

Recommendations

Speeding Up Paulson’s Procedure for Large-Scale Problems Using Parallel Computing
With the rapid development of computing technology, using parallel computing to solve large-scale ranking-and-selection (R&S) problems has emerged as an important research topic. However, direct implementation of traditionally fully sequential procedures ...
Efficient Ranking and Selection in Parallel Computing Environments

The goal of ranking and selection R&S procedures is to identify the best stochastic system from among a finite set of competing alternatives. Such procedures require constructing estimates of each system's performance, which can be obtained ...
Portable and Efficient Parallel Computing Using the BSP Model

The Bulk-Synchronous Parallel (BSP) model was proposed by Valiant as a standard interface between parallel software and hardware. In theory, the BSP model has been shown to allow the asymptotically optimal execution of architecture-independent software ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Operations Research

Operations Research Volume 63, Issue 5

October 2015

269 pages

ISSN:0030-364X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 October 2015

Accepted: 01 June 2015

Received: 01 June 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu DWang YZhou E(2024)Data-Driven Ranking and Selection Under Input UncertaintyOperations Research10.1287/opre.2022.237572:2(781-795)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/opre.2022.2375
Li HLam HPeng Y(2024)Efficient Learning for Clustering and Optimizing Context-Dependent DesignsOperations Research10.1287/opre.2022.236872:2(617-638)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1287/opre.2022.2368
Pei LNelson BHunter S(2024)Parallel Adaptive Survivor SelectionOperations Research10.1287/opre.2022.234372:1(336-354)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/opre.2022.2343
Zhou RPeng Y(2023)Pomdp-Based Ranking and SelectionProceedings of the Winter Simulation Conference10.5555/3643142.3643425(3388-3399)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3643142.3643425
Zhao JEckman DGatica J(2023)Screening Simulated Systems for OptimizationProceedings of the Winter Simulation Conference10.5555/3643142.3643143(1-15)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3643142.3643143
Zhang HZheng ZLavaei J(2023)Gradient-Based Algorithms for Convex Discrete Optimization via SimulationOperations Research10.1287/opre.2022.229571:5(1815-1834)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1287/opre.2022.2295
Avci HNelson BSong EWächter A(2023)Using Cache or Credit for Parallel Ranking and SelectionACM Transactions on Modeling and Computer Simulation10.1145/361829933:4(1-28)Online publication date: 26-Oct-2023
https://dl.acm.org/doi/10.1145/3618299
Nelson B(2022)Let's Do Ranking & SelectionProceedings of the Winter Simulation Conference10.5555/3586210.3586226(180-191)Online publication date: 11-Dec-2022
https://dl.acm.org/doi/10.5555/3586210.3586226
Hong LJiang GZhong Y(2022)Solving Large-Scale Fixed-Budget Ranking and Selection ProblemsINFORMS Journal on Computing10.1287/ijoc.2022.122134:6(2930-2949)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1287/ijoc.2022.1221
Eckman DHenderson S(2022)Posterior-Based Stopping Rules for Bayesian Ranking-and-Selection ProceduresINFORMS Journal on Computing10.1287/ijoc.2021.113234:3(1711-1728)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1287/ijoc.2021.1132
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents