A Multiobjective Branch-and-Bound Framework: Application to the Biobjective Spanning Tree Problem

References

• Andersen K. A., Jörnsten K., Lind M. On bicriterion minimal spanning trees: An approximation. Comput. Oper. Res. (1996) 23:1171–1182Crossref, Google Scholar
• Bitran G., Rivera J. M. A combined approach to solve binary multicriteria problems. Naval Res. Logist. Quart. (1982) 29:181–201Crossref, Google Scholar
• Chandrasekaran R. Minimal ratio spanning trees. Networks (1977) 7:335–342Crossref, Google Scholar
• Corley H. W. Efficient spanning trees. J. Optim. Theory Appl. (1985) 45:481–485Crossref, Google Scholar
• Daellenbach H. G., De Kluyver C. A. Note on multiple objective dynamic programming. J. Oper. Res. Soc. (1980) 31:591–594Crossref, Google Scholar
• Ehrgott M.Multicriteria Optimization (2005) 2nd ed.(Springer-Verlag, Berlin) . [Originally published in Lecture Notes in Economics and Mathematical Systems, Vol. 491. Springer-Verlag, Berlin, 2000.]Google Scholar
• Ehrgott M., Gandibleux X. A survey and annoted bibliography of multiobjective combinatorial optimization. OR Spektrum (2000) 22:425–460Crossref, Google Scholar
• Ehrgott M., Gandibleux X. Approximative solution methods for multiobjective combinatorial optimization. J. Spanish Statist. Oper. Res. Soc. (2004) 12:1–88Google Scholar
• Ehrgott M., Gandibleux X. Bound sets for biobjective combinatorial optimization problems. Comput. Oper. Res. (2007) 34:2674–2694Crossref, Google Scholar
• Ehrgott M., Klamroth K. Connectedness of efficient solutions in multiple criteria combinatorial optimization. Eur. J. Oper. Res. (1997) 97:159–166Crossref, Google Scholar
• Emelichev V. A., Perepelitsa V. A. Multiobjective problems on the spanning trees of a graph. Soviet Math. Doklady (1988) 37:114–117Google Scholar
• Hamacher H. W., Ruhe G. On spanning tree problems with multiple objectives. Ann. Oper. Res. (1994) 52:209–230Crossref, Google Scholar
• Kiziltan G., Yucaoglu E. An algorithm for multiobjective zero-one linear programming. Management Sci. (1983) 29:1444–1453Link, Google Scholar
• Knowles J. D., Corne D. W. Benchmark problem generators and results for the multiobjective degree-constrained minimum spanning tree problem. Proc. Genetic Evolutionary Comput. Conf. (GECCO 2001) (2001a) San Francisco(Morgan Kaufmann Publishers, San Francisco) 424–431Google Scholar
• Knowles J. D., Corne D. W. A comparison of encodings and algorithms for multiobjective spanning tree problems. Proc. 2001 Congress on Evolutionary Comput. (2001b) (IEEE Press, Seoul, Korea) 544–551Crossref, Google Scholar
• Marcotte O., Soland R. M. An interactive branch-and-bound algorithm for multiple criteria optimization. Management Sci. (1986) 32:61–75Link, Google Scholar
• Martin P. D., Shmoys D. B., Cunningham W. H., McCormick S. T., Queyranne M. A new approach to computing optimal schedules for the job shop scheduling problem. Proc. Fifth Internat. IPCO Conf., Vancouver, Canada, Lecture Notes in Computer Science (1996) 1084(Springer, New York) 389–403Crossref, Google Scholar
• Mavrotas G., Diakoulaki D. A branch and bound algorithm for mixed zero-one multiple objective linear programming. Eur. J. Oper. Res. (1998) 107:530–541Crossref, Google Scholar
• Murthy I., Sarkar S. Stochastic shortest path problems with piecewise-linear concave utility functions. Management Sci. (1998) 44:125–136Link, Google Scholar
• Neumann F. Expected runtimes of a simple evolutionary algorithm for the multiobjective minimum spanning tree problem. Eur. J. Oper. Res. (2007) 181:1620–1629Crossref, Google Scholar
• Papadimitriou C. H., Yannakakis M. On the approximability of trade-offs and optimal access of Web sources. IEEE Sympos. Foundations Comput. Sci. (2000) Redondo Beach, CA(Computer Society Press, Los Alamitos, CA) 86–92Crossref, Google Scholar
• Ramos R. M., Alonso S., Sicilia J., Gonzales C. The problem of the optimal biobjective spanning tree. Eur. J. Oper. Res. (1998) 111:617–628Crossref, Google Scholar
• Serafini P., Jahn J., Krabs W. Some considerations about computational complexity for multiobjective combinatorial problems. Recent Advances and Historical Development of Vector Optimization, Lecture Notes in Economics and Mathematical Systems (1986) 294(Springer-Verlag, Berlin) 222–232Google Scholar
• Steiner S., Radzik T. Computing all efficient solutions of the biobjective minimum spanning tree problem. Comput. Oper. Res. (2008) 35:198–211Crossref, Google Scholar
• Tarjan R. E.Data Structures and Network Algorithms: CBMS-NSF Regional Conf. Series in Applied Mathematics (1983) 44(Society for Industrial and Applied Mathematics, Philadelphia) Crossref, Google Scholar
• Visée M., Teghem J., Pirlot M., Ulungu E. L. Two-phases method and branch and bound procedures to solve the biobjective knapsack problem. J. Global Optim. (1998) 12:139–155Crossref, Google Scholar
• Zhou G., Gen M. Genetic algorithm approach on the multi-criteria minimum spanning tree problem. Eur. J. Oper. Res. (1999) 114:141–152Crossref, Google Scholar