On a two-stage discrete stochastic optimization problem with stochastic constraints and nested sampling

, , , and

BibTeX reference

We consider a two-stage stochastic discrete program in which some of the second stage constraints involve expectations that cannot be computed easily and are approximated by simulation. We study a sample average approximation (SAA) approach that uses nested sampling, in which a number of second stage scenarios are examined, and a number of simulation replications are performed for each scenario to estimate the second stage constraints. This approach provides an approximate solution to the two-stage problem. We show that in the second-stage problem, given a scenario, the optimal values and solutions of the SAA converge to those of the true problem with probability one when the sample sizes go to infinity. In the two-stage problem, these convergence results of the second-stage problem do not hold uniformly over all possible scenarios, and this complicates convergence proofs. We are nevertheless able to prove that the optimal values and solutions of the SAA converge to the true ones with probability one when the sample sizes at both stages increase to infinity. As an illustration, we apply this SAA method to a staffing problem in a call center, in which the goal is to optimize the numbers of agents of each type under some constraints on the quality of service (QoS). The staffing allocation has to be decided under an uncertain arrival rate with a prior distribution in the first stage, and can be adjusted at some additional cost when better information on the arrival rate becomes available in the second stage.

, 25 pages


G1859.pdf (500 KB)