Abstract
An approach to constructing a Pareto front approximation to computationally expensive multiobjective optimization problems is developed. The approximation is constructed as a sub-complex of a Delaunay triangulation of a finite set of Pareto optimal outcomes to the problem. The approach is based on the concept of inherent nondominance. Rules for checking the inherent nondominance of complexes are developed and applying the rules is demonstrated with examples. The quality of the approximation is quantified with error estimates. Due to its properties, the Pareto front approximation works as a surrogate to the original problem for decision making with interactive methods.
Similar content being viewed by others
References
Bezerkin VE, Kamenev GK, Lotov AV (2006) Hybrid adaptive methods for approximating a nonconvex multidimensional Pareto frontier. Comput Math Math Phys 46: 1918–1931
Boissonnant J-D (1984) Geometric structures for three-dimensional shape representation. ACM Trans Graph 3: 266–286
Caratheodory C (1913) Bedingt Konvergente Reihen und Konvexe Systeme. J für die reine und angewandte Mathematik 143: 128–175
Coello Coello CA, Van Veldhuizen DA, Lamont GB (2007) Evolutionary algorithms for solving multi-objective problems. Springer, New York
Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, Chichester
Deb K, Thiele L, Laumanns M, Zitzler E (2002) Scalable multi-objective optimization test problems. E-Commer Technol IEEE Int Conf 1: 825–830
Edelsbrunner H (1987) Algorithms in combinatorial geometry. Springer, New York
Edelsbrunner H (1998) Shape reconstruction with Delaunay complex. In: Lucchesi CL, Moura AV (eds) LATIN’98: theoretical informatics. Springer, Berlin, pp 119–132
Edelsbrunner H, Shah NR (1994) Triangulating topological spaces. In: SCG ’94: proceedings of the tenth annual symposium on computational geometry. ACM, New York, pp. 285–292
Efremov RV, Kamenev GK (2009) Properties of a method for polyhedral approximation of the feasible criterion set in convex multiobjective problems. Ann Oper Res 166: 271–279
Eskelinen P, Miettinen K, Klamroth K, Hakanen J (2010) Pareto navigator for interactive nonlinear multiobjective optimization. OR Spectr 23: 211–227
Fortune S (1997) Voronoi diagrams and Delaunay triangulations. In: Goodman JE, O’Rourke J Handbook of discrete and computational geometry. CRC Press, Boca Raton
Fukuda K (2004) Polyhedral computation FAQ. Swiss Federal Institute of Technology, http://www.ifor.math.ethz.ch/~fukuda/polyfaq/polyfaq.html
George P-L, Borouchaki H (1998) Delaunay triangulation and meshing: application to finite elements. Hermes, Paris
Goel T, Vaidyanathan R, Haftka RT, Shyy W, Queipo NV, Tucker K (2007) Response surface approximation of Pareto optimal front in multi-objective optimization. Comput Methods Appl Mech Eng 196: 879–893
Goodman, JE, O’Rourke, J (eds) (1997) Discrete and computational geometry. CRC Press, Boca Raton
Grünbaum B (1967) Convex polytopes. Interscience Publishers, London
Hartikainen M, Miettinen K, Wiecek MM (2011) Pareto front approximations for decision making with inherent non-dominance. In: Yong S, Shouyang W, Gang K, Wallenius J (eds) The proceedings of the MCDM2009 conference, lecture notes in economics and mathematical systems. Springer, Berlin. To Appear
Hasenjäger M, Sendhoff B (2005) Crawling along the Pareto front: tales from the practice. In: The 2005 IEEE congress on evolutionary computation (IEEE CEC 2005). IEEE Press, Piscataway, NJ, pp 174–181
Keeney RL, Raiffa H (1993) Decisions with multiple objectives. Cambridge University Press, Cambridge
Laukkanen T, Tveit T-M, Ojalehto V, Miettinen K, Fogelholm C-J (2010) An interactive multi-objective approach to heat exchanger network synthesis. Comput Chem Eng 34: 943–952
Lotov AV, Bushenkov VA, Kamenev GA (2004) Interactive decision maps. Kluwer, Boston
Luque M, Ruiz F, Miettinen K (2011) Global formulation for interactive multiobjective optimization. OR Spectr. 33: 27–48
Martin J, Bielza C, Insua DR (2005) Approximating nondominated sets in continuous multiobjective optimization problems. Nav Res Logist 52: 469–480
McMullen P (1970) The maximum number of faces of a convex polytope. Mathematika 17: 179–184
Miettinen K (1999) Nonlinear multiobjective optimization. Kluwer, Boston
Miettinen K, Mäkelä M (1995) Interactive bundle-based method for nondifferentiable multiobjective optimization: NIMBUS. Optimization 34: 231–246
Miettinen K, Mäkelä M (2000) Interactive multiobjective optimization system WWW-NIMBUS on the internet. Comput Oper Res 27: 709–723
Miettinen K, Mäkelä MM (2006) Synchronous approach in interactive multiobjective optimization. Eur J Oper Res 170: 909–922
Miettinen K, Ruiz F, Wierzbicki A (2008) Introduction to multiobjective optimization: interactive approaches. In: Branke J, Deb K, Miettinen K, Slowinski R (eds) Multiobjective optimization: interactive and evolutionary approaches. Springer, Berlin, pp 27–57
Monz M (2006) Pareto navigation—interactive multiobjective optimization and its applications in radiotherapy planning. Ph.D. thesis, University of Kaiserslautern
Rajan VT (1994) Optimality of the Delaunay triangulation in \({\mathbb R^d}\). Discret Comput Geom 12: 189–202
Ruzika S, Wiecek MM (2005) Approximation methods in multiobjective programming. J Optim Theory Appl 126: 473–501
Sawaragi Y, Nakayama H, Tanino T (1985) Theory of multiobjective optimization. Academic Press, Orlando
Schandl B, Klamroth K, Wiecek MM (2001) Norm-based approximation in bicriteria programming. Comput Optim Appl 20: 23–42
Schandl B, Klamroth K, Wiecek MM (2002) Norm-based approximation in multicriteria programming. Comput Math Appl 44: 925–942
Shenton D, Cendes Z (1985) Three-dimensional finite element mesh generation using Delaunay tesselation. IEEE Trans Magn 21: 2535–2538
Steuer RE (1986) Multiple criteria optimization: theory, computation and application. Wiley, New York
Steuer RE (1989) The Tchebycheff procedure of interactive multiple objective programming. In: Karpak B, Zionts S (eds) Multiple criteria decision making and risk analysis using micro computers. Springer, Berlin
Steuer RE, Choo E-U (1983) An interactive weighted Tchebycheff procedure for multiple objective programming. Math Program 26: 326–344
Vegter G (1997) Computational topology. In: Goodman JE, O’Rourke J (eds) Handbook of discrete and computational geometry. CRC Press, Boca Raton, pp 719–742
Wierzbicki A (1986) On the completeness and constructiveness of parametric characterizations to vector optimization problems. OR Spectr 8: 73–87
Yu PL, Zeleny M (1975) The set of all nondominated solutions in linear cases and a multicriteria simplex method. J Math Anal Appl 49: 430–468
Author information
Authors and Affiliations
Corresponding author
Additional information
On sabbatical leave from Department of Mathematical Sciences, Clemson University, Clemson, SC, USA. This research was partly supported by the Academy of Finland grant number 128495.
Rights and permissions
About this article
Cite this article
Hartikainen, M., Miettinen, K. & Wiecek, M.M. Constructing a Pareto front approximation for decision making. Math Meth Oper Res 73, 209–234 (2011). https://doi.org/10.1007/s00186-010-0343-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00186-010-0343-0