×

Stochastic multi-objective optimization: a survey on non-scalarizing methods. (English) Zbl 1331.90045

Summary: Currently, stochastic optimization on the one hand and multi-objective optimization on the other hand are rich and well-established special fields of Operations Research. Much less developed, however, is their intersection: the analysis of decision problems involving multiple objectives and stochastically represented uncertainty simultaneously. This is amazing, since in economic and managerial applications, the features of multiple decision criteria and uncertainty are very frequently co-occurring. Part of the existing quantitative approaches to deal with problems of this class apply scalarization techniques in order to reduce a given stochastic multi-objective problem to a stochastic single-objective one. The present article gives an overview over a second strand of the recent literature, namely methods that preserve the multi-objective nature of the problem during the computational analysis. We survey publications assuming a risk-neutral decision maker, but also articles addressing the situation where the decision maker is risk-averse. In the second case, modern risk measures play a prominent role, and generalizations of stochastic orders from the univariate to the multivariate case have recently turned out as a promising methodological tool. Modeling questions as well as issues of computational solution are discussed.

MSC:

90C15 Stochastic programming
90C29 Multi-objective and goal programming

Software:

ParadisEO-MOEO
Full Text: DOI

References:

[1] Abbas, M., & Bellahcene, F. (2006). Cutting plane method for multiple objective stochastic integer linear programming. European Journal of Operational Research, 168, 967-984. · Zbl 1083.90030 · doi:10.1016/j.ejor.2002.11.006
[2] Ahmed, S., Schütz, P., & Tomasgard, A. (2009). Supply chain design under uncertainty using sample average approximation and dual decomposition. European Journal of Operational Research, 199, 409-419. · Zbl 1176.90447 · doi:10.1016/j.ejor.2008.11.040
[3] Amodeo, L.; Prins, C.; Sanchez, D., Comparison of metaheuristic approaches for multi-objective simulation-based optimization in supply chain inventory management (2009), Berlin
[4] Armbruster, B., & Luedtke, J. B. (2011). Models and formulations for multivariate dominance constrained stochastic programs (Technical Report).
[5] Artzner, P., Delbaen, F., Eber, J., & Heath, D. (1999). Coherent measures of risk. Mathematical Finance, 9, 203-228. · Zbl 0980.91042 · doi:10.1111/1467-9965.00068
[6] Artzner, P., Delbaen, F., & Heath, D. (1997). Thinking coherently. Risk, 10, 68-71.
[7] Baesler, F. F.; Sepúlveda, J. A., Multi-objective simulation optimization for a cancer treatment center, 1405-1411 (2001)
[8] Basseur, M., & Zitzler, E. (2006). Handling uncertainty in indicator-based multiobjective optimization. International Journal of Computational Intelligence Research, 2, 255-272. · doi:10.5019/j.ijcir.2006.66
[9] Bath, S. K., Dhillon, J. S., & Kothari, D. P. (2004). Stochastic multiobjective generation dispatch. Electric Power Components and Systems, 32, 1083-1103. · doi:10.1080/15325000490441598
[10] Ben Abdelaziz, F. (1992). L’efficacité en programmation multi-objectifs stochastique. PhD thesis, Université de Laval, Québec.
[11] Ben Abdelaziz, F. (2012). Solution approaches for the multiobjective stochastic programming. European Journal of Operations Research, 216, 1-16. · Zbl 1242.90142 · doi:10.1016/j.ejor.2011.03.033
[12] Ben Abdelaziz, F., Aouni, B., & El Fayedh, R. (2007). Multiobjective stochastic programming for portfolio selection. European Journal of Operations Research, 177, 1811-1823. · Zbl 1102.90054 · doi:10.1016/j.ejor.2005.10.021
[13] Caballero, R., Cerda, E., Muños, M. M., & Rey, L. (2004). Stochastic approach versus multiobjective approach for obtaining efficient solutions in stochastic multiobjective programming problems. European Journal of Operational Research, 158, 633-648. · Zbl 1056.90081 · doi:10.1016/S0377-2217(03)00371-0
[14] Cardona-Valdés, Y., Álvarez, A., & Ozdemir, D. (2011). A bi-objective supply chain design problem with uncertainty. Transportation Research Part C, 19, 821-832. · doi:10.1016/j.trc.2010.04.003
[15] Chinchuluun, A., & Pardalos, P. M. (2007). A survey of recent developments in multiobjective optimization. Annals of Operations Research, 154, 29-50. · Zbl 1146.90060 · doi:10.1007/s10479-007-0186-0
[16] Dantzig, G. B. (1955). Linear programming under uncertainty. Management Science, 197-206. · Zbl 0995.90589
[17] Dentcheva, D., & Martinez, G. (2012). Two-stage stochastic optimization problems with stochastic ordering constraints on the recourse. European Journal of Operational Research, 219(1), 1-8. · Zbl 1244.90174 · doi:10.1016/j.ejor.2011.11.044
[18] Dentcheva, D., & Ruszczyński, A. (2003). Optimization with stochastic dominance constraints. SIAM Journal on Optimization, 14(2), 548-566. · Zbl 1055.90055 · doi:10.1137/S1052623402420528
[19] Dentcheva, D., & Ruszczyński, A. (2009). Optimization with multivariate stochastic dominance constraints. Mathematical Programming Series B, 117, 111-127. · Zbl 1221.90069 · doi:10.1007/s10107-007-0165-x
[20] Ding, H., Benyucef, L., & Xie, X. (2006). A simulation-based multi-objective genetic algorithm approach for networked enterprises optimization. Engineering Applications of Artificial Intelligence, 19, 609-623. · doi:10.1016/j.engappai.2005.12.008
[21] Ehrgott, M. (2000). Multicriteria optimization. Berlin: Springer. · Zbl 0956.90039 · doi:10.1007/978-3-662-22199-0
[22] Ehrgott, M., & Gandibleux, X. (2000). A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum, 22, 425-460. · Zbl 1017.90096 · doi:10.1007/s002910000046
[23] Eskandari, H., & Geiger, C. D. (2009). Evolutionary multiobjective optimization in noisy problem environments. Journal of Heuristics, 15, 559-595. · Zbl 1180.90287 · doi:10.1007/s10732-008-9077-z
[24] Eskandari, H.; Rabelo, L.; Mollaghasemi, M., Multiobjective simulation optimization using an enhanced genetic algorithm, Orlando, Florida · doi:10.1109/WSC.2005.1574329
[25] Fábián, C. I., Mitra, G., & Roman, D. (2011). Processing second order stochastic dominance models using cutting plane representations. Mathematical Programming, 130(1), 33-37. · Zbl 1229.90108 · doi:10.1007/s10107-009-0326-1
[26] Föllmer, H., & Schied, A. (2004). de Gruyter studies in mathematics: Vol.27. Stochastic finance—an introduction in discrete time. Berlin: de Gruyter. · Zbl 1126.91028 · doi:10.1515/9783110212075
[27] Fonseca, M., García-Sánchez, A., Ortega-Mier, M., & Saldanha da Gama, F. (2010). A stochastic bi-objective location model for strategic reverse logistics. TOP, 18, 158-184. · Zbl 1201.90113 · doi:10.1007/s11750-009-0107-2
[28] Gutjahr, W. J., Two metaheuristics for multiobjective stochastic combinatorial optimization, 116-125 (2005), Berlin · Zbl 1159.68641
[29] Gutjahr, W. J. (2009). A provably convergent heuristic for stochastic bicriteria integer programming. Journal of Heuristics, 15, 227-258. · Zbl 1172.90477 · doi:10.1007/s10732-008-9071-5
[30] Gutjahr, W. J. (2011). Recent trends in metaheuristics for stochastic combinatorial optimization. Central European Journal of Computer Science, 1, 58-66. · Zbl 1262.90115
[31] Gutjahr, W. J. (2012a). Multi-objective stochastic optimization under partial risk neutrality (Technical Report). Univ. of Vienna. · Zbl 1191.90018
[32] Gutjahr, W. J.; Zadnik Stirn, L. (ed.); Zerovnik, J. (ed.); Povh, J. (ed.); Drobne, S. (ed.); Lisec, A. (ed.), A note on the utility-theoretic justification of the Pareto approach in stochastic multi-objective combinatorial optimization, Dolenjske Toplice, Slovenia, September 28-30, 2012
[33] Gutjahr, W. J. (2012c). Runtime analysis of an evolutionary algorithm for stochastic multi-objective combinatorial optimization. Evolutionary Computation, 20, 395-421. · doi:10.1162/EVCO_a_00050
[34] Gutjahr, W. J. (2012d, accepted for publication). A three-objective optimization approach to cost effectiveness analysis under uncertainty. In Proc. OR2012 (international annual conference of the German operations research society 2012).
[35] Gutjahr, W. J., & Reiter, P. (2010). Bi-objective project portfolio selection and staff assignment under uncertainty. Optimization Methods & Software, 59, 417-445. · Zbl 1191.90018
[36] Haskell, W. B., Shanthikumar, J. G., & Shen, Z. M. (2012a). Aspects of increasing concave stochastic order constrained optimization (Technical Report). · Zbl 1180.90287
[37] Haskell, W. B., Shanthikumar, J. G., & Shen, Z. M. (2012b). Optimization with stochastic objectives (Technical Report). · Zbl 1390.65003
[38] Hassan-Pour, H. A., Mosadegh-Khah, M., & Tavakkoli-Moghaddam, R. (2009). Solving a multi-objective multi-depot stochastic location-routing problem by a hybrid simulated annealing algorithm. Proceedings of the Institution of Mechanical Engineers. Part B, Journal of Engineering Manufacture, 1045-1054. · Zbl 1172.90477
[39] Heitsch, H., Römisch, W., & Strugarek, C. (2006). Stability of multistage stochastic programs. SIAM Journal on Optimization, 17, 511-525. · Zbl 1165.90582 · doi:10.1137/050632865
[40] Hnaien, F., Delorme, X., & Dolgui, A. (2010). Multi-objective optimization for inventory control in two-level assembly systems under uncertainty of lead times. Computers & Operations Research, 20, 1835-1843. · Zbl 1188.90009 · doi:10.1016/j.cor.2009.06.002
[41] Homem-de Mello, T. (2003). Variable-sample methods for stochastic optimization. ACM Transactions on Modeling and Computer Simulation, 13, 108-133. · Zbl 1390.65003 · doi:10.1145/858481.858483
[42] Homem-de Mello, T., & Mehrotra, S. (2009). A cutting surface method for uncertain linear programs with polyhedral stochastic dominance constraints. SIAM Journal on Optimization, 20, 1250-1273. · Zbl 1198.90291 · doi:10.1137/08074009X
[43] Hu, J., Homem-de Mello, T., & Mehrotra, S. (2011). Risk-adjusted budget allocation models with application in homeland security. IIE Transactions, 43, 819-839. · doi:10.1080/0740817X.2011.578610
[44] Hu, J., Homem-de Mello, T., & Mehrotra, S. (2012). Sample average approximation of stochastic dominance constrained programs. Mathematical Programming, 133, 171-201. · Zbl 1259.90083 · doi:10.1007/s10107-010-0428-9
[45] Hughes, E. J., Evolutionary multi-objective ranking with uncertainty and noise, 329-343 (2001), Berlin
[46] Köksalan, M., Wallenius, J., & Zionts, S. (2011). Multiple criteria decision making: from early history to the 21st century. Singapore: World Scientific. · doi:10.1142/8042
[47] Koopmans, T. C., An analysis of production as an efficient combination of activities (1951), New York · Zbl 0045.09506
[48] Laumanns, M., Thiele, L., & Zitzler, E. (2006). An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method. European Journal of Operational Research, 169, 932-942. · Zbl 1079.90122 · doi:10.1016/j.ejor.2004.08.029
[49] Liefooghe, A.; Basseur, M.; Jourdan, L.; Talbi, E.-G., Combinatorial optimization of stochastic multi-objective problems: an application to the flow-shop scheduling problem, No. 4403, 457-471 (2007), Berlin · doi:10.1007/978-3-540-70928-2_36
[50] Liefooghe, A.; Basseur, M.; Jourdan, L.; Talbi, E.-G., ParadisEO-MOEO: a framework for evolutionary multi-objective optimization, No. 4403, 386-400 (2007), Berlin · doi:10.1007/978-3-540-70928-2_31
[51] Müller, A., & Stoyan, D. (2002). Wiley series in probability and statistics. Comparison methods for stochastic models and risks. Chichester: Wiley. · Zbl 0999.60002
[52] Norkin, V. I., Ermoliev, Y. M., & Ruszczyński, A. (1998). On optimal allocation of indivisibles under uncertainty. Operations Research, 46, 381-395. · Zbl 0987.90064 · doi:10.1287/opre.46.3.381
[53] Noyan, N., & Rudolf, G. (2012). Optimization with multivariate conditional value-at-risk constraints (Technical Report). · Zbl 1291.91124
[54] Ogryczak, W., & Ruszczyński, A. (1999). From stochastic dominance to mean-risk models: semideviations as risk measures. European Journal of Operational Research, 116, 33-50. · Zbl 1007.91513 · doi:10.1016/S0377-2217(98)00167-2
[55] Ogryczak, W., & Ruszczyński, A. (2001). On consistency of stochastic dominance and mean-semideviation models. Mathematical Programming Series B, 89, 217-232. · Zbl 1014.91021 · doi:10.1007/PL00011396
[56] Ogryczak, W., & Ruszczyński, A. (2002). Dual stochastic dominance and related mean-risk models. SIAM Journal on Optimization, 13(1), 60-78. · Zbl 1022.91017 · doi:10.1137/S1052623400375075
[57] Pflug, G. Ch. (2001). Scenario tree generation for multiperiod financial optimization by optimal discretization. Mathematical Programming, 89, 251-271. · Zbl 0987.91034 · doi:10.1007/PL00011398
[58] Pflug, G. Ch.; Ruszczyński, A. (ed.); Shapiro, A. (ed.), Stochastic optimization and statistical inference, No. 10, 427-482 (2003), Amsterdam · doi:10.1016/S0927-0507(03)10007-2
[59] Pflug, G. Ch., & Pichler, A. (2011). In International series in operations research & management science: Vol.163. Approximations for probability distributions and stochastic optimization problems (Chap. 15, pp. 343-387). New York: Springer. · Zbl 1405.90093
[60] Pflug, G. Ch., & Pichler, A. (2012). A distance for multistage stochastic optimization models. SIAM Journal on Optimization, 22, 1-23. · Zbl 1262.90118 · doi:10.1137/110825054
[61] Pflug, G. Ch., & Römisch, W. (2007). Modeling, measuring and managing risk. River Edge: World Scientific. · Zbl 1153.91023 · doi:10.1142/9789812708724
[62] Pflug, G. Ch., & Wozabal, N. (2010). Asymptotic distribution of law-invariant risk functionals. Finance and Stochastics, 14, 397-418. · Zbl 1226.91070 · doi:10.1007/s00780-009-0121-0
[63] Rath, S., Gendreau, M., & Gutjahr, W. J. (2012). Bi-objective stochastic programming models for determining depot locations in disaster relief operations planning (Technical Report). · Zbl 1348.90508
[64] Roman, D., Darby-Dowman, K., & Mitra, G. (2007). Mean-risk models using two risk measures: a multi-objective approach. Quantitative Finance, 7, 443-458. · Zbl 1190.91139 · doi:10.1080/14697680701448456
[65] Saaty, Th., & Gass, S. (1954). Parametric objective function (part i). Operations Research, 316-319. · Zbl 1414.90216
[66] Schultz, R., Risk aversion in two-stage stochastic integer programming, No. 150, 165-187 (2011), New York · Zbl 1246.90111 · doi:10.1007/978-1-4419-1642-6_8
[67] Shaked, M., & Shanthikumar, J. G. (2007). Springer series in statistics. Stochastic order. Berlin: Springer. · Zbl 1111.62016 · doi:10.1007/978-0-387-34675-5
[68] Shapiro, A., & Xu, H. (2007). Uniform laws of large numbers for set-valued mappings and subdifferentials of random functions. Mathematical Analysis and Applications, 325, 1390-1399. · Zbl 1109.60030 · doi:10.1016/j.jmaa.2006.02.078
[69] Shapiro, A., Ruszczyński, A., & Dentcheva, D. (2009). In MPS-SIAM series on optimization: Vol.9. Lectures on stochastic programming. · Zbl 1183.90005 · doi:10.1137/1.9780898718751
[70] Syberfeldt, A., Ng, A., John, R. I., & Moore, Ph. (2009). Multi-objective evolutionary simulation-optimisation of a real-world manufacturing problem. Robotics and Computer-Integrated Manufacturing, 25, 926-931. · doi:10.1016/j.rcim.2009.04.013
[71] Teich, J., Pareto-front exploration with uncertain objectives, 314-328 (2001), Berlin
[72] Tricoire, F., Graf, A., & Gutjahr, W. J. (2012). The bi-objective stochastic covering tour problem. Computers & Operations Research, 39, 1582-1592. · Zbl 1251.90361 · doi:10.1016/j.cor.2011.09.009
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.