American Institute of Mathematical Sciences

Advanced
2012, 2(4): 767-778. doi: 10.3934/naco.2012.2.767

A survey on probabilistically constrained optimization problems

Xiaodi Bai 1, , Xiaojin Zheng 2, and  Xiaoling Sun 1,

1. 

School of Management, Fudan University, Shanghai 200433, China
2. 

School of Economics and Management, Tongji University, Shanghai 200092, China

Received  November 2011 Revised  October 2012 Published  November 2012

Probabilistically constrained optimization problems are an important class of stochastic programming problems with wide applications in finance, management and engineering planning. In this paper, we summarize some important solution methods including convex approximation, DC approach, scenario approach and integer programming approach. We also discuss some future research perspectives on the probabilistically constrained optimization problems.
Keywords: DC approach, integer programming approach., probabilistic constraints, Stochastic programming, convex approximation method.
Mathematics Subject Classification: Primary: 91C15; Secondary: 90C2.
Citation: Xiaodi Bai, Xiaojin Zheng, Xiaoling Sun. A survey on probabilistically constrained optimization problems. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 767-778. doi: 10.3934/naco.2012.2.767
References:
[1]

G. J. Alexander and A. M. Baptista, A comparison of VaR and CVaR constraints on portfolio selection with the mean-variance model, Management Science, 50 (2004), 1261-1273. doi: 10.1287/mnsc.1040.0201.

[2]

G. J. Alexander, A. M. Baptista and S. Yan, Mean-variance portfolio selection with 'at-risk' constraints and discrete distributions, Journal of Banking & Finance, 31 (2007), 3761-3781. doi: 10.1016/j.jbankfin.2007.01.019.

[3]

X. D. Bai, J. Sun, X. J. Zheng and X. L. Sun, A penalty decomposition method for probabilistically constrained convex programs, Technical report, School of Management, Fudan University, P. R. China, 2012. Available from: http://www.optimization-online.org/DB_HTML/2012/04/3448.html.

[4]

A. Ben-Tal, L. El Ghaoui and A. S. Nemirovski, "Robust Optimization," Princeton University Press, 2009.

[5]

S. Benati and R. Rizzi, A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem, European Journal of Operational Research, 176 (2007), 423-434. doi: 10.1016/j.ejor.2005.07.020.

[6]

P. Beraldi and A. Ruszczyński, The probabilistic set-covering problem, Operations Research, 50 (2002), 956-967. doi: 10.1287/opre.50.6.956.345.

[7]

P. Bonami and M. A. Lejeune, An exact solution approach for portfolio optimization problems under stochastic and integer constraints, Operations Research, 57 (2009), 650-670. doi: 10.1287/opre.1080.0599.

[8]

S. P. Boyd and L. Vandenberghe, "Convex Optimization," Cambridge University Press, 2004.

[9]

G. C. Calafiore and M. C. Campi, The scenario approach to robust control design, IEEE Transactions on Automatic Control, 51 (2006), 742-753. doi: 10.1109/TAC.2006.875041.

[10]

A. Charnes and W. W. Cooper, Chance-constrained programming, Management Science, 6 (1959), 73-79. doi: 10.1287/mnsc.6.1.73.

[11]

