×
Benson, Harold P.

An algorithm for optimizing over the weakly-efficient set. (English) Zbl 0594.90082

Eur. J. Oper. Res. 25, 192-199 (1986).
Der Artikel betrifft Probleme der linearen Vektormaximierung mit beschränkten Polyedern als Restriktionsmengen. Es zeigt sich, daß bei vielen Problemen der Praxis eine privilegierte Lösung aus der Menge der schwach-effizienten Punkten dadurch gefunden werden kann, indem das Maximum einer bestimmten linearen Funktion über der Menge der schwach- effizienten Punkten bestimmt wird. Das entsprechende Verfahren wird hier für die Lösung solcher Optimierungsprobleme theoretisch begründet und ausführlich beschrieben; es besteht aus der Lösung von linearen Optimierungsaufgaben und aus der Lösung von Minimierungsaufgaben mit einer konkaven Zielfunktion, bei denen die Zulässigkeitsmenge durch ein System von linearen Ungleichungen beschrieben ist. Es wird weiter gezeigt, daß nach einer endlichen Anzahl von Schritten eine Optimallösung, bzw. eine geeignete Approximation der Optimallösung des vorgegebenen Problems gefunden werden kann. Am Schluß der Arbeit wird bemerkt, daß aufgrund der Berechnungserfahrungen das entsprechende Verfahren für relativ kleine Probleme geeignet ist.
Reviewer: L.Grygarova

Cited in 24 Documents

MSC:

90C31 Sensitivity, stability, parametric optimization
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C05 Linear programming

Keywords:

multiple objective linear programming; efficiency; nonconvex; programming; weakly efficient points; numerical method; linear; vector optimization; bounded polyhedral constraints
PDF BibTeX XML Cite
\textit{H. P. Benson}, Eur. J. Oper. Res. 25, 192--199 (1986; Zbl 0594.90082)
Full Text: DOI

References:

[1] Benson, H. P., A finite algorithm for concave minimization over a polyhedron, Naval Research Logistics Quarterly, 32, 165-177 (1985) · Zbl 0581.90080
[2] Benson, H. P., Optimization over the efficient set, Journal Mathematical Analysis and Applications, 98, 562-580 (1984) · Zbl 0534.90077
[3] Cabot, A. V., Variations on a cutting plane method for solving concave minimization problems with linear constraints, Naval Research Logistics Quarterly, 21, 265-274 (1974) · Zbl 0348.90131
[4] Dessouky, M. I.; Ghiassi, M.; Davis, W. J., Determining the worst value of an objective function within the nondominated solutions in multiple objective linear programming (1979), Department of Mechanical and Industrial Engineering, University of Illinois
[5] Ecker, J. G.; Hegner, N. S.; Kouada, I. A., Generating all maximal efficient faces for multiple objective linear programs, Journal of Optimization Theory and Applications, 30, 353-381 (1980) · Zbl 0393.90087
[6] Ecker, J. G.; Kouada, I. A., Finding all efficient extreme points for multiple objective linear programs, Mathematical Programming, 14, 249-261 (1978) · Zbl 0385.90105
[7] Evans, J. P.; Steuer, R. E., Generating efficient extreme points in linear multiple objective programming: Two algorithms and computing experience, (Cochrane, J. L.; Zeleny, M., Multiple Criteria Decision Making (1973), University of South Carolina Press: University of South Carolina Press Columbia, SC), 349-365
[8] Falk, J. E.; Hoffman, K. R., A successive underestimation method for concave minimization problems, Mathematics Operations Research, 1, 251-259 (1976) · Zbl 0362.90082
[9] Gal, T., A general method for determining the set of all efficient solutions to a linear vector-maximum problem, European Journal of Operational Research, 1, 307-322 (1977) · Zbl 0374.90044
[10] Isermann, H., The enumeration of the set of all efficient solutions for a linear multiple objective program, Operational Research Quarterly, 28, 11-725 (1977) · Zbl 0372.90086
[11] Majthay, A.; Whinston, A., Quasiconcave minimization subject to linear constraints, Discrete Mathematics, 9, 35-59 (1974) · Zbl 0301.90037
[12] Marcotte, O.; Soland, R. M., An interactive branch-and-bound algorithm for multiple criteria optimization, (Serial T-442 (1981), Institute for Management Science and Engineering, The George Washington University) · Zbl 0592.90057
[13] Philip, J., Algorithms for the vector maximization problem, Mathematical Programming, 2, 207-229 (1972) · Zbl 0288.90052
[14] Rockafellar, R. T., Convex Analysis (1970), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0229.90020
[15] Steuer, R. E., A five phase procedure for implementing a vector-maximum algorithm for multiple objective linear programming problems, (Thiriez, H.; Zionts, S., Multiple Criteria Decision Making: Jouy-en-Josas. Multiple Criteria Decision Making: Jouy-en-Josas, France (1976), Springer-Verlag: Springer-Verlag New York), 159-169
[16] Steuer, R. E., Multiple objective linear programming with interval criterion weights, Management Science, 23, 305-316 (1976) · Zbl 0437.90086
[17] Taha, H. A., Concave minimization over a convex polyhedron, Naval Research Logistics Quarterly, 20, 533-548 (1973) · Zbl 0286.90052
[18] Tamura, K.; Miura, S., On linear vector maximization problems, Journal of the Operations Research Society of Japan, 20, 139-149 (1977) · Zbl 0372.90087
[19] Tuy, H., Concave programming under linear constraints, Soviet Mathematics, 5, 1437-1440 (1964) · Zbl 0132.40103
[20] Yu, P. L.; Zeleny, M., The set of all nondominated solutions in linear cases and a multicriteria simplex method, Journal of Mathematical Analysis and Applications, 49, 430-468 (1975) · Zbl 0313.65047
[21] Zionts, S.; Wallenius, J., An interactive programming method for solving the multiple criteria problem, Management Science, 22, 652-663 (1976) · Zbl 0318.90053
[22] Zwart, P. B., Global maximization of a convex function with linear inequality constraints, Operations Research, 22, 602-609 (1974) · Zbl 0322.90049
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.