A bisection-extreme point search algorithm for optimizing over the efficient set in the linear dependence case. (English) Zbl 0799.90101

The problem of maximizing a linear function on the set of efficient points of a linear vector maximization problem is investigated. It is assumed that the objective function of this problem is a linear combination of the objective functions on the linear vector maximization problem. A so-called bisection-extreme point search algorithm is presented for the solution of this problem. It is proved that this method finds a solution in a finite number of iterations.
Reviewer: J.Jahn (Erlangen)


90C29 Multi-objective and goal programming
90C05 Linear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI


[1] Bazaraa, M. S., Jarvis, J. J., and Sherali, H. D. (1990),Linear Programming and Network Flows, Wiley, New York. · Zbl 0722.90042
[2] Benson, H. P. (1986), An Algorithm for Optimizing over the Weakly-Efficient Set,European J. of Operational Research 25, 192-199. · Zbl 0594.90082
[3] Benson, H. P. (1991), An All-Linear Programming Relaxation Algorithm for Optimizing over the Efficient Set,J. of Global Optimization 1, 83-104. · Zbl 0739.90056
[4] Benson, H. P. (1981), Finding an Initial Efficient Extreme Point for a Linear Multiple Objective Program,J. of the Operational Research Society 32, 495-498. · Zbl 0454.90075
[5] Benson, H. P. (1992), A Finite, Non-Adjacent Extreme Point Search Algorithm for Optimization over the Efficient Set,J. of Optimization Theory and Applications 73, 47-64. · Zbl 0794.90048
[6] Benson, H. P. (1981), Optimization over the Efficient Set, Discussion Paper No.35, Center for Econometrics and Decision Sciences, University of Florida, Gainesville, Florida.
[7] Benson, H. P. (1984), Optimization over the Efficient Set,J. of Mathematical Analysis and Applications 98, 562-580. · Zbl 0534.90077
[8] Bolintineanu, S. (1990), Minimization of a Quasi-Concave Function over an Efficient Set, Mathematics Research Paper No. 90-15, Department of Mathematics, La Trobe University, Bundoora, Victoria, Australia.
[9] Dauer, J. P. (1991), Optimization over the Efficient Set Using an Active Constraint Approach,Zeitschrift für Operations Research 35, 185-195. · Zbl 0734.90081
[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] Ecker, J. G. and Hegner, N. S. (1978), On Computing an Initial Efficient Extreme Point,J. of the Operational Research Society 29, 1005-1007. · Zbl 0385.90104
[12] Ecker, J. G. and Kouada, I. A. (1978), Finding All Efficient Extreme Points for Multiple Objective Linear Programs,Mathematical Programming 14, 249-261. · Zbl 0385.90105
[13] Evans, G. W. (1984), An Overview of Techniques for Solving Multiobjective Mathematical Programs,Management Science 30, 1268-1282. · Zbl 0551.90090
[14] Evans, J. P. and Steuer, R. E. (1973), Generating Efficient Extreme Points in Linear Multiple Objective Programming: Two Algorithms and Computing Experience, in J. L. Cochrane and M. Zeleny (eds.),Multiple Criteria Decision Making, University of South Carolina Press, Columbia, South Carolina, pp. 349-365.
[15] Forgo, F. (1988),Nonconvex Programming, Akademiai Kiado, Budapest. · Zbl 0241.90055
[16] Horst, R. and Tuy, H. (1990),Global Optimization: Deterministic Approaches, Springer-Verlag, Berlin. · Zbl 0704.90057
[17] Isermann, H. (1977), The Enumeration of the Set of All Efficient Solutions for a Linear Multiple Objective Program,Operational Research Quarterly 28, 711-725. · Zbl 0372.90086
[18] 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
[19] Martos, B. (1965), The Direct Power of Adjacent Vertex Programming Methods,Management Science 12, 241-252. · Zbl 0142.17002
[20] Murty, K. G. (1983),Linear Programming, Wiley, New York. · Zbl 0521.90071
[21] Pardalos, P. M. and Rosen, J. B. (1987),Constrained Global Optimization: Algorithms and Applications, Springer-Verlag, Berlin. · Zbl 0638.90064
[22] Pardalos, P. M. and Rosen, J. B. (1986), Methods for Global Concave Minimization: A Bibliographic Survey,SIAM Review 28, 367-379. · Zbl 0602.90105
[23] Philip, J. (1972), Algorithms for the Vector Maximization Problem,Mathematical Programming 2, 207-229. · Zbl 0288.90052
[24] 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.
[25] Rosenthal, R. E. (1985), Principles of Multiobjective Optimization,Decision Sciences 16, 133-152.
[26] Steuer, R. E. (1986),Multiple Criteria Optimization: Theory, Computation, and Application, Wiley, New York. · Zbl 0663.90085
[27] Weistroffer, H. R. (1985), Careful Usage of Pessimistic Values Is Needed in Multiple Objectives Optimization,Operations Research Letters 4, 23-25. · Zbl 0569.90087
[28] Yu, P. L. (1985),Multiple-Criteria Decision Making, Plenum, New York. · Zbl 0643.90045
[29] 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.