A face search heuristic algorithm for optimizing over the efficient set. (English) Zbl 0780.90080

Summary: The problem of optimizing a linear function over the efficient set of a multiple objective linear program is an important but difficult problem in multiple criteria decision making. In this article we present a flexible face search heuristic algorithm for the problem. Preliminary computational experiments indicate that the algorithm gives very good estimates of the global optimum with relatively little computational effort.


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] Benson, Journal of Optimization Theory and Applications 26 pp 569– (1978)
[2] Benson, Journal of Mathematical Analysis and Applications 98 pp 562– (1984)
[3] Benson, Journal of Global Optimization 1 pp 83– (1991)
[4] Benson, Journal of Optimization Theory and Applications 73 pp 47– (1992)
[5] ”A Bisection-Extreme Point Search Algorithm for Optimizing Over the Efficient Set in the Linear Dependence Case,” Journal of Global Optimization, to be published. · Zbl 0799.90101
[6] and , ”Optimization Over the Efficient Set: Four Special Cases,” Working Paper, Department of Decision and Information Sciences, University of Florida, Gainesville, 1991.
[7] ”Minimization of a Quasi-Concave Function Over an Efficient Set,” Mathematics Research Paper No. 90–15, Department of Mathematics, La Trobe University, Melbourne, Australia, 1990.
[8] Dauer, Zeitschrift fur Operations Research 35 pp 185– (1991)
[9] Dessouky, Engineering Costs and Production Economics 10 pp 95– (1986)
[10] and , ”Generating Efficient Extreme Points in Linear Multiple Objective Programming: Two Algorithms and Computing Experience,” in and (Eds.), Multiple Criteria Decision Making, University of South Carolina Press, Columbia, 1973, pp. 349–365.
[11] and , Global Optimization: Deterministic Approaches, Springer-Verlag, Berlin, 1990. · Zbl 0704.90057
[12] International Business Machines, Optimization Subroutine Library Guide and Reference. International Business Machines, Mechanicsburg, PA, 1990.
[13] Isermann, European Journal of Operational Research 33 pp 91– (1987)
[14] Marcotte, Management Science 32 pp 61– (1986)
[15] Linear Programming, Wiley, New York, 1983.
[16] and , Constrained Global Optimization: Algorithms and Applications, Springer-Verlag, Berlin, 1987. · Zbl 0638.90064
[17] Philip, Mathematical Programming 2 pp 207– (1972)
[18] Convex Analysis, Princeton University Press, Princeton, NJ, 1970. · Zbl 0932.90001
[19] Multiple Criteria Optimization. Theory, Computation, and Application, Wiley, New York, 1986. · Zbl 0663.90085
[20] ”Operating Manual for the ADBASE Multiple Objective Linear Programming Package,” College of Business Administration, University of Georgia, Athens, 1983.
[21] ”A Five Phase Procedure for Implementing a Vector-Maximum Algorithm for Multiple Objective Linear Programming Problems,” in and (Eds.), Multiple Criteria Decision Making: Jouy-en-Josas, Springer-Verlag, New York, 1976, pp. 159–169.
[22] Weistroffer, Operations Research Letters 4 pp 23– (1985)
[23] Multiple-Criteria Decision Making, Plenum, New York, 1985.
[24] Yu, Journal of Mathematical Analysis and Applications 49 pp 430– (1975)
[25] Multiple Criteria Decision Making, McGraw-Hill, New York, 1982. · 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.