Design sampling and replication assignment under fixed computing budget

Abstract

For many real world problems, when the design space is huge and unstructured, and time consuming simulation is needed to estimate the performance measure, it is important to decide how many designs to sample and how long to run for each design alternative given that we have only a fixed amount of computing time. In this paper, we present a simulation study on how the distribution of the performance measures and distribution of the estimation errors/noises will affect the decision. From the analysis, it is observed that when the underlying distribution of the noise is bounded and if there is a high chance that we can get the smallest noise, then the decision will be to sample as many as possible, but if the noise is unbounded, then it will be important to reduce the noise level first by assigning more replications for each design. On the other hand, if the distribution of the performance measure indicates that we will have a high chance of getting good designs, the suggestion is also to reduce the noise level, otherwise, we need to sample more designs so as to increase the chances of getting good designs. For the special case when the distributions of both the performance measures and noise are normal, we are able to estimate the number of designs to sample, and the number of replications to run in order to obtain the best performance.

Keywords

Ranking and selection / ordinal optimization / random sampling

References

[1] Chen, C.H., “An effective approach to smartly allocate computing budget for discrete event simulation”, Proceedings of the 34th IEEE Conference on Decision and Control, pp2598–2605, 1995.

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

[3] Chen C.H., Lin J.W., 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: 251-270.

[4] Dai L.Y.. Convergence properties of ordinal comparison in the simulation of discrete event dynamic systems. Journal of Optimization Theory & Application, 1996, 91(2): 363-388.

[5] Deng M., Ho Y.C.. An ordinal optimization approach to optimal control problems. Automatica, 1999, 35(2): 331-338.

[6] Goldsman D., Nelson B.L.. Banks J.. Comparing systems via simulation. The Handbook of Simulation, 1998, New York: John Eiley 273-306.

[7] Ho Y.C., Sreenivas R., Vakili P.. Ordinal optimization of discrete event dynamic systems. Journal of Discrete Event Dynamic Systems, 1992, 2: 61-88.

[8] Lee, L.H., E.P. Chew, “A simulation study on sampling and selecting under fixed computing budget”, Proceedings of the 2003 Winter Simulation Conference, 2003.

[9] Lee L.H., Lau T.W.E., Ho Y.C.. Explanation of goal softening in ordinal optimization. IEEE Transaction on Automatic Control, 1999, 44(1): 94-99.

[10] Lin, X.C., L. H. Lee, “A new approach to discrete stochastic optimization problems”, European Journal of Operational Research, in press.

[11] Nelson B.L., Swann J., Goldsman D.. Simple procedures for selecting the best simulated system when the number of alternatives is large. Operations Research, 2001, 49(6): 950-963.

[12] Rinott Y.. On two-stage selection procedures and related probability inequalities. Communications in Statistics, 1978, A7: 799-811.

[13] Xie X.L.. Dynamics and convergence rate of ordinal comparison of stochastic discrete event systems. IEEE Transaction on Automatic Control, 1997, 42(4): 586-590.