Robust reformulations of ambiguous chance constraints with discrete probability distributions




robust optimization, chance constraint, ambiguous chance constraint


This paper proposes robust reformulations of ambiguous chance constraints when the underlying family of distributions is discrete and supported in a so-called ``p-box'' or ``p-ellipsoidal'' uncertainty set. Using the robust optimization paradigm, the deterministic counterparts of the ambiguous chance constraints are reformulated as mixed-integer programming problems which can be tackled by commercial solvers for moderate sized instances. For larger sized instances, we propose a safe approximation algorithm that is computationally efficient and yields high quality solutions. The associated approach and the algorithm can be easily extended to joint chance constraints, nonlinear inequalities, and dependent data without introducing additional mathematical optimization complexity to that of the original robust reformulation. In numerical experiments, we first present our approach over a toy-sized chance constrained knapsack problem. Then, we compare optimality and computational performances of the safe approximation algorithm with those of the exact and the randomized approaches for larger sized instances via Monte Carlo simulation.


Download data is not yet available.

Author Biography

İhsan Yanıkoğlu

Assistant Professor of Industrial Engineering at Özyeğin University.


Charnes, A. & Cooper, W.W. (1959). Chanceconstrained programming. Management Science, 6(1), 73–79.

Charnes, A., Cooper, W.W. & Symonds, G.H. (1958). Cost horizons and certainty equivalents: 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 constraints. Operations Research, 13(6), 930–945.

Prekopa, A. (1970). Efficient robust optimization of metal forming processes using a sequential metamodel based strategy. In Proceedings of the Princeton Symposium on Mathematical Programming, Princeton University Press, Princeton, NJ, 113–138.

Burkauskas, A. (1986). On the convexity problem of probabilistic constraint stochastic programming problems. Alkalmazott Matematikai Lapok, 12, 77–90.

Prekopa, A. (1974). Programming under probabilistic constraints with a random technology matrix. Mathematische Operationsforschung und Statistik, 5, 109–116.

Van de Panne, C. & Popp, W., (1963). Minimum-cost cattle feed under probabilistic protein constraints. Management Science, 9(3), 405–430.

Prekopa, A. (1973). On logarithmic concave measures and functions. Acta Scientiarum Mathematicarum, 34, 335–343.

Prekopa, A. (1995). Stochastic Programming Kluwer Academic Publishers, Dordrecht, The Netherlands.

Nemirovski, A. & Shapiro, A. (2006). Convex approximations of chance constrained programs. SIAM Journal on Optimization, 17(4), 969–996.

Ben-Tal, A. & Nemirovski, A. (2000). Robust solutions of linear programming problems contaminated with uncertain data. Mathematical Programming, 88(3), 411–424.

Chen, W., Sim, M., Sun, J. & Teo, C.P. (2010). From CVaR to uncertainty set: implications in joint chance-constrained optimization. Operations Research, 58(2), 470–485.

Chen, X., Sim, M. & Sun, P. (2007). A robust optimization perspective on stochastic programming. Operations Research 55(6), 1058–1107.

Zymler S., Kuhn, D. & R¨ustem, B. (2013). Distributionally robust joint chance constraints with second-order moment information. Mathematical Programming, 137(1-2), 167–198.

Calafiore, G.C. & Campi, M.C. (2005). Uncertain convex programs: randomized solutions and confidence levels. Mathematical Programming, 102, 25–46.

Campi, M.C. & Garatti, S. (2008). The exact feasibility of randomized solutions of robust convex programs. SIAM Journal on Optimization, 19(3), 1211–1230.

Birge, J.R. & Wets, R.J.-B. (1986). Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recourse. Mathematical Programming Studies, 27, 54–102.

Dupaˇcov´a, J. (2001). Stochastic Programming: minimax approach. In: Encyclopedia of Optimization. Kluwer Academic Publishers, Dordrecht, The Netherlands.

Shapiro, A. & Ahmed, S. (2004). On a class of minimax stochastic programs. SIAM Journal on Optimization, 14(4), 1237–1252.

Shapiro, A. & Kleywegt, A.J. (2002). Minimax analysis of stochastic problems. Optimization Methods and Software, 17, 523–542.

Epstein, L.G. & Schneider, M. (2003). Recursive multiple-priors. Journal of Economic Theory, 113(1), 1–31.

