×

On quantile cuts and their closure for chance constrained optimization problems. (English) Zbl 1412.90096

Summary: A chance constrained optimization problem over a finite distribution involves a set of scenario constraints from which a small subset can be violated. We consider the setting where all scenario constraints are mixed-integer convex. Existing works typically consider a mixed integer nonlinear programming (MINLP) formulation of this problem by introducing binary variables to indicate which constraint systems are to be satisfied or violated. A variety of cutting plane approaches for this MINLP formulation have been developed. In this paper we consider a family of cuts in the original space rather than those in the extended space of the MINLP reformulation. These cuts, known as quantile cuts, can be viewed as a projection of the well known family of mixing inequalities for the MINLP reformulation onto the original problem space. We show that the closure of the infinite family of all quantile cuts has a finite description. An important corollary of this result is that for linear chance constrained problems the quantile closure is polyhedral. We further show that a recursive application of quantile closure operations recovers the convex hull of the nonconvex chance constrained set in the limit, and in the pure integer setting the convergence is finite. We show that separation of quantile cuts is in general NP-hard, develop a heuristic separation method, and demonstrate its effectiveness through a computational study. We also study an approximation of the quantile closure and propose a generalization by grouping scenarios.

MSC:

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

References:

[1] Abdi, Ahmad; Fukasawa, Ricardo, On the mixing set with a knapsack constraint, Mathematical Programming, 157, 191-217, (2016) · Zbl 1354.90076 · doi:10.1007/s10107-016-0979-5
[2] Ahmed, Shabbir; Luedtke, James; Song, Yongjia; Xie, Weijun, Nonanticipative duality, relaxations, and formulations for chance-constrained stochastic programs, Mathematical Programming, 162, 51-81, (2016) · Zbl 1358.90080 · doi:10.1007/s10107-016-1029-z
[3] Atamtürk, A.; Nemhauser, GL; Savelsbergh, MW, The mixed vertex packing problem, Math. Program., 89, 35-53, (2000) · Zbl 1033.90095 · doi:10.1007/s101070000154.
[4] Ceria, S.; Soares, J., Convex programming for disjunctive convex optimization, Math. Program., 86, 595-614, (1999) · Zbl 0954.90049 · doi:10.1007/s101070050106
[5] Grossmann, I.E. , Ruiz, J.P.: Generalized disjunctive programming: a framework for formulation and alternative algorithms for MINLP optimization. In: Lee, J., Leyffer., S. (eds.) Mixed Integer Nonlinear Programming. The IMA Volumes in Mathematics and its Applications, vol. 154. Springer, New York, NY (2012) · Zbl 1242.90133
[6] Günlük, O.; Pochet, Y., Mixing mixed-integer inequalities, Math. Program., 90, 429-457, (2001) · Zbl 1041.90033 · doi:10.1007/PL00011430
[7] Hong, LJ; Yang, Y.; Zhang, L., Sequential convex approximations to joint chance constrained programs: a Monte Carlo approach, Oper. Res., 59, 617-630, (2011) · Zbl 1231.90303 · doi:10.1287/opre.1100.0910
[8] 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
[9] 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
[10] 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
[11] Meyer, RR, On the existence of optimal solutions to integer and mixed-integer programming problems, Math. Program., 7, 223-235, (1974) · Zbl 0292.90036 · doi:10.1007/BF01585518
[12] 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
[13] Raman, R.; Grossmann, IE, Modelling and computational techniques for logic based integer programming, Comput. Chem. Eng., 18, 563-578, (1994) · doi:10.1016/0098-1354(93)E0010-7
[14] Salinetti, G.; Wets, RJ-B, On the convergence of sequences of convex sets in finite dimensions, SIAM Rev., 21, 18-33, (1979) · Zbl 0421.52003 · doi:10.1137/1021002
[15] Schneider, R.: Convex Bodies: The Brunn-Minkowski Theory. Cambridge University Press, Cambridge (1993) · Zbl 0798.52001 · doi:10.1017/CBO9780511526282
[16] Song, Y.; Luedtke, JR; Küçükyavuz, S., Chance-constrained binary packing problems, INFORMS J. Comput., 26, 735-747, (2014) · Zbl 1304.90179 · doi:10.1287/ijoc.2014.0595
[17] Sun, H.; Xu, H.; Wang, Y., Asymptotic analysis of sample average approximation for stochastic optimization problems with joint chance constraints via conditional value at risk and difference of convex functions, J. Optim. Theory Appl., 161, 257-284, (2014) · Zbl 1314.90059 · doi:10.1007/s10957-012-0127-1
[18] Zhao, Ming; Huang, Kai; Zeng, Bo, A polyhedral study on chance constrained program with random right-hand side, Mathematical Programming, 166, 19-64, (2016) · 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.