×
Armand, Paul

Finding all maximal efficient faces in multiobjective linear programming. (English) Zbl 0795.90054

Math. Program. 61, No. 3 (A), 357-375 (1993).
Summary: An algorithm for finding the whole efficient set of a multiobjective linear program is proposed. From the set of efficient edges incident to a vertex , a characterization of maximal efficient faces containing the vertex is given. By means of the lexicographic selection rule of Dantzig, Orden and Wolfe, a connectedness property of the set of dual optimal bases associated to a degenerate vertex is proved. An application of this to the problem of enumerating all the efficient edges incident to a degenerate vertex is proposed. Our method is illustrated with numerical examples and comparisons with Armand-Malivert’s algorithm show that this new algorithm uses less computer time.

Cited in 32 Documents

MSC:

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

Keywords:

degeneracy; simplex algorithm; efficient set; multiobjective linear program; maximal efficient faces; lexicographic selection rule; connectedness
PDF BibTeX XML Cite
\textit{P. Armand}, Math. Program. 61, No. 3 (A), 357--375 (1993; Zbl 0795.90054)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] A.V. Aho, J.E. Hopcroft and J.D. Ullman,The Design and Analysis of Computer Algorithms (Addison-Wesley, Reading, MA, 1974). · Zbl 0326.68005
[2] P. Armand and C. Malivert, ”Determination of the efficient set in multiobjective linear programming,”Journal of Optimization Theory and Applications 70 (1991) 467–489. · Zbl 0793.90064
[3] M.L. Balinski, ”On the graph structure of convex polyhedra inn-space,”Pacific Journal of Mathematics 11 (1961) 431–434. · Zbl 0103.39602
[4] H.P. Benson, ”Finding an initial efficient extreme point for a linear multiple objective program,”Journal of the Operational Research Society 32 (1981) 495–498. · Zbl 0454.90075
[5] A. Brondsted,An Introduction to Convex Polytopes (Springer, New York, 1983).
[6] G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).
[7] J.G. Ecker and N.S. Hegner, ”On computing an initial efficient extreme point,”Journal of the Operational Research Society 29 (1978) 1005–1007. · Zbl 0385.90104
[8] J.G. Ecker, N.S. Hegner and I.A. Kouada, ”Generating all maximal efficient faces for multiple objective linear programs,”Journal of Optimisation Theory and Applications 30 (1980) 353–381. · Zbl 0393.90087
[9] J.G. Ecker and I.A. Kouada, ”Finding efficient points for linear multiple objective programs,”Mathematical Programming 8 (1975) 375–377. · Zbl 0385.90105
[10] J.G. Ecker and I.A. Kouada, ”Finding all efficient extreme points for multiple objective linear programs,”Mathematical Programming 14 (1978) 249–261. · Zbl 0385.90105
[11] J.G. Ecker and N.E. Shoemaker, ”Selecting subsets from the set of nondominated vectors in multiple objective linear programming”,SIAM Journal on Control and Optimization 19 (1981) 505–515. · Zbl 0457.90072
[12] J.P. Evans and R.E. Steuer, ”A revised simplex method for linear multiple objective programs,”Mathematical Programming 5 (1973) 54–72. · Zbl 0281.90045
[13] T. Gal, ”A general method for determining the set of all efficient solutions to a linear vector maximum problem,”European Journal of Operational Research 1 (1977) 307–322. · Zbl 0374.90044
[14] T. Gal, ”On the structure of the set bases of a degenerate point,”Journal of Optimisation Theory and Applications 45 (1985) 577–589. · Zbl 0542.90091
[15] B. Grünbaum,Convex Polytopes (Wiley-Interscience, London, 1967).
[16] G. Hadley,Linear Programming (Addison-Wesley, Reading, MA, 1963).
[17] R. Hartley, ”Survey of algorithms for vector optimization problems,” in: S. French, R. Hartley, L.C. Thomas and D.J. White, eds.,Multi-objective Decision Making (Academic Press, London, 1983) pp. 1–34. · Zbl 0556.90084
[18] H. Isermann, ”The enumeration of the set of all efficient solutions for a linear multiple objective program,”Operational Research Quarterly 28 (1977) 711–725. · Zbl 0372.90086
[19] H.J. Kruse, ”Degeneracy graphs and the neighbourhood problem,”Lecture Notes in Economics and Mathematical Systems No. 260 (Springer, Berlin, 1986). · Zbl 0587.90062
[20] K.G. Murty, ”Faces of polyhedron,”Mathematical Programming Study 24 (1985) 30–42. · Zbl 0591.90082
[21] J. Philip, ”Algorithms for the vector maximization problem,”Mathematical Programming 2 (1973) 207–229. · Zbl 0288.90052
[22] R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970). · Zbl 0193.18401
[23] R.E. Steuer,Multiple Criteria Optimization: Theory, Computation, and Application (Wiley, New York, 1986). · Zbl 0663.90085
[24] P.L. Yu,Multiple-Criteria Decision Making (Plenum, New York, 1985). · Zbl 0643.90045
[25] P.L. Yu and M. Zeleny, ”The set of all non-dominated solutions in linear cases and a multicriteria simplex method,”Journal of Mathematical Analysis and Applications 49 (1975) 430–468. · Zbl 0313.65047
[26] M. Zeleny, ”Linear multi-objective programming,”Lecture Notes in Economics and Mathematical Systems No. 95 (Springer, Berlin, 1974). · Zbl 0325.90033
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.