Epstein, L.G. & Schneider, M. (2007). Learning under ambiguity. Review of Economic Studies, 74(4), 1275–1303.

Hansen, L.P. & Sargent, T.J. (2001). Robust control and model uncertainty. American Economic Review, 91, 60–66.

Erdogan, E. & Iyengar, G. (2006). Ambiguous chance constrained problems and robust optimization. Mathematical Programming, 107(1–2), 37–61.

Yanıkoglu, ˙I, den Hertog, D. (2013). Safe approximations 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 approximations of chance constraints. European Journal of Operations Research, 219(3), 707– 718

Yanıkoglu, ˙I & den Hertog, D. & Kleijnen, J.P.C. (2016). Robust dual-response optimization. IIE Transactions, 48(3), 298–312.

Luedtke, J. (2014). A branch-and-cut decomposition algorithm for solving chanceconstrained mathematical programs with finite support. Mathematical Programming 146(1–2), 219-244.

Song, Y., Luedtke, J. R., & K¨u¸c¨ukyavuz, 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 quantification 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. Mathematical Programming, 158(1-2), 291–327.

Chen, Z., Kuhn, D., & Wiesemann, W. (2018). Data-driven chance constrained programs over Wasserstein Balls. arXiv preprint, arXiv:1809.00210.

Ji, R. & Lejeune, M. (2018). Data-driven distributionally robust chance-constrained programming with Wasserstein metric. Available at Optimization Online.

Zhang, Y., Jiang, R. & Shen, S. (2016). Distributionally robust chance-constrained bin packing. Available at Optimization Online.

Cheng, J., Delage, E. & Lisser, A. (2014). Distributionally robust stochastic knapsack 2 problem. SIAM Journal on Optimization, 24(3), 1485–1506.

Hu, Z. & Hong, L.J. (2013). Kullback-Leibler divergence constrained distributionally robust optimization. Available at Optimization Online.

Xie, W. & Ahmed, S. (2018). On deterministic reformulations of distributionally robust joint chance constrained optimization problems. SIAM Journal on Optimization, 28(2), 1151–1182.

Xie, W., Ahmed, S. & Jiang, R. (2017). Optimized Bonferroni approximations of distributionally 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). Models and algorithms for distributionally robust least squares problems. Mathematical Programming, 146(1-2), 123–141.

Ozmen, A., Weber, G.W., Batmaz, ˙I. & Kropat, E. (2011). RCMARS: Robustification of CMARS with different scenarios under polyhedral uncertainty set. Communications in Nonlinear Science and Numerical Simulation, 16(12), 4780–4787.

Friedman, J.H. (1991). Multivariate adaptive regression splines. Annals of Statistics, 19(1), 1–141.

Weber, G.W., Batmaz, ˙I., K¨oksal, G., Taylan, P. & F. Yerlikaya-¨Ozkurt, (2012). CMARS: a new contribution to nonparametric regression with multivariate adaptive regression splines supported by continuous optimization. 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). Robust portfolio optimization using a simple factor model. IMA Preprint Series, No. 2284, University of Minnesota, Minneapolis, MN.

Kara, G., ¨Ozmen, A., & Weber, G. W. (2019). Stability advances in robust portfolio optimization under parallelepiped uncertainty. Central European Journal of Operations Research, 27(1), 241–261.

Postek, K., den Hertog, D. & Melenberg, B. (2016). Computationally tractable counterparts of distributionally robust constraints on risk measures. SIAM Review, 58(4), 603–650.

Gorissen, B.L., Yanıko˘glu, ˙I & den Hertog, D. (2015). A practical guide to robust optimization. Omega, 53, 124–137.

Ben-Tal, A., den Hertog, D. & and Vial, J.-P. (2015). Deriving robust counterparts of nonlinear uncertain inequalities. Mathematical Programming, 149(1-2), 265–299.

Yanıkoglu, ˙I. (2018). Selected Topics in Robust Optimization. In: Optimization Techniques for Problem Solving in Uncertainty. IGI Global, PA, USA.



DOI: 10.11121/ijocta.01.2019.00611
Published: 2019-07-31

How to Cite

Yanıkoğlu, İhsan. (2019). Robust reformulations of ambiguous chance constraints with discrete probability distributions. An International Journal of Optimization and Control: Theories & Applications (IJOCTA), 9(2), 236–252.



Research Articles