Determination of the efficient set in multiobjective linear programming. (English) Zbl 0793.90064

Armand, P.; Malivert, C.

J. Optimization Theory Appl. 70, No. 3, 467-489 (1991).

Summary: This paper develops a method for finding the whole set of efficient points of a multiobjective linear problem. Two algorithms are presented; the first one describes the set of all efficient vertices and all efficient rays of the constraint polyhedron, while the second one generates the set of all efficient faces. The method has been tested on several examples for which numerical results are reported.

MSC:

90C29	Multi-objective and goal programming
90C05	Linear programming

Keywords:

non-dominated faces; degeneracy; set of efficient points; multiobjective linear problem

References:

[1]	Zeleny, M.,Linear Multi-Objective Programming, Springer-Verlag, New York, New York, 1974. · Zbl 0325.90033
[2]	Evans, J. P., andSteuer, R. E.,A Revised Simplex Method for Linear Multiple Objective Programs, Mathematical Programming, Vol. 5, pp. 54-72, 1973. · Zbl 0281.90045
[3]	Steuer, R. E.,Multiple Criteria Optimization: Theory, Computation, and Applications, Wiley, New York, New York, 1986. · Zbl 0663.90085
[4]	Isermann, H.,The Enumeration of the Set of All Efficient Solutions for a Linear Multiple Objective Program, Operational Research Quarterly, Vol. 28, pp. 711-725, 1977. · Zbl 0372.90086
[5]	Ecker, J. G., andKouada, I. A.,Finding All Efficient Extreme Points for Multiple Objective Linear Programs, Mathematical Programming, Vol. 14, pp. 249-261, 1978. · Zbl 0385.90105
[6]	Hartley, R.,Survey of Algorithms for Vector Optimization Problems in Multi-Objective Decision Making, Multi-Objective Decision Making, Edited by S. French, R. Hartley, L. C. Thomas, and D. J. White, Academic Press, New York, New York, 1983.
[7]	Ecker, J. G., Hegner, N. S., andKouada, I. A.,Generating All Maximal Efficient Faces for Multiple Objective Linear Programs, Journal of Optimization Theory and Applications, Vol. 30, pp. 353-381, 1980. · Zbl 0393.90087
[8]	Gal, T.,A General Method for Determining the Set of All Efficient Solutions to a Linear Vector Maximum Problem, European Journal of Operational Research, Vol. 1, pp. 307-322, 1977. · Zbl 0374.90044
[9]	Ziont, S., andWallenius, J.,Identifying Efficient Vectors: Some Theory and Computational Results, Operations Research, Vol. 28, pp. 785-793, 1980. · Zbl 0445.90079
[10]	Philip, J.,Algorithms for the Vector Maximization Problem, Mathematical Programming, Vol. 2, pp. 207-229, 1973. · Zbl 0288.90052
[11]	Dantzig, G. B.,Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey, 1963. · Zbl 0108.33103
[12]	Ecker, J. G., andKouada, I. A.,Finding Efficient Points for Linear Multiple Objective Problems, Mathematical Programming, Vol. 8, pp. 375-377, 1975.
[13]	Benson, H. P.,Finding an Initial Efficient Extreme Point for a Linear Multiple Objective Program, Journal of the Operational Research Society, Vol. 32, pp. 495-498, 1981. · Zbl 0454.90075
[14]	Aho, A. V., Hopcroft, J. E., andUllman, J. D.,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Massachusetts, 1974. · Zbl 0326.68005
[15]	Yu, P. L., andZeleny, M.,The Set of All Nondominated Solutions in Linear Cases and a Multicriteria Simplex Method, Journal of Mathematical Analysis and Applications, Vol. 49, pp. 430-468, 1975. · Zbl 0313.65047
[16]	Ecker, J. G., andShoemaker, N. E.,Selecting Subsets from the Set of Nondominated Vectors in Multiple Objective Linear Programming, SIAM Journal on Control and Optimization, Vol. 19, pp. 505-515, 1981. · Zbl 0457.90072
[17]	Gal, T.,On the Structure of the Set Basis of a Degenerate Point, Journal of Optimization Theory and Applications, Vol. 45, pp. 577-589, 1985. · Zbl 0542.90091
[18]	Kruse, H. J.,Degeneracy Graphs and the Neighborhood Problem, Springer-Verlag, New York, New York, 1986. · Zbl 0587.90062