×

zbMATH — the first resource for mathematics

Computation of ideal and Nadir values and implications for their use in MCDM methods. (English) Zbl 1043.90039
Summary: We investigate the problem of finding the Nadir point for multicriteria optimization problems (MOP). The Nadir point is characterized by the componentwise maximal values of efficient points for MOP. It can be easily computed in the bicriteria case. However, in general this problem is very difficult. We review some existing methods and heuristics and also discuss some new ones. We propose a general method to compute Nadir values based on theoretical results on Pareto optimal solutions of subproblems with fewer criteria. The general scheme is valid for any number of criteria and practical for the case of three objectives. We also investigate the use of the Nadir point for compromise programming, when the goal is to be as far away as possible from the worst outcomes. We prove some results about (weak) Pareto optimality of the resulting solutions and present examples, which show the limitations of this idea, and therefore limitations of multicriteria methods using this type of problems.

MSC:
90B50 Management decision making, including multiple objectives
90C29 Multi-objective and goal programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Benayoun, R.; de Montgolfier, J.; Tergny, J.; Laritchev, O., Linear programming with multiple objective functions: step method (STEM), Mathematical programming, 1, 3, 366-375, (1971) · Zbl 0242.90026
[2] Benson, H.P., Optimization over the efficient set, Journal of mathematical analysis and applications, 98, 562-580, (1984) · Zbl 0534.90077
[3] Benson, H.P., An all-linear programming relaxation algorithm for optimizing over the efficient set, Journal of global optimization, 1, 1, 83-104, (1991) · Zbl 0739.90056
[4] Benson, H.P., A finite, nonadjacent extreme-point search algorithm for optimization over the efficient set, Journal of optimization theory and applications, 73, 1, 47-64, (1992) · Zbl 0794.90048
[5] Benson, H.P., A bisection-extreme point search algorithm for optimizing over the efficient set in the linear dependence case, Journal of global optimization, 3, 95-111, (1993) · Zbl 0799.90101
[6] Buchanan, J.T., A naive approach for solving MCDM problems, Journal of the operational research society, 45, 2, 202-206, (1997) · Zbl 0891.90141
[7] Chankong, V.; Haimes, Y.Y., Multiobjective decision making: theory and methodology, (1983), North-Holland Amsterdam · Zbl 0525.90085
[8] Choo, E.U.; Atkins, D.R., Proper efficiency in nonconvex multicriteria programming, Mathematics of operations research, 8, 3, 467-470, (1983) · Zbl 0523.90083
[9] Climaco, J.C.M.; Martins, E.Q.V., A bicriterion shortest path algorithm, European journal of operational research, 11, 399-404, (1982) · Zbl 0488.90068
[10] Corley, H.W., Efficient spanning trees, Journal of optimization theory and applications, 45, 3, 481-485, (1985) · Zbl 0544.05052
[11] Dauer, J.P., Optimization over the efficient set using an active constraint approach, Zeitschrift für operations research, 35, 185-195, (1991) · Zbl 0734.90081
[12] Dauer, J.P.; Fosnaugh, T.A., Optimization over the efficient set, Journal of global optimization, 7, 3, 261-277, (1995) · Zbl 0841.90107
[13] Ecker, J.G.; Song, J.H., Optimizing a linear function over an efficient set, Journal of optimization theory and applications, 83, 3, 541-563, (1994) · Zbl 0813.90101
[14] Ehrgott, M., Discrete decision problems, multiple criteria optimization classes and lexicographic MAX-ordering, (), 31-44 · Zbl 0923.90126
[15] Ehrgott, M., Integer solutions of multicriteria network flow problems, Investigaç ao operacional, 19, 229-243, (1999)
[16] Ehrgott, M., Approximation algorithms for combinatorial multicriteria optimization problems, International transactions in operational research, 7, 5-31, (2000)
[17] Ehrgott, M., Multicriteria optimization, () · Zbl 0956.90039
[18] Ehrgott, M.; Gandibleux, X., A survey and annotated bibliography of multiobjective combinatorial optimization, Operations research spektrum, 22, 425-460, (2000) · Zbl 1017.90096
[19] Eskandari, A.; Ffolliott, P.; Szidarovszky, F., Uncertainty and method choice in descrete multiobjective programming problems, Applied mathematics and computation, 69, 335-351, (1995) · Zbl 0832.65054
[20] Garey, M.R.; Johnson, D.S., Computers and intractability–A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[21] Hamacher, H.W.; Labbé, M.; Nickel, S., Multicriteria network location problems with sum objectives, Networks, 33, 79-92, (1999) · Zbl 0918.90097
[22] Hansen, P., Bicriterion path problems, (), 109-127
[23] Horst, R.; Thoai, N.V., Utility function programs and optimization over the efficient set in multiple-objective decision making, Journal of optimization theory and applications, 92, 3, 605-631, (1997) · Zbl 0871.90072
[24] Horst, R.; Thoai, N.V., Maximizing a concave function over the efficient or weakly-efficient set, European journal of operational research, 117, 2, 239-252, (1999) · Zbl 0998.90074
[25] Isermann, H.; Steuer, R.E., Computational experience cnocerning payoff tables and minimum criterion values over the efficient set, European journal of operational research, 33, 91-97, (1987) · Zbl 0632.90074
[26] Kok, M.; Lootsma, F.A., Pairwise comparison methods in multiple objective programming with applications in a long-term energy-planning model, European journal of operational research, 26, 1, 96-107, (1985) · Zbl 0578.90040
[27] Korhonen, P.; Salo, S.; Steuer, R.E., A heuristic for estimating nadir criterion values in multiple objective linear programming, Operations research, 45, 5, 751-757, (1997) · Zbl 0902.90138
[28] Lee, H.; Pulat, P.S., Bicriteria network flow problems: integer case, European journal of operational research, 66, 148-157, (1993) · Zbl 0780.90040
[29] Miettinen, K., Nonlinear multiobjective optimization, () · Zbl 0855.90114
[30] Ramos, R.M.; Alonso, S.; Sicilia, J.; González, C., The problem of the optimal biobjective spanning tree, European journal of operational research, 111, 617-628, (1998) · Zbl 0937.90112
[31] Reeves, G.R.; Reid, R.C., Minimum values over the efficient set in multiple objective decision making, European journal of operational research, 36, 3, 334-338, (1988)
[32] Sawaragi, Y.; Nakayama, H.; Tanino, T., Theory of multiobjective optimization, (1985), Academic Press Orlando, FL · Zbl 0566.90053
[33] Solanki, R.S.; Appino, P.A.; Cohon, J.L., Approximating the noninferior set in multiobjective linear programming problems, European journal of operational research, 68, 356-373, (1993) · Zbl 0782.90084
[34] Steuer, R.E., Multiple criteria optimization: theory, computation and application, (1985), John Wiley & Sons New York, NY
[35] Thach, P.T.; Konno, H.; Yokota, D., Dual approach to minimization of the set of Pareto-optimal solutions, Journal of optimization theory and applications, 88, 3, 689-707, (1996) · Zbl 0851.90109
[36] Thoai, N.V., Conical algorithm in global optimization for optimizing over efficient sets, Journal of global optimization, 18, 321-336, (2000) · Zbl 1026.90081
[37] E.L. Ulungu, Optimisation combinatoire multicritère: Détermination de l’ensemble des solutions efficaces et méthodes interactives, Ph.D. thesis, Faculté des Sciences, Université de Mons-Hainaut, Mons, Belgium, 1993
[38] Ulungu, E.L.; Teghem, J., The two-phases method: an efficient procedure to solve bi-objective combinatorial optimization problems, Foundations of computing and decision sciences, 20, 2, 149-165, (1994) · Zbl 0853.90097
[39] Visée, M.; Teghem, J.; Pirlot, M.; Ulungu, E.L., Two-phases method and branch and bound procedures to solve the bi-obective knapsack problem, Journal of global optimization, 12, 139-155, (1998) · Zbl 0908.90191
[40] Weistroffer, H.R., Careful usage of pessimistic values is needed in multiple objectives optimization, Operations research letters, 4, 1, 23-25, (1985) · Zbl 0569.90087
[41] Wierzbicki, A.P., On the completeness and constructiveness of parametric characterizations to vector optimization problems, OR spektrum, 8, 73-87, (1986) · Zbl 0592.90084
[42] Yu, P.L., Multiple criteria decision making: concepts, techniques and extensions, (1985), Plenum Press New York, NY
[43] Yu, P.L.; Zeleny, M., The set of all nondominated solutions in linear cases and a multicriteria simplex method, Journal of mathematical analysis and applications, 49, 430-468, (1975) · Zbl 0313.65047
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.