El método de aproximación por media muestral aplicado a optimización estocástica discreta

Abstract

The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. The basic idea of such method is that a random sample is generated and the expected objective function of the stochastic problem is approximated by the corresponding sample average function. The obtained sample average approximating problem is then solved by deterministic optimization techniques, and the process is repeated several times with different samples to obtain candidate solutions along with statistical estimates of their optimality gaps until a stopping criterion is satisfied. In section 1 expected value and sample average approximation problems are formally described and some interesting properties are given. In section 2 a statistical inference of the sample average approximation method is discussed; convergence rates of objetive values and solutions of such problem are established as well as asymptotic properties of sample objective values. In section 3 we outline an algorithm design for the sample average approximation approach to solve the expected value problem and in particular we discuss various stopping rules. In the last section several applications of the method are presented. First a knapsack problem is described where the capacity of the knapsack is given and the size of each item is modeled as a random variable, for this reason the problem is called the static stochastic knapsack problem. In the second application, the quality of the approximate solution obtained from sample average approximations for a two-stage stochastic linear program with recourse is studied. In the next application, the problem of detecting a virus that spreads throughtout a contact network with a stochastic behavior is examined. Finally, in the last application, a sample average approximation method for the disassembly line balancing problem under uncertainty is described.