Abstract
A method called PAINT is introduced for computationally expensive multiobjective optimization problems. The method interpolates between a given set of Pareto optimal outcomes. The interpolation provided by the PAINT method implies a mixed integer linear surrogate problem for the original problem which can be optimized with any interactive method to make decisions concerning the original problem. When the scalarizations of the interactive method used do not introduce nonlinearity to the problem (which is true e.g., for the synchronous NIMBUS method), the scalarizations of the surrogate problem can be optimized with available mixed integer linear solvers. Thus, the use of the interactive method is fast with the surrogate problem even though the problem is computationally expensive. Numerical examples of applying the PAINT method for interpolation are included.
Similar content being viewed by others
References
Barber, C.B., Dobkin, D.P., Huhdanpää, H.: The Quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22, 469–483 (1996)
Bezerkin, V.E., Kamenev, G.K., Lotov, A.V.: Hybrid adaptive methods for approximating a nonconvex multidimensional Pareto frontier. Comput. Math. Math. Phys. 46, 1918–1931 (2006)
Brown, K.Q.: Voronoi diagrams from convex hulls. Inf. Process. Lett. 9, 223–228 (1979)
Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable multi-objective optimization test problems. In: IEEE International Conference on E-Commerce Technology, vol. 1, pp. 825–830 (2002)
Eaton, J.W.: GNU Octave Manual. Network Theory Limited (2002)
Edelsbrunner, H., Mücke, E.P.: Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Trans. Graph. 9, 66–104 (1990)
Efremov, R.V., Kamenev, G.K.: Properties of a method for polyhedral approximation of the feasible criterion set in convex multiobjective problems. Ann. Oper. Res. 166, 271–279 (2009)
Eskelinen, P., Miettinen, K., Klamroth, K., Hakanen, J.: Pareto navigator for interactive nonlinear multiobjective optimization. OR Spektrum 32, 211–227 (2010)
Goel, T., Vaidyanathan, R., Haftka, R.T., Shyy, W., Queipo, N.V., Tucker, K.: Response surface approximation of Pareto optimal front in multi-objective optimization. Comput. Methods Appl. Mech. Eng. 196, 879–893 (2007)
Grünbaum, B.: Convex Polytopes. Interscience, London (1967)
Hakanen, J., Miettinen, K., Sahlstedt, K.: Wastewater treatment: new insight provided by interactive multiobjective optimization. Decis. Support Syst. 51, 328–337 (2011)
Hartikainen, M., Miettinen, K., Wiecek, M.M.: Constructing a Pareto front approximation for decision making. Math. Methods Oper. Res. 73, 209–234 (2011)
Hartikainen, M., Miettinen, K., Wiecek, M.M.: Pareto front approximations for decision making with inherent non-dominance. In: Shi, Y., Wang, S., Kou, G., Wallenius, J. (eds.) New State of MCDM in the 21st Century, Selected Papers of the 20th International Conference on Multiple Criteria Decision Making 2009, pp. 35–46. Springer, Berlin (2011)
Hasenjäger, M., Sendhoff, B.: Crawling along the Pareto front: tales from the practice. In: The 2005 IEEE Congress on Evolutionary Computation (IEEE CEC 2005), pp. 174–181. IEEE Press, Piscataway (2005)
Hwang, C., Masud, A.S.M.: Multiple Objective Decision Making—Methods and Applications: a State-of-the-Art Survey. Springer, Berlin (1979)
Kamenev, G.K.: Study of an adaptive single-phase method for approximating the multidimensional Pareto frontier in nonlinear systems. Comput. Math. Math. Phys. 49, 2103–2113 (2009)
Keeney, R.L.: Value-Focused Thinking: a Path to Creative Decisionmaking. Harward University Press, Harward (1996)
Laukkanen, T., Tveit, T.-M., Ojalehto, V., Miettinen, K., Fogelholm, C.-J.: An interactive multi-objective approach to heat exchanger network synthesis. Comput. Chem. Eng. 34, 943–952 (2010)
Lotov, A.V., Bushenkov, V.A., Kamenev, G.A.: Interactive Decision Maps. Kluwer Academic, Boston (2004)
Luque, M., Ruiz, F., Miettinen, K.: Global formulation for interactive multiobjective optimization. OR Spektrum 33, 27–48 (2011)
Martin, J., Bielza, C., Insua, D.R.: Approximating nondominated sets in continuous multiobjective optimization problems. Nav. Res. Logist. 52, 469–480 (2005)
McMullen, P.: The maximum number of faces of a convex polytope. Mathematika 17, 179–184 (1970)
Miettinen, K.: Nonlinear Multiobjective Optimization. Kluwer Academic, Boston (1999)
Miettinen, K.: IND-NIMBUS for demanding interactive multiobjective optimization. In: Trzaskalik, T. (ed.) Multiple Criteria Decision Making’05, pp. 137–150. The Karol Adamiecki University of Economics in Katowice, Katowice (2006)
Miettinen, K., Mäkelä, M.: Interactive bundle-based method for nondifferentiable multiobjective optimization: NIMBUS. Optimization 34, 231–246 (1995)
Miettinen, K., Mäkelä, M.M.: On scalarizing functions in multiobjective optimization. OR Spektrum 24, 193–213 (2002)
Miettinen, K., Mäkelä, M.M.: Synchronous approach in interactive multiobjective optimization. Eur. J. Oper. Res. 170, 909–922 (2006)
Miettinen, K., Ruiz, F., Wierzbicki, A.P.: Introduction to multiobjective optimization: interactive approaches. In: Branke, J., Deb, K., Miettinen, K., Slowinski, R. (eds.) Multiobjective Optimization: Interactive and Evolutionary Approaches, pp. 27–57. Springer, Berlin (2008)
Monz, M.: Pareto navigation—algorithmic foundation of interactive multi-criteria IMRT planning. PhD thesis, University of Kaiserslautern (2006)
Ruzika, S., Wiecek, M.M.: Approximation methods in multiobjective programming. J. Optim. Theory Appl. 126, 473–501 (2005)
Sindhya, K., Deb, K., Miettinen, K.: Improving convergence of evolutionary multi-objective optimization with local search: a concurrent-hybrid algorithm. Nat. Comp. (to appear). doi:10.1007/s11047-011-9250-4
Viennet, R., Fonteix, C., Marc, I.: Multicriteria optimization using a genetic algorithm for determining a Pareto set. Int. J. Syst. Sci. 27, 255–260 (1996)
Wierzbicki, A.P.: On the completeness and constructiveness of parametric characterizations to vector optimization problems. OR Spektrum 8, 73–87 (1986)
Acknowledgements
We thank Mr. Karthik Sindhya for providing the Pareto optimal outcomes for the Viennet’s test problem. We also thank Dr. Jussi Hakanen for his help with the wastewater treatment planning problem.
This research was partly supported by the Academy of Finland (grant number 128495) and Jenny and Antti Wihuri Foundation.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hartikainen, M., Miettinen, K. & Wiecek, M.M. PAINT: Pareto front interpolation for nonlinear multiobjective optimization. Comput Optim Appl 52, 845–867 (2012). https://doi.org/10.1007/s10589-011-9441-z
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-011-9441-z