Discrete optimization with estimation
D. Yan, H. Mukai · 2003
A computational method is proposed for finding a global solution to the discrete optimization problem in which the objective function must be estimated by Monte Carlo simulation. The proposed method is very simple, requiring mainly a computer program for simulating the system and evaluating its performance, yet it can be shown to find a global optimum solution. The method should be practical, since it can be easily used in conjunction with heuristics and yet retain its global convergence property. The Markov chain generated by the method is analyzed. It is shown under mild conditions that the probability that the current solution estimate is globally optimum converges to one. The method is expected to find many practical applications in the fields of manufacturing engineering, traffic engineering, operations research, and management science.>