Publication Type
Journal Article
Version
acceptedVersion
Publication Date
11-2021
Abstract
We consider a multistage stochastic discrete program in which constraints on any stage might 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 at each stage, a number of scenarios are examined and a number of simulation replications are performed for each scenario to estimate the next-stage constraints. This approach provides an approximate solution to the multistage problem. To establish the consistency of the SAA approach, we first consider a two-stage problem and 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. These convergence results do not hold uniformly over all possible scenarios for the second stage problem. 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. We also prove exponential convergence of the probability of a large deviation for the optimal value of the SAA, the true value of an optimal solution of the SAA, and the probability that any optimal solution to the SAA is an optimal solution of the true problem. All of these results can be extended to a multistage setting and we explain how to do it. Our framework and SAA results cover a large variety of resource allocation problems for which at each stage after the first one, new information becomes available and the allocation can be readjusted, under constraints that involve expectations estimated by Monte Carlo. 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 later stages.
Keywords
Sample average approximation, Multistage stochastic program, Expected value constraints, Convergence rate, Staffing optimization
Discipline
Databases and Information Systems | Numerical Analysis and Scientific Computing | Theory and Algorithms
Research Areas
Intelligent Systems and Optimization
Publication
Mathematical Programming
Volume
190
Issue
1-2
First Page
1
Last Page
37
ISSN
0025-5610
Identifier
10.1007/s10107-020-01518-w
Publisher
Springer Verlag (Germany)
Citation
TA, Thuy Anh; MAI, Tien; BASTIN, Fabian; and L'ECUYER, Pierre.
On a multistage discrete stochastic optimization problem with stochastic constraints and nested sampling. (2021). Mathematical Programming. 190, (1-2), 1-37.
Available at: https://ink.library.smu.edu.sg/sis_research/5281
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1007/s10107-020-01518-w
Included in
Databases and Information Systems Commons, Numerical Analysis and Scientific Computing Commons, Theory and Algorithms Commons