×

A survey of recent developments in multiobjective optimization. (English) Zbl 1146.90060

Summary: Multiobjective Optimization (MO) has many applications in such fields as the Internet, finance, biomedicine, management science, game theory and engineering. However, solving MO problems is not an easy task. Searching for all Pareto optimal solutions is expensive and a time consuming process because there are usually exponentially large (or infinite) Pareto optimal solutions. Even for simple problems determining whether a point belongs to the Pareto set is \(\mathcal{NP}\)-hard. In this paper, we discuss recent developments in MO. These include optimality conditions, applications, global optimization techniques, the new concept of epsilon Pareto optimal solution, and heuristics.

MSC:

90C29 Multi-objective and goal programming

Software:

Knapsack
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Aghezzaf, B., & Hachimi, M. (2000). Generalized invexity and duality in multiobjective programming problems. Journal of Global Optimization, 18, 91–101. · Zbl 0970.90087
[2] Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: theory, algorithms, and applications. Jersey: New Prentice–Hall. · Zbl 1201.90001
[3] Ansoff, H. I. (1968). Corporate strategy. Harmandsworth: Penguin.
[4] Bell, D. E., & Raiffa, H. (1988). Risky choice revisited. In D. E. Bell, H. Raiffa & A. Tversky (Eds.), Decision making: descriptive, normative and prescriptive interactions (pp. 99–112). Cambridge: Cambridge University Press. · Zbl 0694.90001
[5] Bhaskar, K. (1979). A multiple objective approach to capital budgeting. Accounting and Business Research, 9, 25–46.
[6] Bitran, G. R. (1977). Linear multiple objective programs with zero-one variables. Mathematical Programming, 13, 121–139. · Zbl 0377.90070
[7] Bitran, G. R. (1979). Theory and algorithms for linear multiple objective programs with zero-one variables. Mathematical Programming, 17, 362–390. · Zbl 0419.90076
[8] Bitran, G. R. (1981). Duality for nonlinear multi-criteria optimization problems. Journal of Optimization Theory and Applications, 35, 367–401. · Zbl 0445.90082
[9] Bouri, A., Martel, J. M., & Chabchoub, H. (2002). A multi-criterion approach for selecting attractive portfolio. Journal of Multi-Criteria Decision Analysis, 11, 269–277. · Zbl 1141.91418
[10] Brumbaugh-Smith, J., & Shier, D. (1989). An empirical investigation of some bicriterion-shortest path algorithms. European Journal of Operational Research, 43, 216–224. · Zbl 0681.90081
[11] Camerini, P.M., Galbiati, G., & Maffioli, F. (1984). The complexity of multi-constrained spanning tree problems. In Theory of algorithms (pp. 53–101). Colloquium Pecs 1984. · Zbl 0606.68060
[12] Chalmet, L. G., Lemonidis, L., & Elzinga, D. J. (1986). An algorithm for the bi-criterion integer programming problem. European Journal of Operations Research, 25, 292–300. · Zbl 0592.90085
[13] Chankong, V., & Haimes, Y. Y. (1983). Multiobjective decision making theory and methodology. New York: Elsevier Science. · Zbl 0622.90002
[14] Cloquette, J. F., Gerard, M., & Hadhri, M. (1995). An empirical analysis of Belgian daily returns using GARCH models. Cahiers Economiques de Bruxelles, 418, 513–535.
[15] Corley, H. W. (1985). Efficient spanning trees. Journal of Optimization Theory and Applications, 45, 481–485. · Zbl 0544.05052
[16] Craven, B. D. (1981). Duality for the generalized convex fractional programs. In S. Schiable & W. T. Ziemba (Eds.), Generalized Concavity in Optimization and Economics (pp. 473–489). New York: Academic. · Zbl 0534.90089
[17] Das, L. N., & Nanda, S. (1997). Symmetric dual multiobjective programming. European Journal of Operational Research, 97, 167–171. · Zbl 0922.90120
[18] Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerical Mathematics, 1, 262–271. · Zbl 0092.16002
[19] Eben-Chaime, M. (1996). Parametric solution for linear bicriteria knapsack models. Management Science, 42, 1565–1575. · Zbl 0879.90162
[20] Egudo, R. (1989). Efficiency and generalized convex duality for multiobjective programs. Journal of Mathematical Analysis and Applications, 138, 84–94. · Zbl 0686.90039
[21] Ehrgott, M., & Gandibleux, X. (2000). A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum, 22, 425–460. · Zbl 1017.90096
[22] Etzioni, O., Hanks, S., Jiang, T., Karp, R. M., Madari, O., & Waarts, O. (1996). Efficient information gathering on the Internet. In Proceedings of the 37th IEEE symposium on foundations of computer science (pp. 234–243).
[23] Gandibleux, X., & Freville, A. (2000). Tabu search based procedure for solving the 0–1 multiobjective knapsack problem: the two objective case. Journal of Heuristics, 6, 361–383. · Zbl 0969.90079
[24] Garfinkel, R. S., & Nemhauser, G. L. (1972). Integer programming. New York: Wiley. · Zbl 0259.90022
[25] Geoffrion, A. M. (1968). Proper efficiency and the theory of vector maximization. Journal of Mathematical Analysis and Applications, 22, 618–630. · Zbl 0181.22806
[26] Hachimi, M., & Aghezzaf, B. (2004). Sufficiency and duality in differentiable multiobjective programming involving generalized type I functions. Journal of Mathematical Analysis and Applications, 296, 382–392. · Zbl 1113.90142
[27] Haimes, Y. Y., Lasdon, L. S., & Wismer, D. A. (1971). On a bicriterion formulation of the problems of integrated system identification and system optimization. IEEE Transactions on Systems, Man and Cybernetics, 1, 296–297. · Zbl 0224.93016
[28] Hamacher, H. W., & Ruhe, G. (1994). On spanning tree problems with multipleobjectives. Annals of Operations Research, 52, 209–230. · Zbl 0821.90126
[29] Hanson, M. A. (1961). A duality theorem in nonlinear programming with nonlinear constraints. Australian Journal of Statistics, 3, 67–71. · Zbl 0102.15601
[30] Hanson, M. A. (1981). On sufficiency of the Kuhn-Tucker conditions. Journal of Mathematical Analysis and Applications, 80, 545–550. · Zbl 0463.90080
[31] Henig, M. I. (1985). The shortest path problem with two objective functions. European Journal of Operational Research, 25, 281–291. · Zbl 0594.90087
[32] Hillermeier, C. (2001). Nonlinear multiobjective optimization: a generalized homotopy approach. Boston: Birkhauser Verlag. · Zbl 0966.90069
[33] Huarng, F., Pulat, P. S., & Shih, L. (1996). A computational comparison of some bicriterion shortest path algorithms. Journal of the Chinese Institution of Industrial Engineers, 13, 121–125.
[34] Hurson, C., & Zopounidis, C. (1995). On the use of multi-criteria decision aid methods to portfolio selection. Journal of Euro-Asian Management, 1, 69–94.
[35] Jacquillat, B. (1972). Les modèles d’évaluation et de sélection des valeurs mobilières: panorama des recherches américaines. Analyse Financière, 11, 68–88.
[36] Jahn, J. (2004). Vector optimization: theory, applications and extensions. Berlin: Springer. · Zbl 1055.90065
[37] Jeyakumar, V. (1985). Strong and weak invexity in mathematical programming. Methods of Operations Research, 55, 109–125. · Zbl 0566.90086
[38] Jeyakumar, V., & Mond, B. (1992). On generalized convex mathematical programming. Journal of the Australian Mathematical Society, Series B, 34, 43–53. · Zbl 0773.90061
[39] Ibaraki, T. (1987). Enumerative approaches to combinatorial optimization, part ii. Annals of Operations Research, 11, 343–602.
[40] Khan, Z., & Hanson, M. A. (1997). On ratio invexity in mathematical programming. Journal of Mathematical Analysis and Applications, 205, 330–336. · Zbl 0872.90094
[41] Khoury, N., Marte, J. M., & Veilleux, M. (1993). Methode multicritere de selection de portefeuilles indiciels interantionaux. Acualite Economique, 69, 171–190.
[42] Klamroth, K., & Wiecek, M. (2000a). Dynamic programming approaches to the multiple criteria knapsack problem. Naval Research Logistics, 47, 57–76. · Zbl 0956.90041
[43] Klamroth, K., & Wiecek, M. (2000b). Time-dependent capital budgeting with multiple criteria. In Y. Y. Haimes & R. E. Steuer (Eds.), Lecture notes in economics and mathematical systems: Vol. 487. Research and practice in multiple criteria decision making (pp. 421–432). Berlin: Springer. · Zbl 0960.90047
[44] Klamroth, K., Tind, J., & Zust, S. (2004). Integer programming duality in multiple objective programming. Journal of Global Optimization, 29, 1–18. · Zbl 1073.90041
[45] Klein, D., & Hannan, E. (1982). An algorithm for the multiple objective integer linear programming problem. European Journal of Operations Research, 93, 378–385. · Zbl 0477.90075
[46] Kostreva, M. M., & Wiecek, M. M. (1993). Time dependency in multiple objective dynamic programming. Journal of Mathematical Analysis and Applications, 173, 289–307. · Zbl 0805.90113
[47] Kruskal, J. B. (1956). On the shortest spanning tree of a graph and the traveling salesman problem. In Proceedings of American mathematical society 7 (pp. 48–50). · Zbl 0070.18404
[48] Kuhn, H. W., & Tucker, A. W. (1951). Nonlinear programming. In J. Neyman (Ed.), Proceedings of the second Berkeley symposium on mathematical statistics and probability (pp. 481–492). Los Angeles: University of California Press. · Zbl 0044.05903
[49] Lee, S. M., & Lerro, A. J. (1974). Capital budgeting for multiple objectives. Management Science, 36, 1106–1119. · Zbl 0707.90058
[50] Liang, Z. A., Huang, H. X., & Pardalos, P. M. (2001). Optimality conditions and duality for a class of nonlinear fractional programming problems. Journal of Optimization Theory and Applications, 110, 611–619. · Zbl 1064.90047
[51] Liang, Z. A., Huang, H. X., & Pardalos, P. M. (2003). Efficiency conditions and duality for a class of multiobjective fractional programming problems. Journal of Global Optimization, 27, 447–471. · Zbl 1106.90066
[52] Luc, D. T. (1984). On duality theory in multiobjective programming. Journal of Optimization Theory and Applications, 43, 557–582. · Zbl 0517.90076
[53] Luc, D. T., & Schaible, S. (1997). Efficiency and generalized concavity. Journal of Optimization Theory and Applications, 94, 147–153. · Zbl 0886.90121
[54] Maeda, T. (1994). Constraint qualifications in multiobjective optimization problems: differentiable case. Journal of Optimization Theory and Applications, 80, 483–500. · Zbl 0797.90083
[55] Markowitz, H. M. (1952). Portfolio selection. Journal of Finance, 7, 77–91.
[56] Martello, S., & Toth, P. (1990). Knapsack problems: algorithms and computer implementations. New York: Wiley. · Zbl 0708.68002
[57] Martello, S., Pisinger, D., & Toth, P. (1997). New trends in exact algorithms for the 0–1 knapsack problem. In J. Barceló (Ed.), Proceedings of EURO/IMFORMS-97 (pp. 151–160), Barcelona · Zbl 0961.90090
[58] Marusciac, I. (1982). On Fritz John type optimality criterion in multiobjective optimization. L’Analyse Numérique et la Theorie de l’Approximation, 11, 109–114. · Zbl 0501.90081
[59] Miettinen, K. M. (1999). Nonlinear multiobjective optimization. Boston: Kluwer Academic. · Zbl 0949.90082
[60] Mond, B., & Weir, T. (1981). Generalized concavity and duality. In S. Schaible & W. T. Ziemba (Eds.), Generalized convexity in optimization and economics (pp. 263–280). New York: Academic. · Zbl 0538.90081
[61] Nakayama, H. (1985). Duality theory in vector optimization: an overview, decision making with multiple objectives. In Y.Y. Haimes & V. Chankong (Eds.), Lecture Notes in Economics and Mathematical Systems (Vol. 337, pp. 109–125). Berlin: Springer.
[62] Papadimitriou, C. H., & Yannakakis, M. (2000). On the approximability of trade-offs and optimal access of web sources, In Proceedings of the 41st annual symposium on foundations of computer science (pp. 86–92).
[63] Pardalos, P. M., Siskos, Y., & Zopounidis, C. (Eds.). (1995). Advances in multicriteria analysis. Netherlands: Kluwer Academic. · Zbl 0847.00021
[64] Pareto, V. (1964). Course d’economie politique. Genève: Libraire Drotz. The first edition in 1986.
[65] Preda, V. (1992). On efficiency and duality for multiobjective programs. Journal of Mathematical Analysis and Applications, 166, 365–377. · Zbl 0764.90074
[66] Prim, R. C. (1957). Shortest connection networks and some generations. Bell System Technical Journal, 36, 1389–1401.
[67] Ramos, R. M., Aloso, S., Sicilia, J., & González, C. (1998). The problem of the optimal biobjective spanning tree. European Journal of Operational Research, 111, 617–628. · Zbl 0937.90112
[68] Reddy, L. V., & Mukherjee, R. N. (1999). Some results on mathematical programming with generalized ratio invexity. Journal of Mathematical Analysis and Applications, 240, 299–310. · Zbl 0946.90089
[69] Rosenblatt, M. J., & Sinuany-Stern, Z. (1989). Generating the discrete efficient frontier to the capital budgeting problem. Operations Research, 37, 38–394. · Zbl 0669.90009
[70] Ruíz-Canales, P., & Rufián-Lizana, A. (1995). A characterization of weakly efficient points. Mathematical Programming, 68, 205–212. · Zbl 0834.90109
[71] Sawaragi, Y., Nakayama, H., & Tanino, T. (1985). Theory of multiobjective optimization. Orlando: Academic. · Zbl 0566.90053
[72] Schweigert, D. (1990). Linear extensions and vector-valued spanning trees. Methods of Operations Research, 60, 219–222. · Zbl 0695.90095
[73] Serafini, P. (1986). Some considerations about computational complexity for multi objective combinatorial problems. In J. Jahn & W. Krabs (Eds.), Lecture notes in economics and mathematical systems: Vol. 294. Recent advances and historical development of vector optimization (pp. 222–231). Berlin: Springer.
[74] Singh, C., & Hanson, M. A. (1991). Multiobjective fractional programming duality theory. Naval Research Logistics, 38, 925–933. · Zbl 0749.90068
[75] Singh, C., Bhatia, D., & Rueda, N. (1996). Duality in nonlinear multiobjective programming using augmented Lagrangian functions. Journal of Optimization Theory and Applications, 88, 659–670. · Zbl 0851.90107
[76] Skriver, A. J. V., & Andersen, K. A. (2000). A label correcting approach for solving bicriterion shortest path problems. Computers and Operations Research, 27, 507–524. · Zbl 0955.90144
[77] Sniedovich, M. (1988). A multi-objective routing problem revisited. Engineering Optimization, 13, 99–108.
[78] Spronk, J., & Hallerbach, W. G. (1997). Financial modelling: where to go? With an illustration for portfolio management. European Journal of Operational Research, 99, 113–127. · Zbl 0952.91034
[79] Steuer, R. E. (1986). Multiple criteria optimization: theory, computation and application. New York: Wiley. · Zbl 0663.90085
[80] Steuer, R. E., & Na, P. (2003). Multiple criteria decision making combined with finance: a categorized bibliography. European Journal of Operational Research, 150, 496–515. · Zbl 1044.90043
[81] Tanina, T., & Sawaragi, Y. (1979). Duality theory in multiobjective programming. Journal of Optimization Theory and Applications, 27, 509–529. · Zbl 0378.90100
[82] Thanassoulis, E. (1985). Selecting a suitable solution method for a multiobjective programming capital budgeting problem. Journal of Business Finance and Accounting, 12, 453–471.
[83] Ulungu, E. L., & Teghem, J. (1994). Application of the two phases method to solve the bi-objective knapsack problem. Technical report, Dept. of Mathematics & Operational Research, Faculté Polytechnique de Mons, Mons, Belgium, 1994. · Zbl 0853.90098
[84] Ulungu, E. L., & Teghem, J. (1997). Solving multiobjective knapsack problems by a branch and bound procedure. In J. N. Climaco (Ed.), Multicriteria analysis (pp. 269–278). New-York: Springer. · Zbl 0899.90143
[85] Vial, J. P. (1983). Strong and weak convexity set and functions. Mathematics of Operations Research, 8, 231–259. · Zbl 0526.90077
[86] Villarreal, B., & Karwan, M. H. (1981). Multicriteria integer programming: a hybrid dynamic programming recursive approach. Mathematical Programming, 21, 204–223. · Zbl 0487.90086
[87] Visée, M., Teghem, J., Pirlot, M., & Ulungu, E. L. (1996). Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem. Technical report, Department of Mathematics & Operational Research, Faculté Polytechnique de Mons, Belgium, 1996. · Zbl 0908.90191
[88] Wang, S. (1991). Second-order necessary and sufficient conditions in multiobjective programming. Numerical functional Analysis and Applications, 12, 237–252. · Zbl 0764.90076
[89] Warburton, A. (1987). Approximation of a Pareto optima in multiple-objective shortest-path problems. Operations Research, 35, 70–79. · Zbl 0623.90084
[90] Weingartner, H. M. (1963). Mathematical programming and the analysis of capital budgeting problems. New Jersey: Prentice–Hall.
[91] Weir, T. (1990). A note on invex functions and duality in generalized fractional programming. Research report, Department of Mathematics, The University of New South Wales, ACT 2600, Australia. · Zbl 0726.90073
[92] Weir, T., & Mond, B. (1988). Symmetric and self duality in multiobjective programming. Asia-Pacific Journal of Operational Research, 5, 124–133. · Zbl 0719.90064
[93] Zadeh, L. (1963). Optimality and non-scalar-valued performance criteria. IEEE Transactions on Automatic Control, 8, 59–60.
[94] Zhou, G., & Gen, M. (1999). Genetic algorithm approach on multi-criteria minimum spanning tree problem. European Journal of Operational Research, 114, 141–152. · Zbl 0945.90009
[95] Zopounidis, C. (1999). Multicriteria decision aid in financial management. European Journal of Operational Research, 119, 404–415.
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.