Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
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.
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.
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.
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.
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.
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.
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.
ARINA: Computational cluster from izo-sgi, sgiker (upv/ehu) (2017). http://www.ehu.eus/sgi/recursos/cluster-arina.
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.
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).
Boyd, S., & Vandenberghe, L. (2009). Convex optimization. Cambridge: Cambridge University Press (Seventh printing with corrections 2009)
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.
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.
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.
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.
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.
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.
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.
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.
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.
Felt, A. (2003). Test-problem collection for stochastic linear programming. https://www4.uwsp.edu/math/afelt/slptestset/download.html.
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.
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/.
Gantmacher, F. R. (1959). The theory of matrices. New York: Chelsea Publishing Company.
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.
Holmes, D. (2017). A (PO)rtable (S)tochastic programming (T)est (S)et (POSTS). http://users.iems.northwestern.edu/~jrbirge/html/dholmes/post.html.
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.
IBM ILOG: CPLEX v12.6.3. (2017). http://www.ilog.com/products/cplex.
Kall, P., & Wallace, S. W. (1994). Stochastic Programming. Hoboken: Wiley.
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.
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.
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.
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.
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.
Neise, F. (2008). Risk management in stochastic integer programming. New York: Vieweg+Teubner Verlag.
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.
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.
Pflug, G. C., & Römisch, W. (2007). Modeling, measuring and managing risk. Singapore: World Scientific Publishing Co. Inc.
Pochet, Y., & Wolsey, L. A. (2006). Production planning by mixed integer programming. New York: Springer. https://doi.org/10.1007/0-387-33477-7.
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.
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.
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.
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.
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.
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]
Acknowledgements
The authors thank for technical and human support provided by IZO-SGI SGIker of UPV/EHU and European funding (ERDF and ESF).
Author information
Authors and Affiliations
Corresponding author
Additional information
This research has been partially supported by the Spanish Ministry of Economy and Competitiveness and the European Regional Development Fund through project MTM2015-65317-P (MINECO/FEDER/EU); via BCAM Severo Ochoa excellence accreditation Grant SEV-2013-0323; by the Bizkaia Talent and EC COFUND program, request AYD-000-280; by the Basque Government through the BERC 2014-2017 program and Grupo de Investigación IT-928-16; and by the University of the Basque Country UPV/EHU through its UFI BETS 2011 program.
Rights and permissions
About this article
Cite this article
Aldasoro, U., Merino, M. & Pérez, G. Time consistent expected mean-variance in multistage stochastic quadratic optimization: a model and a matheuristic. Ann Oper Res 280, 151–187 (2019). https://doi.org/10.1007/s10479-018-3032-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-018-3032-7
Keywords
- Branch-and-Fix Coordination
- Expected Conditional Risk Measures
- Matheuristic algorithms
- McCormick relaxation
- Multistage stochastic optimization
- Quadratic mixed 0–1 programming
- Production planning
- Time consistent risk aversion