×

A polyhedral study on chance constrained program with random right-hand side. (English) Zbl 1386.90089

Summary: The essential structure of the mixed-integer programming formulation for chance-constrained program (CCP) is the intersection of multiple mixing sets with a 0-1 knapsack. To improve our computational capacity on CCP, an underlying substructure, the (single) mixing set with a 0-1 knapsack, has received substantial attentions recently. In this study, we consider a CCP problem with stochastic right-hand side under a finite discrete distribution. We first present a family of strong inequalities that subsumes known facet-defining ones for that single mixing set. Due to the flexibility of our generalized inequalities, we develop a new separation heuristic that has a complexity much less than existing one and guarantees generated cutting planes are facet-defining for the polyhedron of CCP. Then, we study lifting and superadditive lifting on knapsack cover inequalities, and provide an implementable procedure on deriving another family of strong inequalities for the single mixing set. Finally, different from the traditional approach that aggregates original constraints to investigate polyhedral implications due to their interactions, we propose a novel blending procedure that produces strong valid inequalities for CCP by integrating those derived from individual mixing sets. We show that, under certain conditions, they are the first type of facet-defining inequalities describing intersection of multiple mixing sets, and design an efficient separation heuristic for implementation. In the computational experiments, we perform a systematic study and illustrate the efficiency of the proposed inequalities on solving chance constrained static probabilistic lot-sizing problems.

MSC:

