×
Benson, Harold P.

An all-linear programming relaxation algorithm for optimizing over the efficient set. (English) Zbl 0739.90056

J. Glob. Optim. 1, No. 1, 83-104 (1991).
Summary: The problem (P) of optimizing a linear function over the efficient set of a multiple objective linear program has many important applications in multiple criteria decision making. Since the efficient set is in general a nonconvex set, problem (P) can be classified as a global optimization problem. Perhaps due to its inherent difficulty, it appears that no precisely-delineated implementable algorithm exists for solving problem (P) globally. A relaxation algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact optimal solution to the problem after a finite number of iterations. A detailed discussion is included of how to implement the algorithm using only linear programming methods. Convergence of the algorithm is proven, and a sample problem is solved.

Cited in 41 Documents

MSC:

90C29 Multi-objective and goal programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90B50 Management decision making, including multiple objectives

Keywords:

efficient set of a multiple objective linear program; multiple criteria decision making; relaxation algorithm; globally optimal solution; Convergence
PDF BibTeX XML Cite
\textit{H. P. Benson}, J. Glob. Optim. 1, No. 1, 83--104 (1991; Zbl 0739.90056)
Full Text: DOI

References:

[1] Al-Khayyal, F. A. and Falk, J. E. (1983), Jointly Constrained Biconvex Programming, Mathematics of Operations Research 8, 273-286. · Zbl 0521.90087
[2] Belenson, S. and Kapur, K. C. (1973), An Algorithm for Solving Multicriterion Linear Programming Problems with Examples, Operational Research Quarterly 24, 65-77. · Zbl 0261.90035
[3] Benayoun, R., de Montgolfier, J., Tergny, J., and Laritchev, O. (1971), Linear Programming with Multiple Objective Functions: Step Method (STEM), Mathematical Programming 1, 366-375. · Zbl 0242.90026
[4] Benson, H. P. (1986), An Algorithm for Optimizing over the Weakly-Efficient Set, European J. of Operational Research 25, 192-199. · Zbl 0594.90082
[5] Benson, H. P. (1978), Existence of Efficient Solutions for Vector Maximization Problems, J. of Optimization Theory and Applications 26, 569-580. · Zbl 0373.90085
[6] Benson, H. P. (1982), On the Convergence of Two Branch-and-Bound Algorithms for Nonconvex Programming Problems, J. of Optimization Theory and Applications 36, 129-134. · Zbl 0453.65046
[7] Benson, H. P. (1984), Optimization over the Efficient Set, J. of Mathematical Analysis and Applications 98, 562-580. · Zbl 0534.90077
[8] Benson, H. P. and Horst, R. (forthcoming), A Branch and Bound-Outer Approximation Algorithm for Concave Minimization over a Convex Set, Computers and Mathematics with Applications. · Zbl 0722.90055
[9] Blankenship, J. W. and Falk, J. E. (1976), Infinitely Constrained Optimization Problems, J. of Optimization Theory and Applications 19, 261-281. · Zbl 0307.90071
[10] Dessouky, M. I., Ghiassi, M., and Davis, W. J. (1986), Estimates of the Minimum Nondominated Criterion Values in Multiple-Criteria Decision-Making, Engineering Costs and Production Economics 10, 95-104.
[11] Evans, G. W. (1984), An Overview of Techniques for Solving Multiobjective Mathematical Programs, Management Science 30, 1268-1282. · Zbl 0551.90090
[12] Falk, J. E. and Soland, R. M. (1969), An Algorithm for Separable Nonconvex Programming Problems, Management Science 15, 550-569. · Zbl 0172.43802
[13] Ghiassi, M., DeVor, R.E., Dessouky, M. I. and Kijowski, B. A. (1984), An Application of Multiple Criteria Decision Making Principles for Planning Machining Operations, IEEE Transactions 16, 106-114.
[14] Hansen, P. (ed.) (1983), Essays and Surveys on Multiple Criteria Decision Making, Springer-Verlag, Berlin. · Zbl 0552.00016
[15] Hemming, T. (1978), Multiobjective Decision Making Under Certainty, Economic Research Institute of the Stockholm School of Economics, Stockholm.
[16] Horst, R. (1976), An Algorithm for Nonconvex Programming Problems, Mathematical Programming 10, 312-321. · Zbl 0337.90062
[17] Horst, R. (1988), Deterministic Global Optimization with Partition Sets Whose Feasibility is Not Known. Application to Concave Minimization, Reverse Convex Constraints, D.C.-Programming and Lipschitzian Optimization, J. of Optimization Theory and Applications 58, 11-37. · Zbl 0621.90064
[18] Horst, R. (1990), Deterministic Global Optimization: Recent Advances and New Fields of Application, Naval Research Logistics (37, 433-471. · Zbl 0709.90093
[19] Horst, R. (1986), A General Class of Branch and Bound Methods in Global Optimization with Some New Approaches for Convave Minimization, J. of Optimization Theory and Applications 51, 271-291. · Zbl 0581.90073
[20] Horst, R., Thoai, N. V. and Benson, H. P. (forthcoming), Concave Minimization via Conical Partitions and Polyhedral Outer Approximation, Mathematical Programming. · Zbl 0734.90092
[21] Horst, R. and Tuy, H. (1990), Global Optimization: Deterministic Approaches, Springer-Verlag, Berlin. · Zbl 0704.90057
[22] Isermann, H. and Steuer, R. E. (1987), Computational Experience Concerning Payoff Tables and Minimum Criterion Values over the Efficient Set, European J. of Operational Research 33, 91-97. · Zbl 0632.90074
[23] Kok, M. and Lootsma, F. A. (1985), Pairwise-Comparison Methods in Multiple Objective Programming, with Applications in a Long-Term Energy-Planning Model, European J. of Operational Research 22, 44-55. · Zbl 0578.90040
[24] McCormick, G. P. (1976), Computability of Global Solutions to Factorable Nonconvex Programs: Part I-Convex Underestimating Problems, Mathematical Programming 10, 147-175. · Zbl 0349.90100
[25] Pardalos, P. M. and Rosen, J. B. (1982), Constrained Global Optimization: Algorithms and Applications, Springer-Verlag, Berlin. · Zbl 0638.90064
[26] Pardalos, P. M. and Rosen, J. B. (1986), Methods for Global Concave Minimization: A Bibliographic Survey, SLAM Review 28, 367-379. · Zbl 0602.90105
[27] Philip, J. (1972), Algorithms for the Vector Maximization Problem, Mathematical Programming 2, 207-229. · Zbl 0288.90052
[28] Reeves, G. R. and Reid, R. C. (1988), Minimum Values over the Efficient Set in Multiple Objective Decision Making, European J. of Operational Research 36, 334-338.
[29] Rosenthal, R. E. (1985), Principles of Multiobjective Optimization, Decision Sciences 16, 133-152.
[30] Steuer, R. E. (1986), Multiple Criteria Optimization: Theory, Computation, and Application, Wiley, New York. · Zbl 0663.90085
[31] Thoai, N. V. and Tuy, H. (1980), Convergent Algorithms for Minimizing a Concave Function, Mathematics of Operations Research 5, 556-566. · Zbl 0472.90054
[32] Weistroffer, H. R. (1985), Careful Usage of Pessimistic Values is Needed in Multiple Objectives Optimization, Operations Research Letters 4, 23-25. · Zbl 0569.90087
[33] Yu, P. L. (1985), Multiple-Criteria Decision Making, Plenum, New York. · Zbl 0643.90045
[34] Zeleny, M. (1982), Multiple Criteria Decision Making, McGraw-Hill, New York · Zbl 0588.90019
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.