W. Chen, M. Sim, J. Sun and C. P. Teo, From CVaR to uncertainty set: Implications in joint chance-constrained optimization, Operations Research, 58 (2010), 470-485. doi: [10.1287/opre.1090.0712.

[12]

M. S. Cheon, S. Ahmed and F. Al-Khayyal, A branch-reduce-cut algorithm for the global optimization of probabilistically constrained linear programs, Mathematical Programming, 108 (2006), 617-634. doi: 10.1007/s10107-006-0725-5.

[13]

D. Dentcheva and G. Martinez, Augmented Lagrangian method for probabilistic optimization, Annals of Operations Research, 200 (2012), 109-130. doi: 10.1007/s10479-011-0884-5.

[14]

D. Dentcheva, A. Prékopa and A. Ruszczynski, Concavity and efficient points of discrete distributions in probabilistic programming, Mathematical Programming, 89 (2000), 55-77. doi: 10.1007/PL00011393.

[15]

A. A. Gaivoronski and G. Pflug, Value at risk in portfolio optimization: Properties and computational approach, Journal of Risk, 7 (2005), 1-31.

[16]

R. Henrion, Structural properties of linear probabilistic constraints, Optimization, 56 (2007), 425-440. doi: 10.1080/02331930701421046.

[17]

R. Henrion and C. Strugarek, Convexity of chance constraints with independent random variables, Computational Optimization and Applications, 41 (2008), 263-276. doi: 10.1007/s10589-007-9105-1.

[18]

L. J. Hong, Y. Yang, and L. Zhang, Sequential convex approximations to joint chance constrained programs: A monte carlo approach, Operations Research, 59 (2011), 617-630. doi: 10.1287/opre.1100.0910.

[19]

S. Küçükyavuz, On mixing sets arising in chance-constrained programming, Mathematical Programming, 132 (2012), 31-56. doi: 10.1007/s10107-010-0385-3.

[20]

C. M. Lagoa, X. Li, and M. Sznaier, Probabilistically constrained linear programs and risk-adjusted controller design, SIAM Journal on Optimization, 15 (2005), 938-951. doi: 10.1137/S1052623403430099.

[21]

M. Lejeune and N. Noyan, Mathematical programming approaches for generating p-efficient points, European Journal of Operational Research, 207 (2010), 590-600. doi: 10.1016/j.ejor.2010.05.025.

[22]

M. A. Lejeune and A. Ruszczynski, An efficient trajectory method for probabilistic inventory production-distribution problems, Operations Research, 55 (2007), 378-394. doi: 10.1287/opre.1060.0356.

[23]

J. Luedtke and S. Ahmed, A sample approximation approach for optimization with probabilistic constraints, SIAM Journal on Optimization, 19 (2008), 674-699. doi: 10.1137/070702928.

[24]

J. Luedtke, S. Ahmed and G. L. Nemhauser, An integer programming approach for linear programs with probabilistic constraints, Mathematical Programming, 122 (2010), 247-272. doi: 10.1007/s10107-008-0247-4.

[25]

A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs, SIAM Journal on Optimization, 17 (2006), 969-996. doi: 10.1137/050622328.

[26]

A. Nemirovski and A. Shapiro, Scenario approximations of chance constraints, in "Probabilistic and Randomized Methods for Design Under Uncertainty" (eds. G. Calafiore and F. Dabbene), Springer, (2006), 3-47. doi: 10.1007/1-84628-095-8_1.

[27]

J. Nocedal and S. J. Wright, "Numerical Optimization," Springer, 1999. doi: 10.1007/b98874.

[28]

A. Prékopa, Probabilistic programming, in "Stochastic Programming, " Handbooks in Operations Research and Management Science (eds. A. Ruszczyński and A. Shapiro), Elsevier, (2003), 267-351.

[29]

R. T. Rockafellar and S. Uryasev, Optimization of conditional value-at-risk, Journal of Risk, 2 (2000), 21-42.

[30]

A. Ruszczyński, Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra, Mathematical Programming, 93 (2002), 195-215. doi: 10.1007/s10107-002-0337-7.

[31]

A. Saxena, V. Goyal and M. A. Lejeune, MIP reformulations of the probabilistic set covering problem, Mathematical Programming, 121 (2010), 1-31. doi: 10.1007/s10107-008-0224-y.

[32]

X. J. Zheng, X. L. Sun, D. Li and X. T. Cui, Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs, European Journal of Operational Research, 221 (2012), 38-48. doi: 10.1016/j.ejor.2012.03.006.

show all references

References:
[1]

G. J. Alexander and A. M. Baptista, A comparison of VaR and CVaR constraints on portfolio selection with the mean-variance model, Management Science, 50 (2004), 1261-1273. doi: 10.1287/mnsc.1040.0201.

[2]

G. J. Alexander, A. M. Baptista and S. Yan, Mean-variance portfolio selection with 'at-risk' constraints and discrete distributions, Journal of Banking & Finance, 31 (2007), 3761-3781. doi: 10.1016/j.jbankfin.2007.01.019.

[3]

X. D. Bai, J. Sun, X. J. Zheng and X. L. Sun, A penalty decomposition method for probabilistically constrained convex programs, Technical report, School of Management, Fudan University, P. R. China, 2012. Available from: http://www.optimization-online.org/DB_HTML/2012/04/3448.html.

[4]

A. Ben-Tal, L. El Ghaoui and A. S. Nemirovski, "Robust Optimization," Princeton University Press, 2009.

[5]

S. Benati and R. Rizzi, A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem, European Journal of Operational Research, 176 (2007), 423-434. doi: 10.1016/j.ejor.2005.07.020.

[6]

P. Beraldi and A. Ruszczyński, The probabilistic set-covering problem, Operations Research, 50 (2002), 956-967. doi: 10.1287/opre.50.6.956.345.

[7]

P. Bonami and M. A. Lejeune, An exact solution approach for portfolio optimization problems under stochastic and integer constraints, Operations Research, 57 (2009), 650-670. doi: 10.1287/opre.1080.0599.

[8]

S. P. Boyd and L. Vandenberghe, "Convex Optimization," Cambridge University Press, 2004.

[9]

G. C. Calafiore and M. C. Campi, The scenario approach to robust control design, IEEE Transactions on Automatic Control, 51 (2006), 742-753. doi: 10.1109/TAC.2006.875041.

[10]

A. Charnes and W. W. Cooper, Chance-constrained programming, Management Science, 6 (1959), 73-79. doi: 10.1287/mnsc.6.1.73.

[11]

W. Chen, M. Sim, J. Sun and C. P. Teo, From CVaR to uncertainty set: Implications in joint chance-constrained optimization, Operations Research, 58 (2010), 470-485. doi: [10.1287/opre.1090.0712.

[12]

M. S. Cheon, S. Ahmed and F. Al-Khayyal, A branch-reduce-cut algorithm for the global optimization of probabilistically constrained linear programs, Mathematical Programming, 108 (2006), 617-634. doi: 10.1007/s10107-006-0725-5.

[13]

D. Dentcheva and G. Martinez, Augmented Lagrangian method for probabilistic optimization, Annals of Operations Research, 200 (2012), 109-130. doi: 10.1007/s10479-011-0884-5.

[14]

D. Dentcheva, A. Prékopa and A. Ruszczynski, Concavity and efficient points of discrete distributions in probabilistic programming, Mathematical Programming, 89 (2000), 55-77. doi: 10.1007/PL00011393.

[15]

A. A. Gaivoronski and G. Pflug, Value at risk in portfolio optimization: Properties and computational approach, Journal of Risk, 7 (2005), 1-31.

[16]

R. Henrion, Structural properties of linear probabilistic constraints, Optimization, 56 (2007), 425-440. doi: 10.1080/02331930701421046.

[17]

R. Henrion and C. Strugarek, Convexity of chance constraints with independent random variables, Computational Optimization and Applications, 41 (2008), 263-276. doi: 10.1007/s10589-007-9105-1.

[18]

L. J. Hong, Y. Yang, and L. Zhang, Sequential convex approximations to joint chance constrained programs: A monte carlo approach, Operations Research, 59 (2011), 617-630. doi: 10.1287/opre.1100.0910.

[19]

S. Küçükyavuz, On mixing sets arising in chance-constrained programming, Mathematical Programming, 132 (2012), 31-56. doi: 10.1007/s10107-010-0385-3.

[20]

C. M. Lagoa, X. Li, and M. Sznaier, Probabilistically constrained linear programs and risk-adjusted controller design, SIAM Journal on Optimization, 15 (2005), 938-951. doi: 10.1137/S1052623403430099.

[21]

M. Lejeune and N. Noyan, Mathematical programming approaches for generating p-efficient points, European Journal of Operational Research, 207 (2010), 590-600. doi: 10.1016/j.ejor.2010.05.025.

[22]

M. A. Lejeune and A. Ruszczynski, An efficient trajectory method for probabilistic inventory production-distribution problems, Operations Research, 55 (2007), 378-394. doi: 10.1287/opre.1060.0356.

[23]

J. Luedtke and S. Ahmed, A sample approximation approach for optimization with probabilistic constraints, SIAM Journal on Optimization, 19 (2008), 674-699. doi: 10.1137/070702928.

[24]

J. Luedtke, S. Ahmed and G. L. Nemhauser, An integer programming approach for linear programs with probabilistic constraints, Mathematical Programming, 122 (2010), 247-272. doi: 10.1007/s10107-008-0247-4.

[25]

A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs, SIAM Journal on Optimization, 17 (2006), 969-996. doi: 10.1137/050622328.

[26]

A. Nemirovski and A. Shapiro, Scenario approximations of chance constraints, in "Probabilistic and Randomized Methods for Design Under Uncertainty" (eds. G. Calafiore and F. Dabbene), Springer, (2006), 3-47. doi: 10.1007/1-84628-095-8_1.

[27]

J. Nocedal and S. J. Wright, "Numerical Optimization," Springer, 1999. doi: 10.1007/b98874.

[28]

A. Prékopa, Probabilistic programming, in "Stochastic Programming, " Handbooks in Operations Research and Management Science (eds. A. Ruszczyński and A. Shapiro), Elsevier, (2003), 267-351.

[29]

R. T. Rockafellar and S. Uryasev, Optimization of conditional value-at-risk, Journal of Risk, 2 (2000), 21-42.

[30]

A. Ruszczyński, Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra, Mathematical Programming, 93 (2002), 195-215. doi: 10.1007/s10107-002-0337-7.

[31]

A. Saxena, V. Goyal and M. A. Lejeune, MIP reformulations of the probabilistic set covering problem, Mathematical Programming, 121 (2010), 1-31. doi: 10.1007/s10107-008-0224-y.

[32]

X. J. Zheng, X. L. Sun, D. Li and X. T. Cui, Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs, European Journal of Operational Research, 221 (2012), 38-48. doi: 10.1016/j.ejor.2012.03.006.

[1]

Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1349-1366. doi: 10.3934/jimo.2016.12.1349
[2]

Changzhi Wu, Chaojie Li, Qiang Long. A DC programming approach for sensor network localization with uncertainties in anchor positions. Journal of Industrial and Management Optimization, 2014, 10 (3) : 817-826. doi: 10.3934/jimo.2014.10.817
[3]

Le Thi Hoai An, Tran Duc Quynh, Pham Dinh Tao. A DC programming approach for a class of bilevel programming problems and its application in Portfolio Selection. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 167-185. doi: 10.3934/naco.2012.2.167
[4]

Harald Held, Gabriela Martinez, Philipp Emanuel Stelzig. Stochastic programming approach for energy management in electric microgrids. Numerical Algebra, Control and Optimization, 2014, 4 (3) : 241-267. doi: 10.3934/naco.2014.4.241
[5]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353
[6]

Ailing Zhang, Shunsuke Hayashi. Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 83-98. doi: 10.3934/naco.2011.1.83
[7]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557
[8]

Xiantao Xiao, Jian Gu, Liwei Zhang, Shaowu Zhang. A sequential convex program method to DC program with joint chance constraints. Journal of Industrial and Management Optimization, 2012, 8 (3) : 733-747. doi: 10.3934/jimo.2012.8.733
[9]

Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102
[10]

Gang Li, Yinghong Xu, Zhenhua Qin. Optimality conditions for composite DC infinite programming problems. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022064
[11]

Ling Zhang, Xiaoqi Sun. Stability analysis of time-varying delay neural network for convex quadratic programming with equality constraints and inequality constraints. Discrete and Continuous Dynamical Systems - B, 2022  doi: 10.3934/dcdsb.2022035
[12]

Ye Tian, Shucherng Fang, Zhibin Deng, Qingwei Jin. Cardinality constrained portfolio selection problem: A completely positive programming approach. Journal of Industrial and Management Optimization, 2016, 12 (3) : 1041-1056. doi: 10.3934/jimo.2016.12.1041
[13]

Shu-Cherng Fang, David Y. Gao, Ruey-Lin Sheu, Soon-Yi Wu. Canonical dual approach to solving 0-1 quadratic programming problems. Journal of Industrial and Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125
[14]

Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058
[15]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial and Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723
[16]

Rhoda P. Agdeppa, Nobuo Yamashita, Masao Fukushima. An implicit programming approach for the road pricing problem with nonadditive route costs. Journal of Industrial and Management Optimization, 2008, 4 (1) : 183-197. doi: 10.3934/jimo.2008.4.183
[17]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial and Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171
[18]

Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965
[19]

Bao Qing Hu, Song Wang. A novel approach in uncertain programming part II: a class of constrained nonlinear programming problems with interval objective functions. Journal of Industrial and Management Optimization, 2006, 2 (4) : 373-385. doi: 10.3934/jimo.2006.2.373
[20]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363

 Impact Factor: 

Tools

Metrics

  • PDF downloads (157)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy