Abstract
Multi-objective optimization algorithms can generate large sets of Pareto optimal (non-dominated) solutions. Identifying the best solutions across a very large number of Pareto optimal solutions can be a challenge. Therefore it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optimal solutions. This paper analyzes a discrete optimization problem introduced to obtain optimal subsets of solutions from large sets of Pareto optimal solutions. This discrete optimization problem is proven to be NP-hard. Two exact algorithms and five heuristics are presented to address this problem. Five test problems are used to compare the performances of these algorithms and heuristics. The results suggest that preferred subset of Pareto optimal solutions can be efficiently obtained using the heuristics, while for smaller problems, exact algorithms can be applied.
Similar content being viewed by others
References
Coello, C.A., Van Veldhuizen, D.A., Lamont, G.B.: Evolutionary Algorithms for Solving Multi-objective Problems. Kluwer Academic, New York (2002)
Das, I.: A preference ordering among various Pareto optimal alternatives. Struct. Optim. 18(1), 30–35 (1999)
Ehrgott, M.: Multicriteria Optimization. Springer, Berlin (2005)
Ehrgott, M., Gandibleux, X. (eds.): Multiple Criteria Optimization: State of the Art Annotated Bibliographic Surveys. Kluwer Academic, Boston (2002)
Kao, G.K., Jacobson, S.H.: Post-optimality algorithms and heuristic for multi-objective optimization. Technical report, Department of Computer Science, University of Illinois, Urbana, IL (2006)
Kasprzak, E.M., Lewis, K.E.: An approach to facilitate decision tradeoffs in Pareto sets. J. Eng. Valuat. Cost Anal. 3(1), 173–187 (2000)
Kasprzak, E.M., Lewis, K.E.: Pareto analysis in multiobjective optimization using the collinearity theorem and scaling method. Struct. Multidiscip. Optim. 22(3), 208–218 (2001)
Korhonen, P., Halme, M.: Supporting the decision maker to find the most preferred solutions for a MOLP-problem. In: Proceedings of the 9th International Conference on Multiple Criteria Decision Making, Fairfax, VA, pp. 173–183
Mattson, C.A., Mulur, A.A., Messac, A.: Smart Pareto filter: obtaining a minimal representation of multiobjective design space. Eng. Optim. 36(6), 721–740 (2004)
Messac, A., Ismail-Yahaya, A., Mattson, C.A.: The normalized normal constraint method for generating the Pareto frontier. Struct. Multidiscip. Optim. 25(2), 86–98 (2003)
Messac, A., Mattson, C.A.: Normal constraint method with guarantee of even representation of complete Pareto frontier. AIAA J. 42(10), 2101–2111 (2004)
Miettinen, K.M.: Nonlinear Multiobjective Optimization. Kluwer Academic, Boston (1999)
Miettinen, K.M., Mäkelä, M.M.: Interactive multiobjective optimization system WWW-NIMBUS on the Internet. Comput. Oper. Res. 27, 709–723 (2000)
Narula, S.C., Kirilov, L., Vassilev, V.: An interactive algorithm for solving multiple objective nonlinear programming problems. In: Proceedings of the 10th International Joint Conference on Multiple Criteria Decision Making, Taipei, Taiwan, pp. 119–127
Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Appl. Math. 131, 651–654 (2003)
Van Veldhuizen, D.A.: Multiobjective evolutionary algorithms: classifications, analyses, and new innovations. Ph.D. thesis, Department of Electrical and Computer Engineering, Graduate School of Engineering, Air Force Institute of Technology, Wright-Patterson AFB, OH (1999)
Venkat, V., Jacobson, S.H., Stori, J.A.: A post-optimality analysis algorithm for multi-objective optimization. Comput. Optim. Appl. 28, 357–372 (2004)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kao, G.K., Jacobson, S.H. Finding preferred subsets of Pareto optimal solutions. Comput Optim Appl 40, 73–95 (2008). https://doi.org/10.1007/s10589-007-9070-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-007-9070-8