Simulated Annealing for Solving A Special Class of Stochastic Optimization Problems

Abstract

In the field of management and administrative science, operations research and industrial engineering, although estimating the performance of a complex stochastic system is of great value to the decision maker, it is not always sufficient. For example, a production control manager may be interested in finding out the probability that all demands are met from on-hand inventory under a certain system configuration of a fixed safety stock and a fixed order quantity. However, he might be more interested in finding out what values of safety stock and order quantity will maximize this probability. In this paper we propose two variants of Simulated Annealing (SA) algorithm to solve a special class of discrete stochastic optimization problems where the objective function can be represented as the probability involving a performance event of a stochastic system. Similar to the original SA algorithm, both variants have the hill climbing feature to escape the trap of local optima. The first variant selects the last state visited by the algorithm to be the estimate of the optimal solution. The second variant selects the most frequently visited state to estimate the optimal solution. Like the original SA algorithm, the first variant uses decreasing annealing temperature, while the second variant uses constant temperature. Computational results are given to demonstrate the performance of the proposed SA algorithms.