×

Chance-constrained problems and rare events: an importance sampling approach. (English) Zbl 1356.90093

The authors consider chance-constrained optimization problems with rare events, that is, problems in which the violation probability is very small, e.g. \(10^{-6}\). They propose an integration of SAA (sample average approximation approach) with importance sampling (IS), a technique widely used in simulation to estimate probabilities of rare events. Also, they give sufficient conditions to obtain a uniform variance reduction, and prove asymptotic convergence of the combined SAA-IS approach. The authors describe in detail the telecommunication problem with Bernoulli input distributions and present explicit mixed integer programming formulations for the rare-event chance-constrained problem with importance sampling. In the last part of the paper numerical results are presented and concluding remarks are discussed.

MSC:

90C15 Stochastic programming
65C05 Monte Carlo methods
68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adas, A.: Traffic models in broadband networks. IEEE Commun. Mag. 35(7), 82-89 (1997) · doi:10.1109/35.601746
[2] Andrieu, L., Henrion, R., Römisch, W.: A model for dynamic chance constraints in hydro power reservoir management. Eur. J. Oper. Res. 207(2), 579-589 (2010) · Zbl 1205.90145 · doi:10.1016/j.ejor.2010.05.013
[3] Artstein, Z., Wets, R.J.B.: Consistency of minimizers and the SLLN for stochastic programs. J. Convex Anal. 2(1-2), 1-17 (1996) · Zbl 0837.90093
[4] Asmussen, S., Glynn, P.: Stochastic Simulation. Springer, New York (2007) · Zbl 1126.65001
[5] Beraldi, P., Ruszczyński, A.: The probabilistic set-covering problem. Oper. Res. 50(6), 956-967 (2002) · Zbl 1163.90655 · doi:10.1287/opre.50.6.956.345
[6] Bonami, P., Lejeune, M.: An exact solution approach for portfolio optimization problems under stochastic and integer constraints. Oper. Res. 57(3), 650-670 (2009) · Zbl 1226.90049 · doi:10.1287/opre.1080.0599
[7] Calafiore, G., Campi, M.C.: Uncertain convex programs: randomized solutions and confidence levels. Math. Program. 102(1), 25-46 (2005) · Zbl 1177.90317 · doi:10.1007/s10107-003-0499-y
[8] Campi, M.C., Garatti, S.: The exact feasibility of randomized solutions of uncertain convex programs. SIAM J. Optim. 19(3), 1211-1230 (2008) · Zbl 1180.90235 · doi:10.1137/07069821X
[9] Campi, M.C., Garatti, S.: A sampling-and-discarding approach to chance-constrained optimization: feasibility and optimality. J. Optim. Theory Appl. 148(2), 257-280 (2011) · Zbl 1211.90146 · doi:10.1007/s10957-010-9754-6
[10] Campi, M.C., Garatti, S., Prandini, M.: The scenario approach for systems and control design. Ann. Rev. Control 33(2), 149-157 (2009) · doi:10.1016/j.arcontrol.2009.07.001
[11] Carniato, A., Camponogara, E.: Integrated coal-mining operations planning: modeling and case study. Int. J. Coal Prep. Util. 31(6), 299-334 (2011) · doi:10.1080/19392699.2011.576656
[12] Charnes, A., Cooper, W.W., Symonds, G.H.: Cost horizons and certainty equivalents: an approach to stochastic programming of heating oil. Manag. Sci. 4, 235-263 (1958) · doi:10.1287/mnsc.4.3.235
[13] Chung, K.L.: A Course in Probability Theory, 2nd edn. Academic Press, New York (1974) · Zbl 0345.60003
[14] Dantzig, G.B., Glynn, P.W.: Parallel processors for planning under uncertainty. Ann. Oper. Res. 22(1), 1-21 (1990) · Zbl 0714.90074 · doi:10.1007/BF02023045
[15] Dentcheva, D., Prékopa, A., Ruszczynski, A.: Concavity and efficient points of discrete distributions in probabilistic programming. Math. Program. 89(1), 55-77 (2000) · Zbl 1033.90078 · doi:10.1007/PL00011393
[16] Dorfleitner, G., Utz, S.: Safety first portfolio choice based on financial and sustainability returns. Eur. J. Oper. Res. 221(1), 155-164 (2012) · Zbl 1253.91165 · doi:10.1016/j.ejor.2012.02.034
[17] Duckett, W.: Risk analysis and the acceptable probability of failure. Struct. Eng. 83(15), 25-26 (2005)
[18] Ermoliev, Y.M., Ermolieva, T.Y., MacDonald, G., Norkin, V.: Stochastic optimization of insurance portfolios for managing exposure to catastrophic risks. Ann. Oper. Res. 99(1-4), 207-225 (2000) · Zbl 0990.90084 · doi:10.1023/A:1019244405392
[19] Henrion, R., Römisch, W.: Metric regularity and quantitative stability in stochastic programs with probabilistic constraints. Math. Program. 84(1), 55-88 (1999) · Zbl 1050.90534
[20] Homem-de-Mello, T., Bayraksan, G.: Monte Carlo methods for stochastic optimization. Surv. Oper. Res. Manag. Sci. 19(1), 56-85 (2014)
[21] Infanger, G.: Monte Carlo (importance) sampling within a Benders decomposition algorithm for stochastic linear programs. Ann. Oper. Res. 39(1), 69-95 (1992) · Zbl 0773.90054 · doi:10.1007/BF02060936
[22] Jiang, R., Guan, Y.: Data-driven chance constrained stochastic program (2012). http://www.optimization-online.org · Zbl 1346.90640
[23] Kahn, H., Harris, T.: Estimation of particle transmission by random sampling. Nat. Bur. Stand. Appl. Math. Ser. 12, 27-30 (1951)
[24] L’Ecuyer, P., Mandjes, M., Tuffin, B.: Importance sampling in rare event simulation. In: Rubino, G., Tuffin, B., (eds.) Rare Event Simulation using Monte Carlo Methods, Chap. 2. Wiley, New York (2009) · Zbl 1165.62027
[25] Lejeune, M.: Pattern definition of the p-efficiency concept. Ann. Oper. Res. 200(1), 23-36 (2012) · Zbl 1261.90032 · doi:10.1007/s10479-010-0803-1
[26] Li, W.L., Zhang, Y., So, A.C., Win, Z.: Slow adaptive OFDMA systems through chance constrained programming. IEEE Trans. Signal Process. 58(7), 3858-3869 (2010) · Zbl 1392.94304 · doi:10.1109/TSP.2010.2046434
[27] Liu, Y., Guo, H., Zhou, F., Qin, X., Huang, K., Yu, Y.: Inexact chance-constrained linear programming model for optimal water pollution management at the watershed scale. J. Water Resour. Plan. Manag. 134(4), 347-356 (2008) · doi:10.1061/(ASCE)0733-9496(2008)134:4(347)
[28] Luedtke, J., Ahmed, S.: A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19(2), 674-699 (2008) · Zbl 1177.90301 · doi:10.1137/070702928
[29] Minoux, M.: Discrete cost multicommodity network optimization problems and exact solution methods. Ann. Oper. Res. 106(1-4), 19-46 (2001) · Zbl 1015.90013 · doi:10.1023/A:1014554606793
[30] Minoux, M.: Multicommodity network flow models and algorithms in telecommunications. In: Resende, M., Pardalos, P. (eds.) Handbook of Optimization in Telecommunications, pp. 163-184. Springer, Berlin (2006) · Zbl 1118.90022
[31] Nemirovski, A., Shapiro, A.: Convex approximations of chance constrained programs. SIAM J. Optim. 17(4), 969-996 (2006) · Zbl 1126.90056 · doi:10.1137/050622328
[32] Pagnoncelli, B., Ahmed, S., Shapiro, A.: Sample average approximation method for chance constrained programming: theory and applications. J. Optim. Theory Appl. 142(2), 399-416 (2009) · Zbl 1175.90306 · doi:10.1007/s10957-009-9523-6
[33] Pagnoncelli, B.K., Reich, D., Campi, M.C.: Risk-return trade-off with the scenario approach in practice: a case study in portfolio selection. J. Optim. Theory Appl. 155(2), 707-722 (2012) · Zbl 1257.90089 · doi:10.1007/s10957-012-0074-x
[34] Prékopa, A.: Probabilistic programming. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming, vol. 10, pp. 267-351. Elsevier, Amsterdam (2004)
[35] Ramaswami, R., Sivarajan, K., Sasaki, G.: Optical Networks: A Practical Perspective. Morgan Kaufmann, Los Altos (2009)
[36] Rockafellar, R.T., Wets, R.J.B.: Variational Analysis, A Series of Comprehensive Studies in Mathematics, vol. 317. Springer, Berlin (1998)
[37] Römisch, W., Schultz, R.: Stability analysis for stochastic programs. Ann. Oper. Res. 30(1), 241-266 (1991) · Zbl 0748.90047 · doi:10.1007/BF02204819
[38] Rosenbluth, M.N., Rosenbluth, A.W.: Monte Carlo calculation of the average extension of molecular chains. J. Chem. Phys. 23, 356 (1955) · doi:10.1063/1.1741967
[39] Rubinstein, R.Y.: Cross-entropy and rare events for maximal cut and partition problems. ACM Trans. Model. Comput. Simul. 12(1), 27-53 (2002) · Zbl 1390.90482 · doi:10.1145/511442.511444
[40] Rubinstein, R.Y., Shapiro, A.: Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method. Wiley, Chichester (1993) · Zbl 0805.93002
[41] Shapiro, A.; Ruszczynski, A. (ed.); Shapiro, A. (ed.), Monte Carlo sampling methods, No. 10 (2003), Amsterdam · Zbl 1053.90103
[42] Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on stochastic programming: modeling and theory, vol. 9. SIAM (2009) · Zbl 1183.90005
[43] Soekkha, H.M.: Aviation Safety: Human Factors, System Engineering, Flight Operations, Economics, Strategies, Management. VSP, Utrecht (1997)
[44] Thieu, Q.T., Hsieh, H.Y.: Use of chance-constrained programming for solving the opportunistic spectrum sharing problem under rayleigh fading. In: 9th International Wireless Communications and Mobile Computing Conference (IWCMC), pp. 1792-1797 (2013)
[45] Tran, Q.K., Parpas, P., Rustem, B., Ustun, B., Webster, M.: Importance sampling in stochastic programming: a Markov chain Monte Carlo approach (2013). http://www.optimization-online.org · Zbl 1329.90095
[46] Vallejos, R., Zapata-Beghelli, A., Albornoz, V., Tarifeño, M.: Joint routing and dimensioning of optical burst switching networks. Photon Netw. Commun. 17(3), 266-276 (2009) · doi:10.1007/s11107-008-0161-y
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.