Abstract
The problem (P) of optimizing a linear functiond T x over the efficient set for a multiple-objective linear program (M) is difficult because the efficient set is typically nonconvex. Given the objective function directiond and the set of domination directionsD, ifd Tπ≧0 for all nonzero π∈D, then a technique for finding an optimal solution of (P) is presented in Section 2. Otherwise, given a current efficient point\(\hat x\), if there is no adjacent efficient edge yielding an increase ind T x, then a cutting plane\(d^T x = d^T \hat x\) is used to obtain a multiple-objective linear program (\(\bar M\)) with a reduced feasible set and an efficient set\(\bar E\). To find a better efficient point, we solve the problem (Ii) of maximizingc T i x over the reduced feasible set in (\(\bar M\)) sequentially fori. If there is a\(x^i \in \bar E\) that is an optimal solution of (Ii) for somei and\(d^T x^i > d^T \hat x\), then we can choosex i as a current efficient point. Pivoting on the reduced feasible set allows us to find a better efficient point or to show that the current efficient point\(\hat x\) is optimal for (P). Two algorithms for solving (P) in a finite sequence of pivots are presented along with a numerical example.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Philip, J.,Algorithms for the Vector Maximization Problem, Mathematical Programming, Vol. 2, pp. 207–229, 1972.
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.
Benson, H. P.,A Bisection-Extreme Point Search Algorithm for Optimizing over the Efficient Set in the Linear Dependence Case, Journal of Global Optimization, Vol. 3, pp. 95–111, 1993.
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.
Benson, H. P.,A Finite Nonadjacent Extreme-Point Search Algorithm for Optimization over the Efficient Set, Journal of Optimization Theory and Applications, Vol. 73, pp. 47–64, 1992.
Benson, H. P.,Optimization over the Efficient Set, Journal of Mathematical Analysis and Applications, Vol. 98, pp. 562–580, 1984.
Benson, H. P., andSayin, S.,A Face Search Heuristic Algorithm for Optimizing over the Efficient Set, Naval Research Logistics, Vol. 40, pp. 103–116, 1993.
Dessouky, M. I., Ghiassi, M., andDavis, W. J.,Estimates of the Minimum Nondominated Criterion Values in Multiple Criterion Values in Multiple-Criteria Decision Making, Engineering Costs and Production Economics, Vol. 10, pp. 95–104, 1986.
Weistroffer, H. R.,Careful Usage of Pessimistic Values Is Needed in Multiple-Objective Optimization, Operation Research Letters, Vol. 4, pp. 23–25, 1985.
Steuer, R. E.,Multiple-Criteria Optimization: Theory, Computation, and Application, Krieger Publishing Company, Malabar, Florida, pp. 147–159, 1989.
Benson, H. P.,Finding an Initial Efficient Extreme Point for a Multiple-Objective Program, Journal of the Operational Research Society, Vol. 32, pp. 495–498, 1981.
Ecker, J. G., andKouada, I. A.,Finding Efficient Points for Multiple-Objective Linear Programs, Mathematical Programming, Vol. 8, pp. 375–377, 1975.
Ecker, J. G., andHegner, N. S.,On Computing an Initial Efficient Extreme Point, Operation Research, Vol. 26, pp. 1005–1007, 1978.
Ecker, J. G., andHegner, N. S.,Generating the Efficient Set for Multiple-Objective Linear Programs, Transactions of the 24th Conference of Army Mathematicians, ARO Report 79-1, pp. 439–449, 1979.
Ecker, J. G., Hegner, N. S., andKouada, I. A.,Generating All Maximal Efficient Faces for Multiple-Objective Linear Programs, Journal of Optimization Theory and Applications, Vol. 30, pp. 353–381, 1980.
Ecker, J. G., andKouada, I. A.,Finding All Efficient Extreme Points for Multiple-Objective Linear Programs, Mathematical Programming, Vol. 14, pp. 249–261, 1978.
Benson, H. P.,Complete Efficiency and the Initialization of Algorithms for Multiple-Objective Programming, Operation Research Letters, Vol. 10, pp. 481–487, 1991.
Ecker, J. G., andKupferschmid, M.,Introduction to Operations Research, John Wiley and Sons, New York, New York, 1988.
Benson, H. P.,Existence of Efficient Solutions for Vector Maximization Problems, Journal of Optimization Theory and Applications, Vol. 26, pp. 569–580, 1978.
Benson, H. P.,Efficiency and Proper Efficiency in Vector Maximization with Respect to Cones, Journal of Mathematical Analysis and Applications, Vol. 93, pp. 273–289, 1983.
Evan, J. P., andSteuer, R. E.,A Revised Simplex Method for Linear Multiple-Objective Programs, Mathematical Programming, Vol. 15, pp. 54–72, 1973.
Isermann, H.,Proper Efficiency and the Linear Vector Maximization Problem, Operation Research, Vol. 22, pp. 189–191, 1974.
Yu, P. L., andZeleny, M.,The Set of All Nondominated Solutions in Linear Cases and a Multicriteria Simplex Method, Journal of Mathematical Analysis and Applications, Vol. 49, pp. 430–468, 1975.
Author information
Authors and Affiliations
Additional information
Communicated by P. L. Yu
The authors would like to thank an anonymous referee, H. P. Benson, and P. L. Yu for numerous helpful comments on this paper.
Rights and permissions
About this article
Cite this article
Ecker, J.G., Song, J.H. Optimizing a linear function over an efficient set. J Optim Theory Appl 83, 541–563 (1994). https://doi.org/10.1007/BF02207641
Issue Date:
DOI: https://doi.org/10.1007/BF02207641