×
Benson, H. P.; Sun, E.

Outcome space partition of the weight set in multiobjective linear programming. (English) Zbl 1028.90051

J. Optimization Theory Appl. 105, No. 1, 17-36 (2000).
Summary: Approaches for generating the set of efficient extreme points of the decision set of a multiple-objective linear program (P) that are based upon decompositions of the weight set \(W^0\) suffer from one of two special drawbacks. Either the required computations are redundant, or not all of the efficient extreme point set is found. This article shows that the weight set for problem (P) can be decomposed into a partition based upon the outcome set \(Y\) of the problem, where the elements of the partition are in one-to-one correspondence with the efficient extreme points of \(Y\). As a result, the drawbacks of the decompositions of \(W^0\) based upon the decision set of problem (P) disappear. The article explains also how this new partition offers the potential to construct algorithms for solving large-scale applications of problem (P) in the outcome space, rather than in the decision space.

Cited in 26 Documents

MSC:

90C29 Multi-objective and goal programming
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)

Keywords:

multiple-objective linear programming; vector maximization; efficient points; weight set

Software:

ADBASE
PDF BibTeX XML Cite
\textit{H. P. Benson} and \textit{E. Sun}, J. Optim. Theory Appl. 105, No. 1, 17--36 (2000; Zbl 1028.90051)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Steuer, R. E., Multiple-Criteria Optimization: Theory, Computation, and Application, John Wiley and Sons, New York, NY, 1986. · Zbl 0663.90085
[2] Armand, P., Finding All Maximal Efficient Faces in Multiobjective Linear Programming, Mathematical Programming, Vol. 61, pp. 357–375, 1993. · Zbl 0795.90054
[3] Armand, P., and Malivert, C., Determination of the Efficient Set in Multiobjective Linear Programming, Journal of Optimization Theory and Applications, Vol. 70, pp. 467–489, 1991. · Zbl 0793.90064
[4] 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
[5] Benson, H. P., Multiple-Objective Linear Programming with Parametric Criteria Coefficients, Management Science, Vol. 31, pp. 461–474, 1985. · Zbl 0625.90085
[6] Benson, H. P., and Sayin, S., Towards Finding Global Representations of the Efficient Set in Multiple-Objective Mathematical Programming, Naval Research Logistics, Vol. 44, pp. 47–67, 1997. · Zbl 0882.90116
[7] Chankong, V., and Haimes, Y. Y., Multiobjective Decision Making: Theory and Methodology, North-Holland, New York, NY, 1983. · Zbl 0622.90002
[8] Dauer, J. P., and Gallagher, R. J., A Combined Constraint-Space, Objective-Space Approach for Determining High-Dimensional Maximal Efficient Faces of Multiple-Objective Linear Programs, European Journal of Operational Research, Vol. 88, pp. 368–381, 1996. · Zbl 0913.90233
[9] Ecker, J. G., Hegner, N. S., and Kouada, 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
[10] Evans, G. W., An Overview of Techniques for Solving Multiobjective Mathematical Programs, Management Science, Vol. 30, pp. 1268–1282, 1984. · Zbl 0551.90090
[11] Evans, J. P., and Steuer, R. E., Generating Efficient Extreme Points in Linear Multiple-Objective Programming: Two Algorithms and Computing Experience, Multiple-Criteria Decision Making, Edited by J. L. Cochrane and M. Zeleny, University of South Carolina Press, Columbia, South Carolina, pp. 349–365, 1973.
[12] 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
[13] Geoffrion, A. M., Proper Efficiency and the Theory of Vector Maximization, Journal of Mathematical Analysis and Applications, Vol. 22, pp. 618–630, 1968. · Zbl 0181.22806
[14] Isermann, H., Proper Efficiency and Linear Vector Maximum Problem, Operations Research, Vol. 22, pp. 189–191, 1974. · Zbl 0274.90024
[15] 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
[16] Kuhn, H. W., and Tucker, A. W., Nonlinear Programming, Proceedings of the 2nd Berkeley Symposium on Mathematical Statistics and Probability, Edited by J. Neyman, University of California Press, Berkeley, California, pp. 481–492, 1951.
[17] Philip, J., Algorithms for the Vector Maximization Problem, Mathematical Programming, Vol. 2, pp. 207–229, 1972. · Zbl 0288.90052
[18] Sawaragi, Y., Nakayama, H., and Tanino, T., Theory of Multiobjective Optimization, Academic Press, Orlando, Florida, 1985. · Zbl 0566.90053
[19] Yu, P. L., Multiple-Criteria Decision Making, Plenum, New York, NY, 1985.
[20] Zeleny, M., Linear Multiobjective Programming, Springer Verlag, New York, NY, 1974. · Zbl 0325.90033
[21] Zionts, S., and Wallenius, J., Identifying Efficient Vectors: Some Theory and Computational Results, Operations Research, Vol. 28, pp. 785–793, 1980. · Zbl 0445.90079
[22] Benson, H. P., An Outer Approximation Algorithm for Generating All Efficient Extreme Points in the Outcome Set of a Multiple-Objective Linear Programming Problem, Journal of Global Optimization, Vol. 13, pp. 1–24, 1998. · Zbl 0908.90223
[23] Steuer, R. E., ADBASE Multiple-Objective Linear Programming Package, University of Georgia, Athens, Georgia, 1989.
[24] Benson, H. P., Generating the Efficient Outcome Set in Multiple-Objective Linear Programs: The Bicriteria Case, Acta Mathematica Vietnamica, Vol. 22, pp. 29–51, 1997. · Zbl 0895.90164
[25] Benson, H. P., Further Analysis of an Outcome Set-Based Algorithm for Multiple-Objective Linear Programming, Journal of Optimization Theory and Applications, Vol. 97, pp. 1–10, 1998. · Zbl 0907.90228
[26] Benson, H. P., Hybrid Approach for Solving Multiple-Objective Linear Programs in Outcome Space, Journal of Optimization Theory and Applications, Vol. 98, pp. 17–35, 1998. · Zbl 0908.90224
[27] Bitran, G. R., and Magnanti, T., The Structure of Admissible Points with Respect to Cone Dominance, Journal of Optimization Theory and Applications, Vol. 19, pp. 573–614, 1979. · Zbl 0389.52021
[28] Dauer, J. P., Analysis of the Objective Space in Multiple-Objective Linear Programming, Journal of Mathematical Analysis and Applications, Vol. 126, pp. 579–593, 1987. · Zbl 0631.90071
[29] Dauer, J. P., On Degeneracy and Collapsing in the Construction of the Set of Objective Values in a Multiple-Objective Linear Program, Annals of Operations Research, Vol. 47, pp. 279–292, 1993. · Zbl 0796.90046
[30] Dauer, J. P., and Liu, Y. H., Solving Multiple-Objective Linear Programs in Objective Space, European Journal of Operational Research, Vol. 46, pp. 350–357, 1990. · Zbl 0712.90063
[31] Dauer, J. P., and Saleh, O. A., A Representation of the Set of Feasible Objectives in Multiple-Objective Linear Programs, Linear Algebra and Its Applications, Vol. 166, pp. 261–275, 1992. · Zbl 0778.90059
[32] Gallagher, R. J., and Saleh, O. A., A Representation of an Efficiency Equivalent Polyhedron for the Objective Set of a Multiple-Objective Linear Program, European Journal of Operational Research, Vol. 80, pp. 204–212, 1995. · Zbl 0928.90080
[33] Epelman, M. S., On a Property of Polyhedral Sets, Mathematical Programming, Vol. 16, pp. 371–373, 1979. · Zbl 0404.52007
[34] Benson, H. P., A Geometrical Analysis of the Efficient Outcome Set in Multiple-Objective Convex Programs with Linear Criterion Functions, Journal of Global Optimization, Vol. 6, pp. 231–251, 1995. · Zbl 0835.90082
[35] Rockafellar, R. T., Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. · Zbl 0193.18401
[36] Horst, R., An Algorithm for Nonconvex Programming Problems, Mathematical Programming, Vol. 10, pp. 312–321, 1976. · Zbl 0337.90062
[37] Varaiya, P. P., Nonlinear Programming in Banach Space, SIAM Journal on Applied Mathematics, Vol. 15, pp. 284–293, 1967. · Zbl 0171.18004
[38] Benson, H. P., Admissible Points of a Convex Polyhedron, Journal of Optimization Theory and Applications, Vol. 38, pp. 341–361, 1982. · Zbl 0472.49010
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.