Relaxations and approximations of chance constraints under finite distributions. (English) Zbl 1391.90422
Summary: Optimization problems with constraints involving stochastic parameters that are required to be satisfied with a prespecified probability threshold arise in numerous applications. Such chance constrained optimization problems involve the dual challenges of stochasticity and nonconvexity. In the setting of a finite distribution of the stochastic parameters, an optimization problem with linear chance constraints can be formulated as a mixed integer linear program (MILP). The natural MILP formulation has a weak relaxation bound and is quite difficult to solve. In this paper, we review some recent results on improving the relaxation bounds and constructing approximate solutions for MILP formulations of chance constraints. We also discuss a recently introduced bicriteria approximation algorithm for covering type chance constrained problems. This algorithm uses a relaxation to construct a solution whose (constraint violation) risk level may be larger than the pre-specified threshold, but is within a constant factor of it, and whose objective value is also within a constant factor of the true optimal value. Finally, we present some new results that improve on the bicriteria approximation factors in the finite scenario setting and shed light on the effect of strong relaxations on the approximation ratios.
References:
| [1] | Abdi, A; Fukasawa, R, On the mixing set with a knapsack constraint, Math. Program., 157, 191-217, (2016) · Zbl 1354.90076 · doi:10.1007/s10107-016-0979-5 |
| [2] | Ahmed, S; Luedtke, J; Song, Y; Xie, W, Nonanticipative duality, relaxations, and formulations for chance-constrained stochastic programs, Math. Program., 162, 51-81, (2017) · Zbl 1358.90080 · doi:10.1007/s10107-016-1029-z |
| [3] | Ahmed, S; Shapiro, A, Solving chance-constrained stochastic programs via sampling and integer programming, Tutor. Oper. Res. (INFORMS), 10, 261-269, (2008) |
| [4] | Alexander, GJ; Baptista, AM, A comparison of var and CVaR constraints on portfolio selection with the mean-variance model, Manag. Sci., 50, 1261-1273, (2004) · doi:10.1287/mnsc.1040.0201 |
| [5] | Atamtürk, A; Nemhauser, GL; Savelsbergh, MWP, The mixed vertex packing problem, Math. Program., 89, 35-53, (2000) · Zbl 1033.90095 · doi:10.1007/s101070000154. |
| [6] | Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009) · Zbl 1221.90001 · doi:10.1515/9781400831050 |
| [7] | Beraldi, P; Ruszczyński, A, A branch and bound method for stochastic integer problems under probabilistic constraints, Optim. Methods Softw., 17, 359-382, (2002) · Zbl 1064.90030 · doi:10.1080/1055678021000033937 |
| [8] | Bienstock, D; Chertkov, M; Harnett, S, Chance-constrained optimal power flow: risk-aware network control under uncertainty, SIAM Rev., 56, 461-495, (2014) · Zbl 1301.93095 · doi:10.1137/130910312 |
| [9] | Calafiore, GC; Campi, MC, Uncertain convex programs: randomized solutions and confidence levels, Math. Program., 102, 25-46, (2005) · Zbl 1177.90317 · doi:10.1007/s10107-003-0499-y |
| [10] | Calafiore, GC; Campi, MC, The scenario approach to robust control design, IEEE Trans. Autom. Control, 51, 742-753, (2006) · Zbl 1366.93457 · doi:10.1109/TAC.2006.875041 |
| [11] | Charnes, A; Cooper, WW; Symonds, GH, 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 |
| [12] | Deng, Y; Shen, S, Decomposition algorithm for optimizing multi-server appointment scheduling with chance constraints, Math. Program., 157, 245-276, (2016) · Zbl 1347.90062 · doi:10.1007/s10107-016-0990-x |
| [13] | Dentcheva, D; Prékopa, A; Ruszczynski, A, Concavity and efficient points of discrete distributions in probabilistic programming, Math. Program., 89, 55-77, (2000) · Zbl 1033.90078 · doi:10.1007/PL00011393 |
| [14] | Goyal, V., Ravi, R.: Approximation algorithms for robust covering problems with chance constraints. http://repository.cmu.edu/cgi/viewcontent.cgi?article=1365&context=tepper (2008) · Zbl 0998.90076 |
| [15] | Goyal, V; Ravi, R, A PTAS for the chance-constrained knapsack problem with random item sizes, Oper. Res. Lett., 38, 161-164, (2010) · Zbl 1187.90232 · doi:10.1016/j.orl.2010.01.003 |
| [16] | Guan, Y; Ahmed, S; Nemhauser, GL, Sequential pairing of mixed integer inequalities, Discrete Optim., 4, 21-39, (2007) · Zbl 1188.90183 · doi:10.1016/j.disopt.2006.10.003 |
| [17] | Günlük, O; Pochet, Y, Mixing mixed-integer inequalities, Math. Program., 90, 429-457, (2001) · Zbl 1041.90033 · doi:10.1007/PL00011430 |
| [18] | Küçükyavuz, S, On mixing sets arising in chance-constrained programming, Math. Program., 132, 31-56, (2012) · Zbl 1262.90110 · doi:10.1007/s10107-010-0385-3 |
| [19] | Lejeune, MA; Margot, F, Solving chance-constrained optimization problems with stochastic quadratic inequalities, Oper. Res., 64, 939-957, (2016) · Zbl 1348.90504 · doi:10.1287/opre.2016.1493 |
| [20] | Liu, X., Kılınç-Karzan, F., Küçükyavuz, S.: On intersection of two mixing sets with applications to joint chance-constrained programs. Math. Program. (2018). https://doi.org/10.1007/s10107-018-1231-2 · Zbl 0672.60032 |
| [21] | Liu, X; Küçükyavuz, S; Luedtke, J, Decomposition algorithms for two-stage chance-constrained programs, Math. Program., 157, 219-243, (2016) · Zbl 1338.90284 · doi:10.1007/s10107-014-0832-7 |
| [22] | Luedtke, J, A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support, Math. Program., 146, 219-244, (2014) · Zbl 1297.90092 · doi:10.1007/s10107-013-0684-6 |
| [23] | Luedtke, J; Ahmed, S, A sample approximation approach for optimization with probabilistic constraints, SIAM J. Optim., 19, 674-699, (2008) · Zbl 1177.90301 · doi:10.1137/070702928 |
| [24] | Luedtke, J; Ahmed, S; Nemhauser, GL, An integer programming approach for linear programs with probabilistic constraints, Math. Program., 122, 247-272, (2010) · Zbl 1184.90115 · doi:10.1007/s10107-008-0247-4 |
| [25] | Miller, AJ; Wolsey, LA, Tight formulations for some simple mixed integer programs and convex objective integer programs, Math. Program., 98, 73-88, (2003) · Zbl 1047.90035 · doi:10.1007/s10107-003-0397-3 |
| [26] | Nemirovski, A, On safe tractable approximations of chance constraints, Eur. J. Oper. Res., 219, 707-718, (2012) · Zbl 1253.90185 · doi:10.1016/j.ejor.2011.11.006 |
| [27] | Nemirovski, A; Shapiro, A; Calafiore, G (ed.); Dabbene, F (ed.), Scenario approximation of chance constraints, 3-48, (2005), London |
| [28] | Nemirovski, A; Shapiro, A, Convex approximations of chance constrained programs, SIAM J. Optim., 17, 969-996, (2006) · Zbl 1126.90056 · doi:10.1137/050622328 |
| [29] | Pagnoncelli, BK; Ahmed, S; Shapiro, A, Sample average approximation method for chance constrained programming: theory and applications, J. Optim. Theory Appl., 142, 399-416, (2009) · Zbl 1175.90306 · doi:10.1007/s10957-009-9523-6 |
| [30] | Pagnoncelli, BK; Ahmed, S; Shapiro, A, Computational study of a chance constrained portfolio selection problem, J. Optim. Theory Appl., 142, 399-416, (2009) · Zbl 1175.90306 · doi:10.1007/s10957-009-9523-6 |
| [31] | Pavlikov, K; Veremyev, A; Pasiliao, EL, Optimization of value-at-risk: computational aspects of mip formulations, J. Oper. Res. Soc., 69, 127-141, (2018) · doi:10.1057/s41274-017-0197-4 |
| [32] | Pinter, J, Deterministic approximations of probability inequalities, ZOR Methods Models Oper. Res., 33, 219-239, (1989) · Zbl 0672.60032 · doi:10.1007/BF01423332 |
| [33] | Prékopa, A.: Stochastic Programming. Springer, Berlin (1995) · Zbl 0863.90116 · doi:10.1007/978-94-017-3087-7 |
| [34] | Qiu, F; Ahmed, S; Dey, SS; Wolsey, LA, Covering linear programming with violations, INFORMS J. Comput., 26, 531-546, (2014) · Zbl 1304.90139 · doi:10.1287/ijoc.2013.0582 |
| [35] | Rockafellar, RT; Uryasev, S, Optimization of conditional value-at-risk, J. Risk, 2, 21-42, (2000) · doi:10.21314/JOR.2000.038 |
| [36] | Schneider, R.: Convex Bodies: The Brunn-Minkowski Theory, vol. 151. Cambridge University Press, Cambridge (2013) · Zbl 1287.52001 |
| [37] | Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming: Modeling and Theory, vol. 9. SIAM, Philadelphia (2009) · Zbl 1183.90005 · doi:10.1137/1.9780898718751 |
| [38] | Shiina, T, Numerical solution technique for joint chance-constrained programming problem: an application to electric power capacity expansion, J. Oper. Res. Soc. Jpn., 42, 128-140, (1999) · Zbl 0998.90076 |
| [39] | Snyder, L.V., Daskin, M.S: Models for reliable supply chain network design. In: Murray, A.T., Grubesic, T.H. (eds.) Critical Infrastructure, pp. 257-289. Springer, Berlin (2007) · Zbl 1347.90062 |
| [40] | Song, Y; Luedtke, J; Küçükyavuz, S, Chance-constrained binary packing problems, INFORMS J. Comput., 26, 735-747, (2014) · Zbl 1304.90179 · doi:10.1287/ijoc.2014.0595 |
| [41] | Swamy, C.: Risk-averse stochastic optimization: probabilistically-constrained models and algorithms for black-box distributions. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 1627-1646. SIAM (2011) · Zbl 1377.90062 |
| [42] | Takyi, AK; Lence, BJ, Surface water quality management using a multiple-realization chance constraint method, Water Resour. Res., 35, 1657-1670, (1999) · doi:10.1029/98WR02771 |
| [43] | Talluri, S; Narasimhan, R; Nair, A, Vendor performance with supply risk: a chance-constrained dea approach, Int. J. Prod. Econ., 100, 212-222, (2006) · doi:10.1016/j.ijpe.2004.11.012 |
| [44] | van Ackooij, W., Zorgati, R., Henrion, R., Möller, A.: Chance constrained programming and its applications to energy management. In: Dritsas I. (ed.) Stochastic Optimization—Seeing the Optimal for the Uncertain. InTech (2011) · Zbl 1064.90030 |
| [45] | Xie, W., Ahmed, S.: Bicriteria approximation of chance constrained covering problems. Submitted for publication, Preprint available at Optimization Online (2018) |
| [46] | Xie, W; Ahmed, S, Distributionally robust chance constrained optimal power flow with renewables: a conic reformulation, IEEE Trans. Power Syst., 33, 1860, (2018) · doi:10.1109/TPWRS.2017.2725581 |
| [47] | Xie, W., Ahmed, S.: On quantile cuts and their closure for chance constrained optimization problems. Math. Program. (2017). https://doi.org/10.1007/s10107-017-1190-z · Zbl 1412.90096 |
| [48] | Zhang, M; Küçükyavuz, S; Goel, S, A branch-and-cut method for dynamic decision making under joint chance constraints, Manag. Sci., 60, 1317-1333, (2014) · doi:10.1287/mnsc.2013.1822 |
| [49] | Zhao, M; Huang, K; Zeng, B, A polyhedral study on chance constrained program with random right-hand side, Math. Program., 166, 19-64, (2017) · Zbl 1386.90089 · doi:10.1007/s10107-016-1103-6 |
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.
