Discrete stochastic optimization via a modification of the stochastic ruler method

ABSTRACT

In this paper, we present a modification of the stochastic ruler method for solving discrete stochastic optimization problems. Our method generates a stationary Markov chain sequence taking values in the feasible set of the underlying discrete optimization problem. The number of visits to every state by this Markov chain is used to estimate the optimal solution. Unlike the original stochastic ruler method, our method is guaranteed to converge almost surely to a global optimal solution. We present empirical results that illustrate the performance of our method, and we show that these results compare favorably with empirical results obtained using the original stochastic ruler method.

REFERENCES

• 1: Mahmoud H. Alrefaei , Sigrún Andradóttir, A new search algorithm for discrete stochastic optimization, Proceedings of the 27th conference on Winter simulation, p.236-241, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224468]
• 2: Alrefaei, M. H., and S. Andrad6ttir. 1996. A modification of the stochastic ruler method. Working paper.
• 3: Sigrún Andradóttir, A method for discrete stochastic optimization, Management Science, v.41 n.12, p.1946-1961, Dec. 1995 [doi>10.1287/mnsc.41.12.1946]
• 4: Andrad6ttir, S. 1996. A global search method for discrete stochastic optimization. To appear in the SIAM Journal on Optimization.
• 5: Bechhofer, R. E., T. J. $antner, and D. M. Goldsman. 1995. Design and Analysis of Experiments for Statistical Selection, Screening, and Multiple Comparisons. New York: Wiley.
• 6: Fox, B. L., and G. W. Heine. 1995. Probabilistic search with overrides. The Annals of Applied Probability 5:1087-1094.
• 7: Gelfand, S. B., and S. K. Mitter. 1989. Simulated annealing with noisy or imprecise energy measuremeats. Journal of Optimization Theory and Applications 62:49-62.
• 8: David Goldsman , Barry L. Nelson , Bruce Schmeiser, Methods for selecting the best system, Proceedings of the 23rd conference on Winter simulation, p.177-186, December 08-11, 1991, Phoenix, Arizona, United States
• 9: Ho, Y. C., R. S. Sreenivas, and P. Vakili. 1992. Ordinal optimization of DEDS. journal of Discrete Event Dynamical Systems 2:61-88.
• 10: Lee, j. 1995. Faster simulated annealing techniques for stochastic optimization problems, with application to queueing network simulation. Ph.D. Thesis, North Carolina State University, Raleigh.
• 11: Di Yan , H. Mukai, Stochastic discrete optimization, SIAM Journal on Control and Optimization, v.30 n.3, p.594-612, June 1992 [doi>10.1137/0330034]