Finding the best in the presence of a stochastic constraint

ABSTRACT

Our problem is that of finding the best system---i.e., the system with the largest or smallest primary performance measure---among a finite number of simulated systems in the presence of a stochastic constraint on a secondary performance measure. In order to solve this problem, we first find a set that contains only feasible or near-feasible systems (Phase I) and then choose the best among those systems in the set (Phase II). We present a statistically valid procedure for Phase I and then propose another procedure that performs Phases I and II sequentially to find the best feasible system. Finally, we provide some experimental results for the second procedure.

REFERENCES

• 1: Andradóttir, S., D. Goldsman, and S.-H. Kim. 2005. Fully sequential procedures for comparing constrained systems via simulation. Working Paper, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia.
• 2: Bechhofer, R. E. 1954. A single-sample multiple decision procedure for ranking means of normal populations with known variances. Annals of Mathematical Statistics, 25:16--39.
• 3: Justin Boesel , Barry L. Nelson , Seong-Hee Kim, Using Ranking and Selection to "Clean Up" after Simulation Optimization, Operations Research, v.51 n.5, p.814-825, September 2003 [doi>10.1287/opre.51.5.814.16751]
• 4: John Butler , Douglas J. Morrice , Peter W. Mullarkey, A Multiple Attribute Utility Theory Approach to Ranking and Selection, Management Science, v.47 n.6, p.800-816, June 2001 [doi>10.1287/mnsc.47.6.800.9812]
• 5: Chen, C.-H. 1996. A lower bound for the correct-selection probability and its application to discrete event simulations. IEEE Transactions on Automatic Control, 41:1227--1231.
• 6: Hsiao-Chang Chen , Liyi Dai , Chun-Hung Chen , Enver Yücesan, New development of optimal computing budget allocation for discrete event simulation, Proceedings of the 29th conference on Winter simulation, p.334-341, December 07-10, 1997, Atlanta, Georgia, United States [doi>10.1145/268437.268501]
• 7: Chen, H.-C., C.-H. Chen, and E. Yücesan. 2000. Computing efforts allocation for ordinal optimization and discrete event simulation. IEEE Transactions on Automatic Control, 45: 960--964.
• 8: Stephen E. Chick, Selecting the best system: a decision-theoretic approach, Proceedings of the 29th conference on Winter simulation, p.326-333, December 07-10, 1997, Atlanta, Georgia, United States [doi>10.1145/268437.268499]
• 9: Stephen E. Chick , Koichiro Inoue, New Two-Stage and Sequential Procedures for Selecting the Best Simulated System, Operations Research, v.49 n.5, p.732-743, September 2001 [doi>10.1287/opre.49.5.732.10615]
• 10: Stephen E. Chick , Koichiro Inoue, New Procedures to Select the Best Simulated System Using Common Random Numbers, Management Science, v.47 n.8, p.1133-1149, August 2001 [doi>10.1287/mnsc.47.8.1133.10229]
• 11: David Goldsman , William S. Marshall , Seong-Hee Kim , Barry L. Nelson, Ranking and selection for steady-state simulation, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
• 12: David Goldsman , Seong-Hee Kim , William S. Marshall , Barry L. Nelson, Ranking and Selection for Steady-State Simulation: Procedures and Perspectives, INFORMS Journal on Computing, v.14 n.1, p.2-19, January 2002 [doi>10.1287/ijoc.14.1.2.7710]
• 13: Goldsman, D., and B. L. Nelson. 1998. Comparing systems via simulation. In Handbook of Simulation: Principles, Methodology, Advances, Applications, and Practice, ed. J. Banks, 273--306. New York: John Wiley & Sons.
• 14: Hartmann, M. 1988. An improvement on Paulson's sequential ranking procedure. Sequential Analysis, 7:363--372.
• 15: 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 Analysis, 10:1--16.
• 16: Seong-Hee Kim, Efficient simulation procedures: comparison with a standard via fully sequential procedures, Proceedings of the 35th conference on Winter simulation: driving innovation, December 07-10, 2003, New Orleans, Louisiana
• 17: Seong-Hee Kim, Comparison with a standard via fully sequential procedures, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.15 n.2, p.155-174, April 2005 [doi>10.1145/1060576.1060579]
• 18: Seong-Hee Kim , Barry L. Nelson, A fully sequential procedure for indifference-zone selection in simulation, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.11 n.3, p.251-273, July 2001 [doi>10.1145/502109.502111]
• 19: Kim, S.-H., and B. L. Nelson. 2005. On the asymptotic validity of fully sequential selection procedures for steady-state simulation. Operations Research, forthcoming.
• 20: Barry L. Nelson , Julie Swann , David Goldsman , Wheyming Song, Simple Procedures for Selecting the Best Simulated System When the Number of Alternatives is Large, Operations Research, v.49 n.6, p.950-963, November 2001 [doi>10.1287/opre.49.6.950.10019]
• 21: Paulson, E. 1964. A sequential procedure for selecting the population with the largest mean from k normal populations. Annals of Mathematical Statistics, 35:174--180.
• 22: Juta Pichitlamken , Barry L. Nelson, Comparing systems via stochastic simulation: selection-of-the-best procedures for optimization via simulation, Proceedings of the 33nd conference on Winter simulation, December 09-12, 2001, Arlington, Virginia
• 23: Pichitlamken, J., B. L. Nelson, and L. J. Hong. 2005. A sequential procedure for neighborhood selection-of-the-best in optimization via simulation. European Journal of Operational Research, forthcoming.
• 24: Rinott, Y. 1978. On two-stage selection procedures and related probability-inequalities. Communications in Statistics, A7:799--811.
• 25: Santner, T. J., and A. C. Tamhane. 1984. Designing experiments for selecting a normal population with a large mean and a small variance. In Design of Experiments - Ranking and Selection: Essays in Honor of Robert E. Bechhofer, ed. T. J. Santner and A. C. Tamhane, 179--198. New York: Marcel-Dekker.