×

zbMATH — the first resource for mathematics

Time consistent expected mean-variance in multistage stochastic quadratic optimization: a model and a matheuristic. (English) Zbl 1435.90092
Summary: In this paper, we present a multistage time consistent expected conditional risk measure for minimizing a linear combination of the expected mean and the expected variance, so-called expected mean-variance. The model is formulated as a multistage stochastic mixed-integer quadratic programming problem combining risk-sensitive cost and scenario analysis approaches. The proposed problem is solved by a matheuristic based on the branch-and-fix coordination method. The multistage scenario cluster primal decomposition framework is extended to deal with large-scale quadratic optimization by means of stage-wise reformulation techniques. A specific case study in risk-sensitive production planning is used to illustrate that a remarkable decrease in the expected variance (risk cost) is obtained. A competitive behavior on the part of our methodology in terms of solution quality and computation time is shown when comparing with plain use of CPLEX in 150 benchmark instances, ranging up to 711,845 constraints and 193,000 binary variables.
MSC:
90C15 Stochastic programming
90C20 Quadratic programming
90C59 Approximation methods and heuristics in mathematical programming
90C11 Mixed integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adams, W. P., Forrester, R. J., & Glover, F. W. (2004). Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs. Discrete Optimization, 1(2), 99-120. https://doi.org/10.1016/j.disopt.2004.03.006. · Zbl 1091.90040
[2] Ahmed, S., Garcia, R., Kong, N., Ntaimo, L., Parija, G., Qiu, F., & Sen, S (2015) SIPLIB: A stochastic integer programming test problem library. http://www.isye.gatech.edu/ sahmed/siplib.
[3] Ahmed, S. (2006). Convexity and decomposition of mean-risk stochastic programs. Mathematical Programming, 106(3), 433-446. https://doi.org/10.1007/s10107-005-0638-8. · Zbl 1134.90025
[4] Aldasoro, U., Merino, M., & Pérez, G. (2017). SMIQLib: Dataset for stochastic mixed integer quadratic optimization. Website. https://ehubox.ehu.eus/index.php/s/02Jhx3vYSXVQx7e.
[5] Aldasoro, U., Escudero, L. F., Merino, M., & Pérez, G. (2013). An algorithmic framework for solving large-scale multistage stochastic mixed 0-1 problems with nonsymmetric scenario trees. Part II: Parallelization. Computers & Operations Research, 40, 2950-2960. https://doi.org/10.1016/j.cor.2013.06.015. · Zbl 1348.90497
[6] Aldasoro, U., Escudero, L. F., Merino, M., & Pérez, G. (2017). A parallel Branch-and-Fix Coordination based matheuristic algorithm for solving large sized multistage stochastic mixed 0-1 problems. European Journal of Operational Research, 258(2), 590-606. https://doi.org/10.1016/j.ejor.2016.08.072. · Zbl 1394.90443
[7] Alonso-Ayuso, A., Escudero, L. F., Garín, M. A., Ortuño, M. T., & Pérez, G. (2005). On the product selection and plant dimensioning problem under uncertainty. Omega, 33(4), 307-318. https://doi.org/10.1016/j.omega.2004.05.001.
[8] ARINA: Computational cluster from izo-sgi, sgiker (upv/ehu) (2017). http://www.ehu.eus/sgi/recursos/cluster-arina.
[9] Birge, J. R., & Louveaux, F. (2011). Introduction to stochastic programming, 2nd edn. New York: Springer. https://doi.org/10.1007/978-1-4614-0237-4. · Zbl 1223.90001
[10] Bliek, C., Bonami, P., & Lodi, A. (2014). Solving mixed-integer quadratic programming problems with IBM-CPLEX: A progress report. In Proceedings of the Twenty-Sixth RAMP Symposium (pp. 171-180).
[11] Boyd, S., & Vandenberghe, L. (2009). Convex optimization. Cambridge: Cambridge University Press (Seventh printing with corrections 2009) · Zbl 1058.90049
[12] Cesarone, F., Scozzari, A., & Tardella, F. (2013). A new method for mean-variance portfolio optimization with cardinality constraints. Annals of Operations Research, 205(1), 213-234. https://doi.org/10.1007/s10479-012-1165-7. · Zbl 1269.91069
[13] Conejo, A. J., Nogales, F. J., Arroyo, J. M., & García-Bertrand, R. (2004). Risk-constrained self-scheduling of a thermal power producer. IEEE Transactions on Power Systems, 19(3), 1569-1574. https://doi.org/10.1109/TPWRS.2004.831652.
[14] Cristobal, M. P., Escudero, L. F., & Monge, J. F. (2009). On stochastic dynamic programming for solving large-scale planning problems under uncertainty. Computers & Operations Research, 36, 2418-2428. https://doi.org/10.1016/j.cor.2008.09.009. · Zbl 1179.90243
[15] Dentcheva, D., & Ruszczyński, A. (2009). Optimization with multivariate stochastic dominance constraints. Mathematical Programming, 117(1), 111-127. https://doi.org/10.1007/s10107-007-0165-x. · Zbl 1221.90069
[16] Dentcheva, D., & Ruszczyński, A. (2009). Robust stochastic dominance and its application to risk-averse optimization. Mathematical Programming, 123(1), 85. https://doi.org/10.1007/s10107-009-0321-6. · Zbl 1216.90064
[17] Escudero, L., Garín, M., Merino, M., & Pérez, G. (2009). A general algorithm for solving two-stage stochastic mixed 0-1 first-stage problems. Computers & Operations Research, 36(9), 2590-2600. https://doi.org/10.1016/j.cor.2008.11.011. · Zbl 1179.90245
[18] Escudero, L. F., Garín, M. A., Merino, M., & Pérez, G. (2009). BFC-MSMIP: An exact branch-and-fix coordination approach for solving multistage stochastic mixed 0-1 problems. TOP, 17, 96-122. https://doi.org/10.1007/s11750-009-0083-6. · Zbl 1170.90447
[19] Escudero, L. F., Garín, M. A., Merino, M., & Pérez, G. (2010). On BFC-MSMIP strategies for scenario cluster partitioning, and twin node family branching selection and bounding for multistage stochastic mixed integer programming. Computers & Operations Research, 37(4), 738-753. https://doi.org/10.1016/j.cor.2009.06.023. · Zbl 1176.90422
[20] Escudero, L. F., Garín, M. A., Merino, M., & Pérez, G. (2012). An algorithmic framework for solving large-scale multistage stochastic mixed 0-1 problems with nonsymmetric scenario trees. Computers & Operations Research, 39, 1133-1144. https://doi.org/10.1016/j.cor.2011.06.021. · Zbl 1251.90295
[21] Felt, A. (2003). Test-problem collection for stochastic linear programming. https://www4.uwsp.edu/math/afelt/slptestset/download.html.
[22] Fortet, R. (1960). L’algebre de boole et ses applications en recherche operationnelle. Revue française d’informatique et de recherche opérationnelle, 11(2), 111-118. https://doi.org/10.1007/BF03006558. · Zbl 0109.38201
[23] Furini, F., Traversi, E., Belotti, P., Frangioni, A., Gleixner, A., Gould, N., Liberti, L., Lodi, A., Misener, R., Mittelmann, H., Sahinidis, N. V., Vigerske, S., & Wiegele, A. QPLIB: A library of quadratic programming instances. http://qplib.zib.de/. · Zbl 1435.90099
[24] Gantmacher, F. R. (1959). The theory of matrices. New York: Chelsea Publishing Company.
[25] Glover, F. (1975). Improved linear integer programming formulations of nonlinear integer problems. Management Science, 22(4), 455-460. https://doi.org/10.1287/mnsc.22.4.455. · Zbl 0318.90044
[26] Holmes, D. (2017). A (PO)rtable (S)tochastic programming (T)est (S)et (POSTS). http://users.iems.northwestern.edu/ jrbirge/html/dholmes/post.html.
[27] Homem-de Mello, T., & Pagnoncelli, B. (2016). Risk aversion in multistage stochastic programming: A modeling and algorithmic perspective. European Journal of Operational Research, 249(1), 188-199. https://doi.org/10.1016/j.ejor.2015.05.048. · Zbl 1346.90639
[28] IBM ILOG: CPLEX v12.6.3. (2017). http://www.ilog.com/products/cplex.
[29] Kall, P., & Wallace, S. W. (1994). Stochastic Programming. Hoboken: Wiley.
[30] Kolodziej, S., Castro, P. M., & Grossmann, I. E. (2013). Global optimization of bilinear programs with a multiparametric disaggregation technique. Journal of Global Optimization, 57(4), 1039-1063. https://doi.org/10.1007/s10898-012-0022-1. · Zbl 1282.90137
[31] Louveaux, F. V. (1980). A solution method for multistage stochastic programs with recourse with application to an energy investment problem. Operations Research, 29(4), 889-902. https://doi.org/10.1287/opre.28.4.889. · Zbl 0441.90076
[32] McCormick, G. P. (1976). Computability of global solutions to factorable nonconvex programs: Part I-Convex underestimating problems. Mathematical Programming, 10(1), 147-175. https://doi.org/10.1007/BF01580665. · Zbl 0349.90100
[33] Mijangos, E. (2015). An algorithm for two-stage stochastic mixed-integer nonlinear convex problems. Annals of Operations Research, 235(1), 581-598. https://doi.org/10.1007/s10479-015-1899-0. · Zbl 1332.90183
[34] Mula, J., Poler, R., García-Sabater, J. P., & Lario, F. C. (2006). Models for production planning under uncertainty: A review. International Journal of Production Economics, 103(1), 271-285. https://doi.org/10.1016/j.ijpe.2005.09.001.
[35] Neise, F. (2008). Risk management in stochastic integer programming. New York: Vieweg+Teubner Verlag.
[36] Osorio, M. A., Gulpinar, N., & Rustem, B. (2008). A mixed integer programming model for multistage mean-variance post-tax optimization. European Journal of Operational Research, 185(2), 451-480. https://doi.org/10.1016/j.ejor.2006.09.105. · Zbl 1137.90606
[37] Osorio, M. A., Gülpınar, N., & Rustem, B. (2008). A general framework for multistage mean-variance post-tax optimization. Annals of Operations Research, 157(1), 3-23. https://doi.org/10.1007/s10479-007-0255-4. · Zbl 1147.91029
[38] Pflug, G. C., & Römisch, W. (2007). Modeling, measuring and managing risk. Singapore: World Scientific Publishing Co. Inc. · Zbl 1153.91023
[39] Pochet, Y., & Wolsey, L. A. (2006). Production planning by mixed integer programming. New York: Springer. https://doi.org/10.1007/0-387-33477-7. · Zbl 1102.90039
[40] Shapiro, A. (2009). On a time consistency concept in risk averse multistage stochastic programming. Operations Research Letters, 37(3), 143-147. https://doi.org/10.1016/j.orl.2009.02.005. · Zbl 1167.90613
[41] Siddiqui, S., Gabriel, S. A., & Azarm, S. (2015). Solving mixed-integer robust optimization problems with interval uncertainty using Benders decomposition. Journal of the Operational Research Society, 66(4), 664-673. https://doi.org/10.1057/jors.2014.41.
[42] Sun, J., Liao, L. Z., & Rodrigues, B. (2017). Quadratic two-stage stochastic optimization with coherent measures of risk. Mathematical Programming. https://doi.org/10.1007/s10107-017-1131-x. · Zbl 1402.90108
[43] Wets, R. J. B. (1975). On the relation between stochastic and deterministic optimization. In Control theory, numerical methods and computer systems modelling (pp. 350-361). New York: Springer. https://doi.org/10.1007/978-3-642-46317-4_26.
[44] Wets, R. J. B. (1974). Stochastic Programs with fixed recourse: The equivalent deterministic program. SIAM Review, 16(3), 309-339. https://doi.org/10.1007/s10107-012-0621-0. · Zbl 1286.90101
[45] Wu, B., Sun, X., Li, D., & Zheng, X. (2015). Tight MIQP reformulations for semi-continuous quadratic programming: Lift-and-convexification approach. arXiv:1507.05708v1 [math.OC]
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.