×

zbMATH — the first resource for mathematics

An extension of the non-inferior set estimation algorithm for many objectives. (English) Zbl 1441.90150
Summary: This work proposes a novel multi-objective optimization approach that globally finds a representative non-inferior set of solutions, also known as Pareto-optimal solutions, by automatically formulating and solving a sequence of weighted sum method scalarization problems. The approach is called MONISE (Many-Objective NISE) because it represents an extension of the well-known non-inferior set estimation (NISE) algorithm, which was originally conceived to deal with two-dimensional objective spaces. The proposal is endowed with the following characteristics: (1) uses a mixed-integer linear programming formulation to operate in two or more dimensions, thus properly supporting many (i.e., three or more) objectives; (2) relies on an external algorithm to solve the weighted sum method scalarization problem to optimality; and (3) creates a faithful representation of the Pareto frontier in the case of convex problems, and a useful approximation of it in the non-convex case. Moreover, when dealing specifically with two objectives, some additional properties are portrayed for the estimated non-inferior set. Experimental results validate the proposal and indicate that MONISE is competitive, in convex and non-convex (combinatorial) problems, both in terms of computational cost and the overall quality of the non-inferior set, measured by the acquired hypervolume.
MSC:
90C29 Multi-objective and goal programming
Software:
ASMO; NBI; SMS-EMOA; SPEA2
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bazgan, C.; Hugot, H.; Vanderpooten, D., Solving efficiently the 0-1 multi-objective knapsack problem, Computers & Operations Research, 36, 1, 260-279 (2009) · Zbl 1175.90323
[2] Benson, H. P., An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem, Journal of Global Optimization, 13, 1, 1-24 (1998) · Zbl 0908.90223
[3] Beume, N.; Naujoks, B.; Emmerich, M., SMS-EMOA: Multiobjective selection based on dominated hypervolume, European Journal of Operational Research, 181, 3, 1653-1669 (2007) · Zbl 1123.90064
[4] Bokrantz, R.; Forsgren, A., An algorithm for approximating convex Pareto surfaces based on dual techniques, INFORMS Journal on Computing, 25, 2, 377-393 (2013)
[5] Burachik, R. S.; Kaya, C. Y.; Rizvi, M. M., A new scalarization technique to approximate pareto fronts of problems with disconnected feasible sets, Journal of Optimization Theory and Applications, 162, 428-446 (2013) · Zbl 1298.90091
[6] Caballero, R.; Hernández, M., The controlled estimation method in the multiobjective linear fractional problem, Computers & Operations Research, 31, 11, 1821-1832 (2004) · Zbl 1073.90038
[7] Ceyhan, G.; Köksalan, M.; Lokman, B., Finding a representative nondominated set for multi-objective mixed integer programs, European Journal of Operational Research, 272, 1, 61-77 (2019) · Zbl 1403.90522
[8] Cohon, J. L.; Church, R. L.; Sheer, D. P., Generating multiobjective tradeâoffs: An algorithm for bicriterion problems, Water Resources Research, 15, 5, 1001-1010 (1979)
[9] Craft, D. L.; Halabi, T. F.; Shih, H. A.; Bortfeld, T. R., Approximating convex Pareto surfaces in multiobjective radiotherapy planning, Medical Physics, 33, 9, 3399-3407 (2006)
[10] Das, I.; Dennis, J., A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems, Structural Optimization, 14, 1, 63-69 (1997)
[11] Das, I.; Dennis, J., Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems, SIAM Journal on Optimization, 8, 3, 631-657 (1998) · Zbl 0911.90287
[12] Deb, K.; Jain, H., An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, part i: solving problems with box constraints, IEEE Transactions on Evolutionary Computation, 18, 4, 577-601 (2013)
[13] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 6, 2, 182-197 (2002)
[14] Ehrgott, M. M.; Shao, L. L.; Schöbel, A. A., An approximation algorithm for convex multi-objective programming problems, Journal of Global Optimization, 50, 3, 397-416 (2011) · Zbl 1242.90210
[15] Eichfelder, G., An adaptive scalarization method in multiobjective optimization, SIAM Journal on Optimization, 19, 4, 1694-1718 (2009) · Zbl 1187.90252
[16] Eichfelder, G., Scalarizations for adaptively solving multi-objective optimization problems, Computational Optimization and Applications, 44, 2, 249-273 (2009) · Zbl 1184.90152
[17] Fleischer, M., The measure of Pareto optima applications to multi-objective metaheuristics, Evolutionary Multi-Criterion Optimization, 17, 519-533 (2003) · Zbl 1036.90530
[18] Geoffrion, A. M., Proper efficiency and the theory of vector maximization, Journal of Mathematical Analysis and Applications, 22, 3, 618-630 (1968) · Zbl 0181.22806
[19] Ishibuchi, H.; Sakane, Y.; Tsukamoto, N.; Nojima, Y., Evolutionary many-objective optimization by NSGA-II and MOEA/D with large populations, IEEE International Conference on Systems, Man and Cybernetics, 1758-1763 (2009)
[20] Khorram, E.; Khaledian, K.; Khaledyan, M., A numerical method for constructing the Pareto front of multi-objective optimization problems, Journal of Computational and Applied Mathematics, 261, 158-171 (2014) · Zbl 1278.90359
[21] Kim, I.; Weck, O.; De Weck, O., Adaptive weighted sum method for multiobjective optimization: a new method for Pareto front generation, Structural and Multidisciplinary Optimization, 31, 2, 105-116 (2006) · Zbl 1245.90117
[22] Kirlik, G.; Sayin, S., A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems, European Journal of Operational Research, 232, 3, 479-488 (2014) · Zbl 1305.90368
[23] Klamroth, K.; Tind, J.; Wiecek, M. M., Unbiased approximation in multicriteria optimization, Mathematical Methods of Operations Research, 56, 3, 413-437 (2003) · Zbl 1064.90042
[24] Koski, J., Defectiveness of weighting method in multicriterion optimization of structures, Communications in Applied Numerical Methods, 1, May, 333-337 (1985) · Zbl 0586.73148
[25] Kukkonen, S.; Member, S.; Lampinen, J., Ranking-dominance and many-objective optimization, Proceedings of the IEEE congress on evolutionary computation, 3983-3990 (2007)
[26] Marler, R.; Arora, J., Survey of multi-objective optimization methods for engineering, Structural and Multidisciplinary Optimization, 26, 6, 369-395 (2004) · Zbl 1243.90199
[27] Marler, R.; Arora, J., The weighted sum method for multi-objective optimization: new insights, Structural and Multidisciplinary Optimization, 41, 6, 853-862 (2010) · Zbl 1274.90359
[28] Masin, M.; Bukchin, Y., Diversity maximization approach for multiobjective optimization, Operations Research, 56, 2, 411-424 (2008) · Zbl 1167.90644
[29] Messac, A.; Ismail-Yahaya, A.; Mattson, C., The normalized normal constraint method for generating the Pareto frontier, Structural and Multidisciplinary Optimization, 25, 2, 86-98 (2003) · Zbl 1243.90200
[30] Messac, A.; Mattson, C., Normal constraint method with guarantee of even representation of complete Pareto frontier, AIAA Journal, 42, 10, 2101-2111 (2004)
[31] Michalewicz, Z.; Arabas, J., Genetic algorithms for the 0/1 knapsack problem, Methodologies for Intelligent Systems, 869, 134-143 (1994)
[32] Miettinen, K., Nonlinear multiobjective optimization (1999), Springer · Zbl 0949.90082
[33] Nobakhtian, S.; Shafiei, N., A Benson type algorithm for nonconvex multiobjective programming problems, Top, 25, 2, 271-287 (2016) · Zbl 1372.90085
[34] Özlen, M.; Azizoglu, M. M., Multi-objective integer programming: A general approach for generating all non-dominated solutions, European Journal of Operational Research, 199, 1, 25-35 (2009) · Zbl 1176.90554
[35] Özlen, M.; Burton, B.; MacRae, C., Multi-objective integer programming: An improved recursive algorithm, Journal of Optimization Theory and Applications, 160, 470-482 (2014) · Zbl 1300.90044
[36] Özpeynirci, Ã.; Köksalan, M., An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs, Management Science, 56, 12, 2302-2315 (2010) · Zbl 1232.90329
[37] Rennen, G.; van Dam, E. R.; Hertog, D.den, Enhancement of sandwich algorithms for approximating higher-dimensional convex Pareto sets, INFORMS Journal on Computing, 23, 4, 493-517 (2011) · Zbl 1243.90204
[38] Romero, C.; Rehman, T., Multiobjective programming, (Romero, C.; Rehman, T., Multiple criteria analysis for agricultural decisions. Multiple criteria analysis for agricultural decisions, Developments in Agricultural Economics, 11 (2003), Elsevier), 47-61
[39] Ryu, J. H.; Kim, S.; Wan, H., Pareto front approximation with adaptive weighted sum method in multiobjective simulation optimization, Winter Simulation Conference, 623-633 (2009)
[40] Sanchis, J.; Martínez, M.; Blasco, X.; Salcedo, J. V., A new perspective on multiobjective optimization by enhanced normalized normal constraint method, Structural and Multidisciplinary Optimization, 36, 5, 537-546 (2007)
[41] Shao, L.; Ehrgott, M., Approximately solving multiobjective linear programmes in objective space and an application in radiotherapy treatment planning, Mathematical Methods of Operations Research, 68, 2, 257-276 (2008) · Zbl 1211.90217
[42] Smith, N. A., & Tromble, R. W. (2004). Sampling uniformly from the unit simplex naive algorithms. Johns Hopkins University, Technical Report(29), 1-6.
[43] Snyder, S.; ReVelle, C., Multiobjective grid packing model: an application in forest management, Location Science, 5, 3, 165-180 (1997) · Zbl 0915.90162
[44] Solanki, R. S.; Appino, P. A.; Cohon, J. L., Approximating the noninferior set in multiobjective linear programming problems, European Journal of Operational Research, 68, 3, 356-373 (1993) · Zbl 0782.90084
[45] Sylva, J.; Crema, A., A method for finding the set of non-dominated vectors for multiple objective integer linear programs, European Journal of Operational Research, 158, 1, 46-55 (2004) · Zbl 1061.90103
[46] Zitzler, E.; Laumanns, M.; Thiele, L., SPEA2: Improving the strength Pareto evolutionary algorithm, Evolutionary Methods for Design Optimization and Control with Applications to Industrial Problems, 95-100 (2001)
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.