×

A bookkeeping strategy for multiple objective linear programs. (English) Zbl 0889.90121

Summary: This paper discusses bookkeeping strategies for solving large MOLPs on ADBASE, a popular sequential software package, and on a parallel ADBASE algorithm. Three representative list creation schemes were first analyzed and tested. The best of them, binary search with insertion sort (BSIS), was incorporated into ADBASE and the parallel ADBASE algorithm. These revised versions were compared with their standard counterparts on a series of test problems, and their computation times were compared. The results show that the new bookkeeping strategy for maintaining a list of efficient solutions significantly speeds up the process of solving MOLPs, especially on parallel computers.

MSC:

90C29 Multi-objective and goal programming
90C05 Linear programming
90C06 Large-scale problems in mathematical programming
65Y05 Parallel numerical computation

Software:

EFFACET; ADBASE
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Chankong, V.; Haimes, Y. Y., Multiobjective Decision Making — Theory and Methodology (1983), North-Holland: North-Holland New York · Zbl 0525.90085
[2] Steuer, R. E., Multiple Criteria Optimization: Theory, Computation, and Application (1986), John Wiley: John Wiley New York · Zbl 0663.90085
[3] Zeleny, M., Lecture Notes in Economics and Mathematical Systems: Linear Multiobjective Programming (1974), Springer-Verlag: Springer-Verlag New York · Zbl 0325.90033
[4] Ecker, J. G.; Kouda, I. A., Finding all efficient extreme points for linear multiple objective programs, Mathematical Programming, 14, 249-261 (1978) · Zbl 0385.90105
[5] Zeleny, M., Multicriteria Simplex Method: A Fortran Routine, (Lecture Notes in Economics and Mathematical Systems, Vol. 123 (1976), Springer-Verlag: Springer-Verlag Berlin), 323-345 · Zbl 0335.90036
[6] Fotso, L., Multiple objective programming, (Ph.D. Dissertation (1981), Operations Research and Statistics Interdisciplinary Program, Rensselaer Polytechnic Institute: Operations Research and Statistics Interdisciplinary Program, Rensselaer Polytechnic Institute Troy, NY)
[7] Isermann, H.; Naujoks, G., (Operating Manual for the EFFACET Multiple Objective Linear Programming Package (1984), Fakultaet für Wirtschaftswissenschaften, University of Bielefeld: Fakultaet für Wirtschaftswissenschaften, University of Bielefeld Bielefeld, Germany)
[8] Strijbosch, L. W.G.; van Doorne, A. G.M.; Selen, W. J., A simplified MOLP algorithm: the MOLP-S procedure, Computers and Operations Research, 18, 709-716 (1991) · Zbl 0741.90060
[9] Armand, P.; Malivert, C., Determination of the efficient set in multiobjective linear programming, Journal of Optimization Theory and Applications, 70, 467-490 (1991) · Zbl 0793.90064
[10] Steuer, R. E., (Manual for the ADBASE Multiple Objective Linear Programming Package (1995), Department of Science and Information Technology, University of Georgia: Department of Science and Information Technology, University of Georgia Athens, GA)
[11] Evtushenko, Y.; Mazourik, V.; Ratkin, V., Multicriteria optimization in the DISO system, (Kurzhanski, A.; Neumann, K.; Pallaschke, D., Optimization, Parallel Processing and Application (1988), Springer-Verlag: Springer-Verlag Berlin), 94-102 · Zbl 0648.90079
[12] Costa, J. P.; Climaco, J. N., A multiple reference point parallel approach in MCDM, (Proceedings of the Tenth International Conference on Multiple Criteria Decision Making, Taipei, Vol. 3 (1992)), 265-272
[13] Chang, C. S., Coordinated static and dynamic monitoring and optimization of power systems using a parallel architecture and pattern recognition techniques, (IEE Proceedings, C139 (1992)), 197-204
[14] Wiecek, M. M.; Zhang, H., Solving multiple objective linear programs on the Intel Paragon, (Proceedings of Mardi Gras ’94 Conference: Toward Teraflop Computing and New Grand Challenge Applications. Proceedings of Mardi Gras ’94 Conference: Toward Teraflop Computing and New Grand Challenge Applications, Baton Rouge, LA (February 10-12, 1994)), 323-329
[15] Wiecek, M. M.; Zhang, H., A parallel algorithm for multiple objective linear programs, Computational Optimization and Applications, 8 (1997) · Zbl 0880.90121
[16] Steuer, R. E., Random problem generation and the computation of efficient extreme points in multiple objective linear programming, Computational Optimization and Applications, 3, 333-347 (1994) · Zbl 0819.90088
[17] Horowitz, E.; Sahni, S.; Anderson-Freed, S., Fundamentals of Data Structures (1993), C. W. H. Freeman: C. W. H. Freeman New York · Zbl 0842.68017
[18] (Kronsjo, L.; Shumsheruddin, D., Advances in Parallel Algorithms (1992), John Wiley: John Wiley New York)
[19] Kumar, V.; Grama, A.; Gupta, A.; Karypis, G., Introduction to Parallel Computing: Design and Analysis of Algorithms (1994), Benjamin/Cummings: Benjamin/Cummings Redwood City, CA · Zbl 0861.68040
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.