Stochastic systems simulation optimization

Abstract

With the advance of new computational technology, stochastic systems simulation and optimization has become increasingly a popular subject in both academic research and industrial applications. This paper presents some of recent developments about the problem of optimizing a performance function from a simulation model.We begin by classifying different types of problems and then provide an overview of the major approaches, followed by a more in-depth presentation of two specific areas: optimal computing budget allocation and the nested partitions method.

Keywords

simulation optimization / discrete-event systems / simulation-based decision making / computing budget allocation / ranking and selection

References

[1] Fu M C. Are we there yet? The marriage between simulation & optimization. OR/MS Today, 2007, 16-17

[2] Rubinstein R Y, Shapiro A. Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method. New York, NY: John Wiley & Sons, 1993

[3] Homem-de-Mello T, Shapiro A, Spearman M L. Finding optimal material release times using simulation-based optimization. Management Science, 1999, 45(1): 86-102

[4] Kleywegt A, Shapiro A, Homem-de-Mello T. The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 2002, 12(2): 479-502

[5] Barton R R, Meckesheimer M. Metamodel-based simulation optimization. In: Henderson S G, Nelson B L, eds. Handbooks in Operations Research and Management Science: Simulation. Chapter 18. Amsterdam: Elsevier, 2006, 535-574

[6] Kleijnen J. Design and Analysis of Simulation Experiments. New York, NY: Springer, 2008

[7] Kushner H J, Yin G G. Stochastic Approximation Algorithms and Applications. 2nd ed. New York, NY: Springer-Verlag, 2003

[8] Ólafsson S. Metaheuristics. In: Henderson S G, Nelson B L, eds. Handbooks in Operations Research and Management Science: Simulation. Chapter 21. Amsterdam: Elsevier, 2006, 633-654

[9] Fu M C. Optimization via simulation: A review. Annals of Operations Research, 1994, 53(1): 199-247

[10] Fu M C. Optimization for simulation: Theory vs. practice (Feature Article). INFORMS Journal on Computing, 2002, 14(3): 192-215

[11] Andradóttir S. Simulation optimization. In: Banks J, ed. Handbook of Simulation: Principles, Methodology, Advances, Applications, and Practice. Chapter 9. New York, NY: John Wiley & Sons, 1998

[12] Andradóttir S. An overview of simulation optimization with random search. In: Henderson S G, Nelson B L, eds. Handbooks in Operations Research and Management Science: Simulation. Chapter 20. Amsterdam: Elsevier, 2006, 617-632

[13] Fu M C. Gradient estimation. In: Henderson S G, Nelson B L, eds. Handbooks in Operations Research and Management Science: Simulation. Chapter 19. Amsterdam: Elsevier, 2006, 575-616

[14] Fu M C. What you should know about simulation and derivatives. Naval Research Logistics, 2008, 55(8): 723-736

[15] Fu MC. Sample path derivatives for (s, S) inventory systems. Operations Research, 1994, 42(2): 351-364

[16] Fu M C, Hu J Q. (s, S) inventory systems with random lead times: Harris recurrence and its implications in sensitivity analysis. Probability in the Engineering and Informational Sciences, 1994, 8(3): 355-376

[17] Bashyam S, Fu M C. Application of perturbation analysis to a class of periodic review (s, S) inventory systems. Naval Research Logistics, 1994, 41(1): 47-80

[18] Bashyam S, Fu M C. Optimization of (s, S) inventory systems with random lead times and a service level constraint. Management Science, 1998, 44(12): S243-S256

[19] Pflug G C, Rubinstein R Y. Inventory processes: Quasiregenerative property, performance evaluation and sensitivity estimation via simulation. Stochastic Models, 2002, 18(3): 469-496

[20] Zhang H, Fu M C. Sample path derivatives for (s, S) inventory systems with price determination. In: Golden B L, Raghavan S, Wasil E A, eds. The Next Wave in Computing, Optimization, and Decision Technologies. Boston, MA: Kluwer Academic Publisher, 2005, 229-246

[21] Whitt W. What you should know about queuing models to set staffing requirements in service systems. Naval Research Logistics, 2007, 54(5): 476-484

[22] Bechhofer R E, Santner T J, Goldsman D M. Design and Analysis of Experiments for Statistical Selection, Screening, and Multiple Comparisons. New York, NY: John Wiley & Sons, 1995

[23] Kim S H, Nelson B L. Selecting the best system. In: Henderson S G, Nelson B L, eds. Handbooks in Operations Research and Management Science: Simulation. Chapter 17. Amsterdam: Elsevier, 2006, 501-534

[24] Chen H C, Chen C H, Dai L, Yücesan E. New development of optimal computing budget allocation for discrete event simulation. In: Proceedings of the 1997 Winter Simulation Conference. 1997, 334-341

[25] Chen C H, Lin J, Yücesan E, Chick S E. Simulation budget allocation for further enhancing the efficiency of ordinal optimization. Discrete Event Dynamic Systems: Theory and Applications, 2000, 10(3): 251-270

[26] Chen C H, Yücesan E, Dai L, Chen H C. Optimal budget allocation for discrete-event simulation experiments. IIE Transactions, 2010, 42(1): 60-70

[27] Fu M C, Hu J Q, Chen C H, Xiong X. Simulation allocation for determining the best design in the presence of correlated sampling. INFORMS Journal on Computing, 2007, 19(1): 101-111

