Computing all efficient solutions of the biobjective minimum spanning tree problem

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2006.02.023 Byline: Sarah Steiner, Tomasz Radzik Abstract: A common way of computing all efficient (Pareto optimal) solutions for a biobjective combinatorial optimisation problem is to compute first the extreme efficient solutions and then the remaining, non-extreme solutions. The second phase, the computation of non-extreme solutions, can be based on a "k-best" algorithm for the single-objective version of the problem or on the branch-and-bound method. A k-best algorithm computes the k-best solutions in order of their objective values. We compare the performance of these two approaches applied to the biobjective minimum spanning tree problem. Our extensive computational experiments indicate the overwhelming superiority of the k-best approach. We propose heuristic enhancements to this approach which further improve its performance. Author Affiliation: Department of Computer Science, King's College London, Strand, London WC2R 2LS, UK