Robust reformulations of ambiguous chance constraints with discrete probability distributions

This paper proposes robust reformulations of ambiguous chance constraintswhen the underlying family of distributions is discrete and supported in aso-called “p-box” or “p-ellipsoidal” uncertainty set. Using the robust opti-mization paradigm, the deterministic counterparts of the ambiguous chanceconstraints are reformulated as mixed-integer programming problems whichcan be tackled by commercial solvers for moderate sized instances. For largersized instances, we propose a safe approximation algorithm that is compu-tationally efficient and yields high quality solutions. The associated approachand the algorithm can be easily extended to joint chance constraints, nonlinearinequalities, and dependent data without introducing additional mathemati-cal optimization complexity to that of the original robust reformulation. Innumerical experiments, we first present our approach over a toy-sized chanceconstrained knapsack problem. Then, we compare optimality and computa-tional performances of the safe approximation algorithm with those of the ex-act and the randomized approaches for larger sized instances via Monte Carlosimulation.

PDF

___

Charnes, A. & Cooper, W.W. (1959). Chance- constrained programming. Management Sci- ence, 6(1), 73–79.
Charnes, A., Cooper, W.W. & Symonds, G.H. (1958). Cost horizons and certainty equiva- lents: an approach to stochastic programming of heating oil. Management Science, 4(3), 235–263.
Miller, B.L. & Wagner, H.M. (1965). Chance constrained programming with joint con- straints. Operations Research, 13(6), 930–945.
Prékopa, A. (1970). Efficient robust opti- mization of metal forming processes using a sequential metamodel based strategy. In Proceedings of the Princeton Symposium on Mathematical Programming, Princeton Uni- versity Press, Princeton, NJ, 113–138.
Burkauskas, A. (1986). On the convexity problem of probabilistic constraint stochastic programming problems. Alkalmazott Matem- atikai Lapok, 12, 77–90.
Prékopa, A. (1974). Programming under probabilistic constraints with a random tech- nology matrix. Mathematische Operations- forschung und Statistik, 5, 109–116.
Van de Panne, C. & Popp, W., (1963). Minimum-cost cattle feed under probabilis- tic protein constraints. Management Science, 9(3), 405–430.
Prékopa, A. (1973). On logarithmic concave measures and functions. Acta Scientiarum Mathematicarum, 34, 335–343.
Prékopa, A. (1995). Stochastic Programming Kluwer Academic Publishers, Dordrecht, The Netherlands.
Nemirovski, A. & Shapiro, A. (2006). Convex approximations of chance constrained pro- grams. SIAM Journal on Optimization, 17(4), 969–996.
Ben-Tal, A. & Nemirovski, A. (2000). Robust solutions of linear programming problems contaminated with uncertain data. Mathe- matical Programming, 88(3), 411–424.
Chen, W., Sim, M., Sun, J. & Teo, C.P. (2010). From CVaR to uncertainty set: impli- cations in joint chance-constrained optimiza- tion. Operations Research, 58(2), 470–485.
Chen, X., Sim, M. & Sun, P. (2007). A robust optimization perspective on stochastic pro- gramming. Operations Research 55(6), 1058– 1107.
Zymler S., Kuhn, D. & Rüstem, B. (2013). Distributionally robust joint chance con- straints with second-order moment informa- tion. Mathematical Programming, 137(1-2), 167–198.
Calafiore, G.C. & Campi, M.C. (2005). Un- certain convex programs: randomized so- lutions and confidence levels. Mathematical Programming, 102, 25–46.
Campi, M.C. & Garatti, S. (2008). The ex- act feasibility of randomized solutions of ro- bust convex programs. SIAM Journal on Op- timization, 19(3), 1211–1230.
Birge, J.R. & Wets, R.J.-B. (1986). Design- ing approximation schemes for stochastic op- timization problems, in particular for sto- chastic programs with recourse. Mathematical Programming Studies, 27, 54–102.
Dupačová, J. (2001). Stochastic Program- ming: minimax approach. In: Encyclopedia of Optimization. Kluwer Academic Publish- ers, Dordrecht, The Netherlands.
Shapiro, A. & Ahmed, S. (2004). On a class of minimax stochastic programs. SIAM Jour- nal on Optimization, 14(4), 1237–1252.
Shapiro, A. & Kleywegt, A.J. (2002). Min- imax analysis of stochastic problems. Opti- mization Methods and Software, 17, 523–542.
Epstein, L.G. & Schneider, M. (2003). Re- cursive multiple-priors. Journal of Economic Theory, 113(1), 1–31.
Epstein, L.G. & Schneider, M. (2007). Learn- ing under ambiguity. Review of Economic Studies, 74(4), 1275–1303.
Hansen, L.P. & Sargent, T.J. (2001). Ro- bust control and model uncertainty. American Economic Review, 91, 60–66.
Erdoğan, E. & Iyengar, G. (2006). Am- biguous chance constrained problems and robust optimization. Mathematical Program- ming, 107(1–2), 37–61.
Yanıkoğlu, İ, den Hertog, D. (2013). Safe ap- proximations of ambiguous chance constraints using historical data. INFORMS Journal on Computing, 25(4), 666–681.
Ben-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton Press, Princeton, NJ.
Nemirovski, A. (2012). On safe tractable ap- proximations of chance constraints. European Journal of Operations Research, 219(3), 707– 718
Yanıkoğlu, İ & den Hertog, D. & Kleij- nen, J.P.C. (2016). Robust dual-response op- timization. IIE Transactions, 48(3), 298–312.
Luedtke, J. (2014). A branch-and-cut de- composition algorithm for solving chance- constrained mathematical programs with fi- nite support. Mathematical Programming 146(1–2), 219-244.
Song, Y., Luedtke, J. R., & Küçükyavuz, S. (2014). Chance-constrained binary packing problems. INFORMS Journal on Computing, 26(4), 735-747.
Hanasusanto, G.A., Roitch, V., Kuhn, D. & Wiesemann, W. (2015). A distributionally robust perspective on uncertainty quantifi- cation and chance constrained programming. Mathematical Programming, 151(1), 35–62.
Hanasusanto, G.A., Roitch, V., Kuhn, D. & Wiesemann, W. (2017). Ambiguous joint chance constraints under mean and dispersion information. Operations Research, 65(3), 751– 767.
Jiang, R. & Guan, Y. (2016). Data-driven chance constrained stochastic program. Math- ematical Programming, 158(1-2), 291–327.
Chen, Z., Kuhn, D., & Wiesemann, W. (2018). Data-driven chance constrained pro- grams over Wasserstein Balls. arXiv preprint, arXiv:1809.00210.
Ji, R. & Lejeune, M. (2018). Data-driven dis- tributionally robust chance-constrained pro- gramming with Wasserstein metric. Available at Optimization Online.
Zhang, Y., Jiang, R. & Shen, S. (2016). Dis- tributionally robust chance-constrained bin packing. Available at Optimization Online.
Cheng, J., Delage, E. & Lisser, A. (2014). Distributionally robust stochastic knapsack problem. SIAM Journal on Optimization, 24(3), 1485–1506.
Hu, Z. & Hong, L.J. (2013). Kullback-Leibler divergence constrained distributionally ro- bust optimization. Available at Optimization Online.
Xie, W. & Ahmed, S. (2018). On determin- istic reformulations of distributionally robust joint chance constrained optimization prob- lems. SIAM Journal on Optimization, 28(2), 1151–1182.
Xie, W., Ahmed, S. & Jiang, R. (2017). Optimized Bonferroni approximations of dis- tributionally robust joint chance constraints. Available at Optimization Online.
Xie, W. (2018). On distributionally robust chance constrained program with wasserstein distance. arXiv preprint, arXiv:1806.07418.
Mehrotra, S. & Zhang, H. (2014). Mod- els and algorithms for distributionally robust least squares problems. Mathematical Pro- gramming, 146(1-2), 123–141.
Özmen, A., Weber, G.W., Batmaz, İ. & Kropat, E. (2011). RCMARS: Robustifica- tion of CMARS with different scenarios under polyhedral uncertainty set. Communications in Nonlinear Science and Numerical Simula- tion, 16(12), 4780–4787.
Friedman, J.H. (1991). Multivariate adaptive regression splines. Annals of Statistics, 19(1), 1–141.
Weber, G.W., Batmaz, İ., Köksal, G., Taylan, P. & F. Yerlikaya-Özkurt, (2012). CMARS: a new contribution to nonparamet- ric regression with multivariate adaptive re- gression splines supported by continuous op- timization. Inverse Problems in Science and Engineering, 20(3), 371–400.
Bemis, C., Hu, X., Lin, W., Moazeni, S., Wang, L., Wang, T. & Zhang, J. (2009). Ro- bust portfolio optimization using a simple fac- tor model. IMA Preprint Series, No. 2284, University of Minnesota, Minneapolis, MN.
Kara, G., Özmen, A., & Weber, G. W. (2019). Stability advances in robust portfo- lio optimization under parallelepiped uncer- tainty. Central European Journal of Opera- tions Research, 27(1), 241–261.
Postek, K., den Hertog, D. & Melenberg, B. (2016). Computationally tractable coun- terparts of distributionally robust constraints on risk measures. SIAM Review, 58(4), 603- –650.
Gorissen, B.L., Yanıkoğlu, İ & den Hertog, D. (2015). A practical guide to robust opti- mization. Omega, 53, 124–137.
Ben-Tal, A., den Hertog, D. & and Vial, J.-P. (2015). Deriving robust counterparts of nonlinear uncertain inequalities. Mathemati- cal Programming, 149(1-2), 265–299.
Yanıkoğlu, İ. (2018). Selected Topics in Ro- bust Optimization. In: Optimization Tech- niques for Problem Solving in Uncertainty. IGI Global, PA, USA.