Random problem generation and the computation of efficient extreme points in multiple objective linear programming
Tóm tắt
This paper looks at the task of computing efficient extreme points in multiple objective linear programming. Vector maximization software is reviewed and the ADBASE solver for computing all efficient extreme points of a multiple objective linear program is described. To create MOLP test problems, models for random problem generation are discussed. In the computational part of the paper, the numbers of efficient extreme points possessed by MOLPs (including multiple objective transportation problems) of different sizes are reported. In addition, the way the utility values of the efficient extreme points might be distributed over the efficient set for different types of utility functions is investigated. Not surprisingly, results show that it should be easier to find good near-optimal solutions with linear utility functions than with, for instance, Tchebycheff types of utility functions.
Tài liệu tham khảo
Andrei, N. and Barbulescu, M. (1993). “HERCULES: An Advanced System for Computer-Assisted Modeling and Optimization,” Technical Report, University of Duisburg, Duisburg, Germany.
Arbel, A. (1993).Exploring Interior Point Linear Programming: Algorithms and Software, MIT Press, Cambridge, Massachusetts.
Armand, P. and Malivert, C. (1991). “Determination of the Efficient Set in Multiobjective Linear Programming,”Journal of Optimization Theory and Applications, 70(3), 467–490.
Benson, H.P. (1981). “Finding an Initial Efficient Extreme Point for a Linear Multiple Objective Program,”Joural of the Operational Research Society, 32(6), 495–498.
Bradley, S.P., Hax, A.C., and Magnanti, T.L. (1976).Applied Mathematical Programming, Addison-Wesley, Reading, Massachusetts.
Charnes, A. and Cooper, W.W. (1961).Management Models and Industrial Applications of Linear Programming, Vols. I and II, Wiley, New York.
Chernikova, N.V. (1965). “Algorithm for Finding a General Formula for the Nonnegative Solutions of a System of Linear Inequalities,”U.S.S.R. Computational Mathematics and Mathematical Physics, 5(2), 228–233.
Dantzig, G.B. (1963).Linear Programming and Extensions, Princeton University Press, Princeton, New Jersey.
Dantzig, G.B. (1982). “Reminiscences about the Origins of Linear Programming,”Operations Research Letters, 1(2), 43–48.
Ecker, J.G., Hegner, N.S., and Kouada, I.A. (1980). “Generating All Maximal Efficient Faces for Multiple Objective Linear Programs,”Journal of Optimization Theory and Applications, 30(3), 353–381.
Evans, J.P. and Steuer, R.E. (1972a). “A Revised Simplex Method for Multiple Objective Programs,”Mathematical Programming, 5(1), 54–72.
Evans, J.P. and Steuer, R.E. (1973b). “Generating Efficient Extreme Points in Linear Multiple Objective Programming: Two Algorithms and Computing Experience.” In Cochrane, J.L. and M. Zeleny (eds.),Multiple Criteria Decision Making, University of South Carolina Press, Columbia, South Carolina, 349–365.
Fotso, L. (1981). “Multiple Objective Programming,” Ph.D. Dissertation, Operations Research and Statistics Interdisciplinary Program, Rensselaer Polytechnic Institute, Troy, New York.
Gal, T. (1977). “A General Method for Determining the Set of All Efficient Solutions to a Linear Vectormaximum Problem,”European Journal of Operational Research, 1(5), 306–322.
Hillier, F.S. and Lieberman, G.J. (1990).Introduction to Mathematical Programming, McGraw-Hill, New York.
IBM Document No. GH19-1091-1 (1979). “IBM Mathematical Programming System Extended/370: Primer,” IBM Corporation, Data Processing Division, White Plains, New York.
Isermann, H. (1977). “The Enumeration of the Set of All Efficient Solutions for a Linear Multiple Objective Program,”Operational Research Quarterly, 28(3), 711–725.
Isermann, H. and Naujoks, G. (1984). “Operating Manual for the EFFACET Multiple Objective Linear Programming Package,” Fakultät für Wirtschaftswissenschaften, University of Bielefeld, Bielefeld, Germany.
Isermann, H. and Steuer, R.E. (1988). “Payoff Tables and Minimum Criterion Values Over the Nondominated Set,”European Journal of Operational Research, 33(1), 91–97.
Marston, R.E. (1981). “The Design of theXMP Linear Programming Library,”Transactions on Mathematical Software, 7(4), 481–497.
Murtagh, B.A. and Saunders, M.A. (1980). “MINOS/AUGMENTED User's Manual,” Report SOL 80-14, Department of Operations Research, Stanford University, Stanford, California.
Philip, J. (1972). “Algorithms for the Vector-Maximization Problem,”Mathematical Programming, 2(2), 207–229.
Seiford, L. and Yu, P.L. (1979). “Potential Solutions of Linear Systems: The Multi-Criteria Multiple Constraint Levels Program,”Journal of Mathematical Analysis and Applications, 69(2), 283–303.
Steuer, R.E. (1976). “Multiple Objective Linear Programming with Interval Criterion Weights,”Management Science, 23(3), 305–316.
Steuer, R.E. (1986).Multiple Criteria Optimization: Theory, Computation, and Application, Wiley, New York York.
Steuer, R.E. (1994). “Manual for the ADBASE Multiple Objective Linear Programming Package,” Faculty of Management Science, University of Georgia, Athen, Georgia.
Steuer, R.E. and Gardiner, L.R. (1991). “On the Computational Testing of Procedures for Interactive Multiple Objective Linear Programming.” In Fandel, G. and H. Gehring (eds.),Operations Research: Beiträge zur Quantitativen Wirtschaftsforschung, Springer-Verlag, Berlin, 121–131.
Strijbosch, L.W.G., van Doorne, A.G.M., and Selen, W.J. (1991). “A Simplified MOLP Algorithm: The MOLP-S Procedure,”Computers & Operations Research, 18(8), 709–716.
Yu, P.L. and Zeleny, M. (1975). “The Set of All Non-Dominated Solutions in Linear Cases and a Multicriteria Simplex Method,”Journal of Mathematical Analysis and Applications, 49(2), 430–468.
Zeleny, M. (1974). “Linear Multiobjective Programming,”Lecture Notes in Economics and Mathematical Systems, 95, Springer-Verlag, Berlin.
Zeleny, M. (1976). “Multicriteria Simplex Method: A Fortran Routine,”Lecture Notes in Economics and Mathematical Systems, 123, Springer-Verlag, Berlin, 323–345.