Robust reformulations of ambiguous chance constraints with discrete probability distributions
DOI:
https://doi.org/10.11121/ijocta.01.2019.00611Keywords:
robust optimization, chance constraint, ambiguous chance constraintAbstract
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.Downloads
References
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.
Downloads
Published
How to Cite
Issue
Section
License
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
