Stochastic Programming by Monte Carlo Simulation Methods

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Many stochastic programming problems can be formulated as problems of optimization of an expected value function. Quite often the corresponding expected value function cannot be computed exactly and should be approximated, say by Monte Carlo methods. In fact, in many interesting examples, Monte Carlo simulation is the only reasonable way of estimating the expected value function. It turns out that if the underline probability distribution is discrete and the approximating problems are piecewise linear and convex, then with probability approaching one exponentially fast, with increase of the sample size, an optimal solution of the Monte Carlo approximation problem provides an exact optimal solution of the expected value problem. This gives a theoretical justification for the following approach to a numerical solution of such problems. Construct and solve a Monte Carlo approximation problem based on a relatively small sample. Repeat this procedure several times and validate calculated solutions until a stopping criterion is satisfied. The goal of this project is to develop this method. The method is ideally suited for parallel computations and some preliminary experiments showed good results. Optimization of real world systems almost always involves randomness which can come in various conceptual forms such as uncertainty, lack of information, natural variability of the data, etc. One may think, for example, about optimizing a manufacturing process when the demand for produced goods is uncertain. It turns out that solving stochastic optimization problems involving randomness is much more difficult than solving deterministic problems, both conceptually and numerically. However, there is obvious practical need for developing a methodology for dealing with stochastic problems and in recent years this was a very active area of scientific research. This proposal is aimed at developing numerical techniques for solving a particular class of stochastic problems. If successful, it will allow numerical solutions of considerably larger problems, which in turn may result in bigger variety of applications. Alexander Shapiro , Tel. 404-8946544; Fax: 404-8942301, E-mail : ashapiro@isye.gatech.edu http://www.isye.gatech.edu/~ashapiro ISyE, Georgia Tech, Atlanta, GA 30332-0205