×
Benson, H. P.

A finite, nonadjacent extreme-point search algorithm for optimization over the efficient set. (English) Zbl 0794.90048

J. Optimization Theory Appl. 73, No. 1, 47-64 (1992).
Summary: The problem (P) of optimizing a linear function over the efficient set of a multiple-objective linear program serves many useful purposes in multiple-criteria decision making. Mathematically, problem (P) can be classified as a global optimization problem. Such problems are much more difficult to solve than convex programming problems. In this paper, a nonadjacent extreme-point search algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact extreme-point optimal solution for the problem after a finite number of iterations. It can be implemented using only linear programming methods. Convergence of the algorithm is proven, and a discussion is included of its main advantages and disadvantages.

Cited in 45 Documents

MSC:

90C29 Multi-objective and goal programming
90C26 Nonconvex programming, global optimization
90C05 Linear programming

Keywords:

efficient set; multiple-objective linear program; global optimization; nonadjacent extreme-point search algorithm
PDF BibTeX XML Cite
\textit{H. P. Benson}, J. Optim. Theory Appl. 73, No. 1, 47--64 (1992; Zbl 0794.90048)
Full Text: DOI

References:

[1] Cohon, J. L.,Multiobjective Programming and Planning, Academic Press, New York, New York, 1978. · Zbl 0462.90054
[2] Evans, G. W.,An Overview of Techniques for Solving Multiobjective Mathematical Programs, Management Science, Vol. 30, pp. 1268-1282, 1984. · Zbl 0551.90090
[3] Goicoechea, A., Hansen, D. R., andDuckstein, L.,Multiobjective Decision Analysis with Engineering and Business Applications, John Wiley and Sons, New York, New York, 1982. · Zbl 0584.90045
[4] Hemming, T.,Multiobjective Decision Making under Certainty, Economic Research Institute, Stockholm School of Economics, Stockholm, Sweden, 1978.
[5] Rosenthal, R. E.,Principles of Multiobjective Optimization, Decision Sciences, Vol. 16, pp. 133-152, 1985.
[6] Roy, B.,Problems and Methods with Multiple Objective Functions, Mathematical Programming, Vol. 1, pp. 239-266, 1972. · Zbl 0254.90061
[7] Stadler, W.,A Survey of Multicriteria Optimization or the Vector Maximum Problem, Part 1: 1776-1960, Journal of Optimization Theory and Applications, Vol. 29, pp. 1-52, 1979. · Zbl 0388.90001
[8] Steuer, R. E.,Multiple Criteria Optimization: Theory, Computation, and Application, John Wiley and Sons, New York, New York, 1986. · Zbl 0663.90085
[9] Yu, P. L.,Multiple Criteria Decision Making, Plenum, New York, New York, 1985. · Zbl 0643.90045
[10] Zeleny, M.,Multiple Criteria Decision Making, McGraw-Hill, New York, New York, 1982. · Zbl 0588.90019
[11] Philip, J.,Algorithms for the Vector Maximization Problem, Mathematical Programming, Vol. 2, pp. 207-229, 1972. · Zbl 0288.90052
[12] Benson, H. P.,An All-Linear Programming Relaxation Algorithm for Optimizing over the Efficient Set, Journal of Global Optimization, Vol. 1, pp. 83-104, 1991. · Zbl 0739.90056
[13] Evans, J. P., andSteuer, 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.
[14] Marcotte, O., andSoland, R. M.,An Interactive Branch-and-Bound Algorithm for Multiple Criteria Optimization, Management Science, Vol. 32, pp. 61-75, 1986. · Zbl 0592.90057
[15] Steuer, R. E.,A Five-Phase Procedure for Implementing a Vector-Maximum Algorithm for Multiple Objective Linear Programming Problems, Multiple-Criteria Decision Making: Jouy-en-Josas, France, Edited by H. Thiriez and S. Zionts, Springer-Verlag, New York, New York, 1976. · Zbl 0335.90037
[16] Dessouky, M. I., Ghiassi, M., andDavis, W. J.,Estimates of the Minimum Nondominated Criterion Values in Multiple-Criteria Decision-Making, Engineering Costs and Production Economics, Vol. 10, pp. 95-104, 1986.
[17] Isermann, H., andSteuer, R. E.,Computational Experience Concerning Payoff Tables and Minimum Criteria Values over the Efficient Set, European Journal of Operational Research, Vol. 33, pp. 91-97, 1987. · Zbl 0632.90074
[18] Weistroffer, H. R.,Careful Use of Pessimistic Values Is Needed in Multiple Objectives Optimization, Operations Research Letters, Vol. 4, pp. 23-25, 1985. · Zbl 0569.90087
[19] Benayoun, R., de Montgolfier, J., Tergny, J., andLaritchev, O.,Linear Programming with Multiple Objective Functions: Step Method (STEM), Mathematical Programming, Vol. 1, pp. 366-375, 1971. · Zbl 0242.90026
[20] Belenson, S., andKapur, K. C.,An Algorithm for Solving Multicriterion Linear Programming Problems with Examples, Operational Research Quarterly, Vol. 24, pp. 65-77, 1973. · Zbl 0261.90035
[21] Kok, M., andLootsma, F. A.,Pairwise-Comparison Methods in Multiple Objective Programming, with Applications in a Long-Term Energy-Planning Model, European Journal of Operational Research, Vol. 22, pp. 44-55, 1985. · Zbl 0578.90040
[22] Benson, H. P.,On the Convergence of Two Branch-and-Bound Algorithms for Nonconvex Programming Problems, Journal of Optimization Theory and Applications, Vol. 36, pp. 129-134, 1982. · Zbl 0453.65046
[23] Horst, R.,An Algorithm for Nonconvex Programming Problems, Mathematical Programming, Vol. 10, pp. 312-321, 1976. · Zbl 0337.90062
[24] Horst, R.,Deterministic Global Optimization with Partition Sets Whose Feasibility Is Not Known: Application to Concave Minimization, Reverse Convex Constraints, DC Programming, and Lipschitzian Optimization, Journal of Optimization Theory and Applications, Vol. 58, pp. 11-37, 1988. · Zbl 0621.90064
[25] Horst, R.,Deterministic Global Optimization: Recent Advances and New Fields of Application, Naval Research Logistics, Vol. 37, pp. 433-471, 1990. · Zbl 0709.90093
[26] Horst, R.,A General Class of Branch-and-Bound Methods in Global Optimization with Some New Approaches for Concave Minimization, Journal of Optimization Theory and Applications, Vol. 51, pp. 271-291, 1986. · Zbl 0581.90073
[27] Horst, R., andTuy, H.,Global Optimization: Deterministic Approaches, Springer-Verlag, Berlin, Germany, 1990. · Zbl 0704.90057
[28] McCormick, G. P.,Computability of Global Solutions to Factorable Nonconvex Programs, Part 1: Convex Underestimating Problems, Mathematical Programming, Vol. 10, pp. 147-175, 1976. · Zbl 0349.90100
[29] Pardalos, P. M., andRosen, J. B.,Constrained Global Optimization: Algorithms and Applications, Springer-Verlag, Berlin, Germany, 1987. · Zbl 0638.90064
[30] Pardalos, P. M., andRosen, J. B.,Methods for Global Concave Minimization: A Bibliographic Survey, SIAM Review, Vol. 28, pp. 367-379, 1986. · Zbl 0602.90105
[31] Thoai, N. V., andTuy, H.,Convergent Algorithms for Minimizing a Concave Function, Mathematics of Operations Research, Vol. 5, pp. 556-566, 1980. · Zbl 0472.90054
[32] Benson, H. P.,Optimization over the Efficient Set, Journal of Mathematical Analysis and Applications, Vol. 98, pp. 562-580, 1984. · Zbl 0534.90077
[33] Ecker, J. G., andKouada, I. A.,Finding Efficient Points for Linear Multiple Objective Programs, Mathematical Programming, Vol. 8, pp. 375-377, 1975.
[34] Benson, H. P.,Existence of Efficient Solutions for Vector Maximization Problems, Journal of Optimization Theory and Applications, Vol. 26, pp. 569-580, 1978. · Zbl 0373.90085
[35] Spivey, W. A., andThrall, R. M.,Linear Optimization, Holt, Rinehart, and Winston, New York, New York, 1970.
[36] Murty, K. G.,Linear and Combinatorial Programming, John Wiley and Sons, New York, New York, 1976. · Zbl 0334.90032
[37] Rockafellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. · Zbl 0193.18401
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.