Solution quality of random search methods for discrete stochastic optimization

In this paper, we propose a framework for selecting a high quality global optimal solution for discrete stochastic optimization problems with a predetermined confidence level using general random search methods. This procedure is based on performing the random search algorithm several replications to get estimate of the error gap between the estimated optimal value and the actual optimal value. A confidence set that contains the optimal solution is then constructed and methods of the indifference zone approach are used to select the optimal solution with high probability. The proposed procedure is applied on a simulated annealing algorithm for solving a particular discrete stochastic optimization problem involving queuing models. The numerical results indicate that the proposed technique indeed locate a high quality optimal solution.