[28] Glynn P, Juneja S. A large deviations perspective on ordinal optimization. In: Proceedings of the 2004 Winter Simulation Conference. 2004, 577-585

[29] Fu M C, Hu J Q, Chen C H, Xiong X. Optimal computing budget allocation under correlated sampling. In: Proceedings of the 2004 Winter Simulation Conference. 2004, 595-603

[30] Brantley M W, Lee L H, Chen C H, Chen A. Optimal sampling in design of experiment for simulation-based stochastic optimization. In: Proceedings of 2008 IEEE Conference on Automation Science and Engineering. 2008, 388-393

[31] Lee L H, Chew E P, Teng S Y, Goldsman D. Optimal computing budget allocation for multi-objective simulation models. In: Proceedings of the 2004 Winter Simulation Conference. 2004, 586-594

[32] Chew E P, Lee L H, Teng S Y, Koh C H. Differentiated service inventory optimization using nested partitions and MOCBA. Computers & Operations Research, 2009, 36(5): 1703-1710

[33] Lee L H, Chew E P, Teng S Y, Goldsman D. Finding the nondominated Pareto set for multi-objective simulation models. IIE Transactions, 2010, 42(9): 656-674

[34] Chick S E, Wu Y Z. Selection procedures with frequentist expected opportunity cost. Operations Research, 2005, 53(5): 867-878

[35] He D, Chick S E, Chen C H. The opportunity cost and OCBA selection procedures in ordinal optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2007, 37(5): 951-961

[36] Trailovic L, Pao L Y. Computing budget allocation for efficient ranking and selection of variances with application to target tracking algorithms. IEEE Transactions on Automatic Control, 2004, 49(1): 58-67

[37] Morrice D J, Brantley M W, Chen C H. An efficient ranking and selection procedure for a linear transient mean performance measure. In: Proceedings of the 2008 Winter Simulation Conference. 2008, 290-296

[38] Morrice D J, Brantley M W, Chen C H. A transient means ranking and selection procedure with sequential sampling constraints. In: Proceedings of the 2009 Winter Simulation Conference. 2009, 590-600

[39] Chen C H, He D, Fu M C, Lee L H. Efficient simulation budget allocation for selecting an optimal subset. INFORMS Journal on Computing, 2008, 20(4): 579-595

[40] Pujowidianto N A, Lee L H, Chen C H, Yep C M. Optimal computing budget allocation for constrained optimization. In: Proceedings of the 2009 Winter Simulation Conference. 2009, 584-589

[41] Yan S, Zhou E, Chen C H. Efficient simulation budget allocation for selecting the best set of simplest good enough designs. In: Proceedings of the 2010 Winter Simulation Conference. 2010, 1152-1159

[42] Chick S E, Inoue K. New two-stage and sequential procedures for selecting the best simulated system. Operations Research, 2001, 49(5): 732-743

[43] Chick S E, Inoue K. New procedures to select the best simulated system using common random numbers. Management Science, 2001, 47(8): 1133-1149

[44] Branke J, Chick S E, Schmidt C. Selecting a selection procedure. Management Science, 2007, 53(12): 1916-1932

[45] Chen C H. A lower bound for the correct subset-selection probability and its application to discrete event system simulations. IEEE Transactions on Automatic Control, 1996, 41(8): 1227-1231

[46] Chen C H, Lee L H. Stochastic Simulation Optimization: An Optimal Computing Budget Allocation. Singapore: World Scientific Publishing Company, 2011

[47] Rinott Y. On two-stage selection procedures and related probability inequalities. Communications in Statistics, 1978, 7(8): 799-811

[48] Shi L, Ólafsson S. Nested partitions method for global optimization. Operations Research, 2000, 48(3): 390-407

[49] Shi L, Ólafsson S. Nested partitions method for stochastic optimization. Methodology and Computing in Applied Probability, 2000, 2(3): 271-291

[50] Shi L, Ólafsson S. Nested Partitions Optimization: Methodology and Applications. New York, NY: Springer, 2008

[51] Shi L, Ólafsson S. Nested partitions optimization. In: Tutorials in Operations Research. Chapter 1. Hanover, MD: INFORMS, 2007, 1-22

[52] Shi L, Ólafsson S, Sun N. New parallel randomized algorithms for the traveling salesman problem. Computers & Operations Research, 1999, 26(4): 371-394

[53] Ho Y C, Sreenivas R S, Vakili P. Ordinal optimization of DEDS. Discrete Event Dynamic Systems: Theory and Applications, 1992, 2(4): 61-88

[54] Ho Y C, Cassandras C G, Chen C H, Dai L. Ordinal optimization and simulation. Journal of the Operational Research Society, 2000, 51(4): 490-500

[55] Shi L, Chen C H. A new algorithm for stochastic discrete resource allocation optimization. Discrete Event Dynamic Systems: Theory and Applications, 2000, 10(3): 271-294

[56] Chen C H, Fu M C, Shi L. Simulation and optimization. In: Tutorials in Operations Research. Chapter 11. Hanover, MD: INFORMS, 2008, 247-260

[57] Fu M C, Chen C H, Shi L. Some topics for simulation optimization. In: Proceedings of the 2008 Winter Simulation Conference. 2008, 27-38

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg