×

On a multistage discrete stochastic optimization problem with stochastic constraints and nested sampling. (English) Zbl 1489.65011

Summary: 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.

MSC:

65C05 Monte Carlo methods
90C15 Stochastic programming

Software:

SSJ; ContactCenters
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ahmed, S., Shapiro, A.: Solving chance-constrained stochastic programs via sampling and integer programming. In: Tutorials in Operations Research, INFORMS, pp 261-269 (2008)
[2] Atlason, J.; Epelman, MA; Henderson, SG, Call center staffing with simulation and cutting plane methods, Ann. Oper. Res., 127, 333-358 (2004) · Zbl 1116.90342
[3] Atlason, J.; Epelman, MA; Henderson, SG, Optimizing call center staffing using simulation and analytic center cutting plane methods, Manag. Sci., 54, 2, 295-309 (2008) · Zbl 1232.90266
[4] Avramidis, AN; Deslauriers, A.; L’Ecuyer, P., Modeling daily arrivals to a telephone call center, Manag. Sci., 50, 7, 896-908 (2004) · Zbl 1232.90268
[5] Avramidis, AN; Chan, W.; Gendreau, M.; L’Ecuyer, P.; Pisacane, O., Optimizing daily agent scheduling in a multiskill call centers, Euro. J. Oper. Res., 200, 3, 822-832 (2010) · Zbl 1177.90262
[6] Bassamboo, A.; Harrison, JM; Zeevi, A., Design and control of a large call center: Asymptotic analysis of an LP-based method, Oper. Res., 54, 3, 419-435 (2006) · Zbl 1167.90528
[7] Bastin, F.; Cirillo, C.; Toint, PhL, Convergence theory for nonconvex stochastic programming with an application to mixed logit, Math. Program. Ser. B, 108, 2-3, 207-234 (2006) · Zbl 1130.90371
[8] Bertsekas, D.P.: Dynamic Programming and Optimal Control, vol. II, 4th edn. Athena Scientific, Belmont, Mass (2012) · Zbl 1298.90001
[9] Bertsekas, D.P.: Dynamic Programming and Optimal Control, vol. I, 4th edn. Athena Scientific, Belmont, Mass (2017) · Zbl 1375.90299
[10] Birge, JR; Louveaux, F., Introduction to Stochastic Programming (2011), New York: Springer, New York · Zbl 1223.90001
[11] Buist, E., L’Ecuyer, P.: A Java library for simulating contact centers. In: Kuhl ME, Steiger NM, Armstrong FB, Joines JA (eds) Proceedings of the 2005 Winter Simulation Conference, IEEE Press, pp 556-565 (2005)
[12] Buist, E., L’Ecuyer, P.: ContactCenters: A Java Library for Simulating Contact Centers. Software user’s guide, available at http://simul.iro.umontreal.ca/contactcenters (2012)
[13] Cez̧ik MT, L’Ecuyer P, : Staffing multiskill call centers via linear programming and simulation. Manag. Sci. 54(2), 310-323 (2008) · Zbl 1232.90301
[14] Chan, W., Ta T.A., L’Ecuyer, P., Bastin, F.: Chance-constrained staffing with recourse for multi-skill call centers with arrival-rate uncertainty. In: Proceedings of the 2014 Winter Simulation Conference, IEEE Press, pp 4103-4104 (2014)
[15] Chan, W., Ta, T.A., L’Ecuyer, P., Bastin, F.: Two-stage chance-constrained staffing with agent recourse for multi-skill call centers. In: Proceedings of the 2016 Winter Simulation Conference, IEEE Press, Piscataway, NJ, USA, pp 3189-3200 (2016)
[16] Dai, L.; Chen, CH; Birge, JR, Convergence properties of two-stage stochastic programming, J. Optim. Theory Appl., 106, 3, 489-509 (2000) · Zbl 0980.90057
[17] Defraeye, M.; Van Nieuwenhuyse, I., Staffing and scheduling under nonstationary demand for service: A literature review, Omega, 58, 4-25 (2016) · Zbl 1349.90546 · doi:10.1016/j.omega.2015.04.002
[18] Dempster, MAH; Fisher, ML; Jansen, L.; Lageweg, BJ; Lenstra, JK; Rinnooy Kan, AHG, Analytical evaluation of hierarchical planning systems, Oper. Res., 29, 4, 707-716 (1981) · Zbl 0464.90039
[19] Dupačová, J., Wets, R.: Asymptotic behavior of statistical estimators and of optimal solutions of stochastic optimization problems. Ann. Stat. pp 1517-1549 (1988) · Zbl 0667.62018
[20] Dussault, JP; Labrecque, D.; L’Ecuyer, P.; Rubinstein, R., Combining the stochastic counterpart and stochastic approximation methods, Discrete Event Dyn. Syst. Theory Appl., 7, 1, 5-28 (1997) · Zbl 0870.93052
[21] Gans, N.; Koole, G.; Mandelbaum, A., Telephone call centers: tutorial, review, and research prospects, Manuf. Serv. Oper. Manag., 5, 79-141 (2003)
[22] Gans, N.; Shen, H.; Zhou, YP; Korolev, N.; McCord, A.; Ristock, H., Parametric forecasting and stochastic programming models for call-center workforce scheduling, Manuf. Serv. Oper. Manag., 17, 4, 571-588 (2015)
[23] Gurvich, I.; Luedtke, J.; Tezcan, T., Staffing call centers with uncertain demand forecasts: A chance-constrained optimization approach, Manag. Sci., 56, 7, 1093-1115 (2010) · Zbl 1232.90278
[24] Haneveld, W.K.K., van der Vlerk, M.H.: Optimizing electricity distribution using two-stage integer recourse models. In: Stochastic optimization: Algorithms and applications, Springer, pp 137-154 (2001) · Zbl 0984.90026
[25] Harrison, JM; Zeevi, A., A method for staffing large call centers based on stochastic fluid models, Manuf. Serv. Oper. Manag., 7, 1, 20-36 (2005)
[26] Helber, S.; Henken, K., Profit-oriented shift scheduling of inbound contact centers with skills-based routing, impatient customers, and retrials, OR Spectr., 32, 109-134 (2010) · Zbl 1181.90179
[27] Hoeffding, W., Probability inequalities for sums of bounded random variables, J. Am. Stat. Assoc., 58, 13-29 (1963) · Zbl 0127.10602
[28] Ibrahim, R., L’Ecuyer, P., Régnard, N., Shen, H.: On the modeling and forecasting of call center arrivals. In: Laroque C, Himmelspach J, Pasupathy R, Rose O, Uhrmacher AM (eds) Proceedings of the 2012 Winter Simulation Conference, IEEE Press, pp 256-267 (2012)
[29] Ibrahim, R.; Ye, H.; L’Ecuyer, P.; Shen, H., Modeling and forecasting call center arrivals: a literature study and a case study, Int. J. Forecast., 32, 3, 865-874 (2016)
[30] Jaoua, A.; L’Ecuyer, P.; Delorme, L., Call type dependence in multiskill call centers, Simulation, 89, 6, 722-734 (2013)
[31] Jouini, O.; Koole, G.; Roubos, A., Performance indicators for call centers with impatient customers, IIE Trans., 45, 3, 341-354 (2013)
[32] Kaniovski, YM; King, AJ; Wets, RJB, Probabilistic bounds (via large deviations) for the solutions of stochastic programming problems, Ann. Oper. Res., 56, 1, 189-208 (1995) · Zbl 0835.90055
[33] Kim, K.; Mehrotra, S., A two-stage stochastic integer programming approach to integrated staffing and scheduling with application to nurse management, Oper. Res., 63, 6, 1431-1451 (2015) · Zbl 1334.90092
[34] Kim, S.; Pasupathy, R.; Henderson, SG; Fu, MC, A guide to sample average approximation, Handbook of Simulation Optimization, 207-243 (2015), New York: Springer, New York
[35] Kleywegt, AJ; Shapiro, A.; Homem-de Mello, T., The sample average approximation method for stochastic discrete optimization, SIAM J. Optim., 12, 2, 479-502 (2002) · Zbl 0991.90090
[36] Koole, G., Call Center Optimization (2013), Amsterdam: MG books, Amsterdam
[37] Kushner, HJ; Clark, DS, Stochastic Approximation Methods for Constrained and Unconstrained Systems, Applied Mathematical Sciences (1978), Berlin: Springer, Berlin · Zbl 0381.60004
[38] Lan, G.; Zhou, Z., Algorithms for stochastic optimization with function or expectation constraints, Comput. Optim. Appl., 76, 461-498 (2020) · Zbl 1443.90263 · doi:10.1007/s10589-020-00179-x
[39] Laporte, G.; Louveaux, F.; Mercure, H., The vehicle routing problem with stochastic travel times, Trans. sci., 26, 3, 161-170 (1992) · Zbl 0761.90035
[40] L’Ecuyer, P.; Yin, G., Budget-dependent convergence rate for stochastic approximation, SIAM J. Optim., 8, 1, 217-247 (1998) · Zbl 0911.60003
[41] L’Ecuyer, P., Meliani, L., Vaucher, J.: SSJ: A framework for stochastic simulation in Java. In: Yücesan E, Chen CH, Snowdon JL, Charnes JM (eds) Proceedings of the 2002 Winter Simulation Conference, IEEE Press, pp 234-242 (2002)
[42] L’Ecuyer, P., Gustavsson, K., Olsson, L.: Modeling bursts in the arrival process to an emergency call center. In: Proceedings of the 2018 Winter Simulation Conference, IEEE Press, pp 525-536 (2018)
[43] Liao, S.; van Delft, C.; Koole, G.; Jouini, O., Staffing a call center with uncertain non-stationary arrival rate and flexibility, OR Spectr., 34, 691-721 (2012) · Zbl 1244.90096
[44] Liao, S.; van Delft, C.; Vial, JP, Distributionally robust workforce scheduling in call centers with uncertain arrival rates, Optim. Methods Softw., 28, 3, 501-522 (2013) · Zbl 1266.90122
[45] Matteson, DS; McLean, MW; Woodard, DB; Henderson, SG, Forecasting emergency medical service call arrival rates, Ann. Appl. Stat., 5, 2, 1379-1406 (2011) · Zbl 1223.62161
[46] Mehrotra, V.; Ozlük, O.; Saltzman, R., Intelligent procedures for intra-day updating of call center agent schedules, Prod. Oper. Manag., 19, 3, 353-367 (2010)
[47] Nedic, A.; Bertsekas, DP, Incremental subgradient methods for nondifferentiable optimization, SIAM J. Optim., 12, 1, 109-138 (2001) · Zbl 0991.90099
[48] Nemirovski, A.; Juditsky, A.; Lan, G.; Shapiro, A., Robust stochastic approximation approach to stochastic programming, SIAM J. Optim., 19, 4, 1574-1609 (2009) · Zbl 1189.90109
[49] Oreshkin, B.; Régnard, N.; L’Ecuyer, P., Rate-based daily arrival process models with application to call centers, Oper. Res., 64, 2, 510-527 (2016) · Zbl 1345.60106
[50] Pichitlamken, J., Deslauriers, A., L’Ecuyer, P., Avramidis, A.N.: Modeling and simulation of a telephone call center. In: Proceedings of the 2003 Winter Simulation Conference, IEEE Press, pp 1805-1812 (2003)
[51] Pillac, V.; Gendreau, M.; Guéret, C.; Medaglia, AL, A review of dynamic vehicle routing problems, Euro. J. Oper. Res., 225, 1, 1-11 (2013) · Zbl 1292.90203
[52] Polyak, BT; Juditsky, AB, Acceleration of stochastic approximation by averaging, SIAM J. Control Optim., 30, 4, 838-855 (1992) · Zbl 0762.62022
[53] Punnakitikashem, P.; Rosenberger, JM; Buckley-Behan, D., Stochastic programming for nurse assignment, Comput. Optim. Appl., 40, 3, 321-349 (2008) · Zbl 1153.90516
[54] Punnakitikashem, P.; Rosenberber, JM; Buckley-Behan, DF, A stochastic programming approach for integrated nurse staffing and assignment, IIE Trans., 45, 10, 1059-1076 (2013)
[55] Robbins, H.; Monro, S., A stochastic approximation method, Ann. Math. Stat., 22, 400-407 (1951) · Zbl 0054.05901
[56] Robbins, TR; Harrison, TP, A stochastic programming model for scheduling call centers with global service level agreements, Euro. J. Oper. Res., 207, 3, 1608-1619 (2010) · Zbl 1206.90052
[57] Robinson, SM, Analysis of sample path optimization, Math. Oper. Res., 21, 513-528 (1996) · Zbl 0868.90087
[58] Rubinstein, RY; Shapiro, A., Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method (1993), New York: Wiley, New York · Zbl 0805.93002
[59] Ruszczyński, A.; Syski, W., On convergence of the stochastic subgradient method with on-line stepsize rules, J. Math. Anal. Appl., 114, 2, 512-527 (1986) · Zbl 0604.90106
[60] Shapiro, A., Asymptotic behavior of optimal solutions in stochastic programming, Math. Oper. Res., 18, 4, 829-845 (1993) · Zbl 0804.90101
[61] Shapiro, A.; Ruszczyński, A.; Shapiro, A., Monte Carlo sampling methods, Stochastic Programming, 353-425 (2003), Amsterdam: Handbooks in Operations Research and Management Science, Elsevier, Amsterdam
[62] Shapiro, A.; de Mello, TH, On rate of convergence of Monte Carlo approximations of stochastic programs, SIAM J. Optim., 11, 1, 70-86 (2000) · Zbl 0999.90023
[63] Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lecture Notes on Stochastic Programming: Modeling and Theory, 2nd edn. Handbooks in Operations Research and Management Science, SIAM, Philadelphia (2014) · Zbl 1302.90003
[64] Stroock, DW, An introduction to the theory of large deviations (1984), New York: Springer, New York · Zbl 0552.60022
[65] Ta, T.A., L’Ecuyer, P., Bastin, F.: Staffing optimization with chance constraints for emergency call centers. In: MOSIM 2016-11th International Conference on Modeling, Optimization and Simulation, see http://www.iro.umontreal.ca/ lecuyer/myftp/papers/mosim16emergency.pdf (2016)
[66] Ta, T.A., Chan, W., Bastin, F., L’Ecuyer, P.: A simulation-based decomposition approach for two-stage staffing optimization in call centers under arrival rate uncertainty. Submitted for publication (2019)
[67] Vogel, S., A stochastic approach to stability in stochastic programming, J. Comput. Appl. Math., 56, 65-96 (1994) · Zbl 0824.90107
[68] Wang, W.; Ahmed, S., Sample average approximation of expected value constrained stochastic programs, Oper. Res. Lett., 36, 515-519 (2008) · Zbl 1210.90131
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.