90C11 Mixed integer programming
90C15 Stochastic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdi, A., Fukasawa, R.: On the mixing set with a knapsack constraint. Math. Program. 157(1), 191-217 (2016) · Zbl 1354.90076 · doi:10.1007/s10107-016-0979-5
[2] Adam, L., Branda, M.: Nonlinear chance constrained problems: optimality conditions, regularization and solvers. J. Optim. Theor. Appl. 170(2), 419-436 (2016) · Zbl 1346.90634 · doi:10.1007/s10957-016-0943-9
[3] Atamtürk, A., Nemhauser, G.L., Savelsbergh, M.W.P.: The mixed vertex packing problem. Math. Program. 89(1), 35-53 (2000) · Zbl 1033.90095 · doi:10.1007/s101070000154.
[4] Ben-Tal, A., Nemirovski, A.: Robust solutions of linear programming problems contaminated with uncertain data. Math. Program. 88(3), 411-424 (2000) · Zbl 0964.90025 · doi:10.1007/PL00011380
[5] Beraldi, P., Bruni, M.E., Conforti, D.: Designing robust emergency medical service via stochastic programming. Eur. J. Oper. Res. 158(1), 183-193 (2004) · Zbl 1066.90063 · doi:10.1016/S0377-2217(03)00351-5
[6] Beraldi, P., Ruszczyński, A.: A branch and bound method for stochastic integer programs under probabilistic constraints. Optim. Methods Softw. 17(3), 359-382 (2002) · Zbl 1064.90030 · doi:10.1080/1055678021000033937
[7] 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
[8] Campi, M.C., Garatti, S.: A sampling-and-discarding approach to chance-constrained optimization: feasibility and optimality. J. Optim. Theory App. 148(2), 257-280 (2011) · Zbl 1211.90146 · doi:10.1007/s10957-010-9754-6
[9] Dentcheva, D., Prékopa, A., Ruszczyński, 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
[10] Ehmke, J.F., Campbell, A.M., Urban, T.L.: Ensuring service levels in routing problems with time windows and stochastic travel times. Eur. J. Oper. Res. 240(2), 539-550 (2015) · Zbl 1357.90015 · doi:10.1016/j.ejor.2014.06.045
[11] Gu, Z., Nemhauser, G.L., Savelsbergh, M.W.: Lifted cover inequalities for 0-1 integer programs: computation. INFORMS J. Comp. 10(4), 427-437 (1998) · doi:10.1287/ijoc.10.4.427
[12] Gu, Z., Nemhauser, G.L., Savelsbergh, M.W.: Sequence independent lifting in mixed integer programming. J. Comb. Optim. 4(1), 109-129 (2000) · Zbl 0964.90030 · doi:10.1023/A:1009841107478
[13] Guan, Y., Ahmed, S., Nemhauser, G.L.: Sequential pairing of mixed integer inequalities. Discrete Optim. 4(1), 21-39 (2007) · Zbl 1188.90183 · doi:10.1016/j.disopt.2006.10.003
[14] Günlük, O.; Pochet, Y., No article title, Math. Program., 90, 429-457 (2001) · doi:10.1007/PL00011430
[15] Hanasusanto, G.A., Roitch, V., Kuhn, D., Wiesemann, W.: Ambiguous joint chance constraints under mean and dispersion information. Oper. Res. 62(6), 1358-1376 (2016)
[16] Henrion, R.: Structural properties of linear probabilistic constraints. Optimization 56(4), 425-440 (2007) · Zbl 1149.90110 · doi:10.1080/02331930701421046
[17] Henrion, R., Möller, A.: A gradient formula for linear chance constraints under Gaussian distribution. Math. Oper. Res. 37(3), 475-488 (2012) · Zbl 1297.90095 · doi:10.1287/moor.1120.0544
[18] Henrion, R., Strugarek, C.: Convexity of chance constraints with independent random variables. Comput. Optim. Appl. 41(2), 263-276 (2008) · Zbl 1168.90568 · doi:10.1007/s10589-007-9105-1
[19] High Performance Computing Center. http://www.hpcc.ttu.edu/. Accessed April 2016 · Zbl 0964.90030
[20] Hong, L.J., Yang, Y., Zhang, L.: Sequential convex approximations to joint chance constrained programs: a Monte Carlo approach. Oper. Res. 59(3), 617-630 (2011) · Zbl 1231.90303 · doi:10.1287/opre.1100.0910
[21] Kogan, A., Lejeune, M.: Threshold boolean form for joint probabilistic constraints with random technology matrix. Math. Program. 147(1-2), 391-427 (2014) · Zbl 1297.90101 · doi:10.1007/s10107-013-0728-y
[22] Küçükyavuz, S.: On mixing sets arising in chance-constrained programming. Math. Program. 132(1), 31-56 (2012) · Zbl 1262.90110 · doi:10.1007/s10107-010-0385-3
[23] Küçükyavuz, S., Noyan, N.: Cut generation for optimization problems with multivariate risk constraints. Math. Program. 159(1), 165-199 (2016) · Zbl 1346.90642 · doi:10.1007/s10107-015-0953-7
[24] Lejeune, M.A.: Pattern-based modeling and solution of probabilistically constrained optimization problems. Oper. Res. 60(6), 1356-1372 (2012) · Zbl 1269.90071 · doi:10.1287/opre.1120.1120
[25] Lejeune, M., Noyan, N.: Mathematical programming approaches for generating \[p\] p-efficient points. Eur. J. Oper. Res. 207(2), 590-600 (2010) · Zbl 1205.90210 · doi:10.1016/j.ejor.2010.05.025
[26] Lejeune, M.A., Margot, F.: Solving chance-constrained optimization problems with stochastic quadratic inequalities. Oper. Res. 64(4), 939-957 (2016) · Zbl 1348.90504 · doi:10.1287/opre.2016.1493
[27] Liu, X., Küçükyavuz, S., Luedtke, J.: Decomposition algorithms for two-stage chance-constrained programs. Math. Program. 157(1), 219-243 (2016) · Zbl 1338.90284
[28] Luedtke, J.: A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support. Math. Program. 146(1), 219-244 (2014) · Zbl 1297.90092 · doi:10.1007/s10107-013-0684-6
[29] Luedtke, J., Ahmed, S., Nemhauser, G.: An integer programming approach for linear programs with probabilistic constraints. Math. Program. 122(2), 247-272 (2010) · Zbl 1184.90115 · doi:10.1007/s10107-008-0247-4
[30] Miller, A.J., Wolsey, L.A.: Tight formulations for some simple mixed integer programs and convex objective integer programs. Math. Program. 98(1), 73-88 (2003) · Zbl 1047.90035 · doi:10.1007/s10107-003-0397-3
[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] Prékopa, A.: Dual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution. Z. Oper. Res. 34(6), 441-461 (1990) · Zbl 0724.90048
[33] Prékopa, A.; Ruszczyński, A. (ed.); Shapiro, A. (ed.), Probabilistic programming, No. 10, 267-351 (2003), Amsterdam
[34] Qiu, F., Shabbir, A., Dey, S.D., Wolsey, L.A.: Covering linear programming with violations. INFORMS J. Comp. 26(3), 531-546 (2014) · Zbl 1304.90139 · doi:10.1287/ijoc.2013.0582
[35] Rockafellar, R.T., Uryasev, S.: Optimization of conditional valueat-risk. J. Risk 2(3), 21-41 (2000) · doi:10.21314/JOR.2000.038
[36] Ruszczyński, A.: Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra. Math. Program. 93(2), 195-215 (2002) · Zbl 1065.90058 · doi:10.1007/s10107-002-0337-7
[37] Saxena, A., Goyal, V., Lejeune, M.A.: MIP reformulations of the probabilistic set covering problem. Math. Program. 121(1), 1-31 (2010) · Zbl 1184.90116 · doi:10.1007/s10107-008-0224-y
[38] Sen, S.: Relaxations for probabilistically constrained programs with discrete random variables. Oper. Res. Lett. 11(2), 81-86 (1992) · Zbl 0765.90071 · doi:10.1016/0167-6377(92)90037-4
[39] Tanner, N.W., Ntaimo, L.: IIS branch-and-cut for joint chance-constrained stochastic programs and application to optimal vaccine allocation. Eur. J. Oper. Res. 207(1), 290-296 (2010) · Zbl 1205.90211 · doi:10.1016/j.ejor.2010.04.019
[40] van Ackooij, W., Berge, V., De Oliveira, W., Sagastizabal, C.: Probabilistic optimization via approximate p-efficient points and bundle methods. Comput. Oper. Res. 77, 177-193 (2017) · Zbl 1391.90450 · doi:10.1016/j.cor.2016.08.002
[41] van Ackooij, W., Henrion, R.: Gradient formulae for nonlinear probabilistic constraints with Gaussian and Gaussian-like distributions. SIAM J. Optim. 24, 1864-1889 (2014) · Zbl 1319.93080 · doi:10.1137/130922689
[42] van Ackooij, W., Henrion, R., Mller, A., Zorgati, R.: On joint probabilistic constraints with Gaussian coefficient matrix. Oper. Res. Lett. 39(2), 99-102 (2011) · Zbl 1218.90147 · doi:10.1016/j.orl.2011.01.005
[43] van Ackooij, W., Henrion, R., Möller, A., Zorgati, R.: Joint chance constrained programming for hydro reservoir management. Optim. Eng. 15(2), 509-531 (2014) · Zbl 1364.90232
[44] van Ackooij, W., Sagastizábal, C.: Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems. SIAM J. Optim. 24(2), 733-765 (2014) · Zbl 1297.49057 · doi:10.1137/120903099
[45] Wang, J., Shen, S.: Risk and energy consumption tradeoffs in cloud computing service via stochastic optimization models. In: Proceedings of the 5th IEEE/ACM International Conference on Utility and Cloud Computing (UCC 2012). Chicago, Illinois (2012) · Zbl 1346.90634
[46] Zemel, E.: Easily computable facets of the knapsack polytope. Math. Oper. Res. 14(4), 760-764 (1989) · Zbl 0689.90057 · doi:10.1287/moor.14.4.760
[47] Zeng, B., An, Y., Kuznia, L.: Chance constrained mixed integer program: Bilinear and linear formulations, and Benders decomposition. Optimization Online (2014). arXiv:1403.7875v2 · Zbl 1218.90147
[48] Zhang, M., Küçükyavuz, S., Goel, S.: A branch-and-cut method for dynamic decision making under joint chance constraints. Manag. Sci. 60(5), 1317-1333 (2014) · doi:10.1287/mnsc.2013.1822
[49] Zhao, M., de Farias Jr, I.R.: The mixing-MIR set with divisible capacities. Math. Program. 115(1), 73-103 (2008) · Zbl 1176.90433 · doi:10.1007/s10107-007-0140-6
[50] Zhao, M., de Farias Jr, I.R.: A note on the continuous mixing set. Oper. Res. Lett. 36(6), 726-733 (2008) · Zbl 1165.90581 · doi:10.1016/j.orl.2008.08.001
[51] Zhao, M., Huang, K., Zeng, B.: Test instances of—a polyhedral study on chance constrained program with random right-hand side. www.pitt.edu/ bzeng/ · Zbl 1386.90089
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.