### G-2018-59

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

## Thuy Anh Ta, Tien Mai, Fabian Bastin, and Pierre L'Ecuyer

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.

Published **August 2018**
,
25 pages