Two-phase strategies for the bi-objective minimum spanning tree problem

This paper presents a new two-phase algorithm for the bi-objective minimum spanning tree (BMST) problem. In the first phase, it computes the extreme supported efficient solutions resorting to both mathematical programming and algorithmic approaches, while the second phase is devoted to obtaining the remaining efficient solutions (non-extreme supported and non-supported). This latter phase is based on a new recursive procedure capable of generating all the spanning trees of a connected graph through edge interchanges based on increasing evaluation of non-zero reduced costs of associated weighted linear programs. Such a procedure exploits a common property of a wider class of problems to which the minimum spanning tree (MST) problem belongs, that is the spanning tree structure of its basic feasible solutions. Computational experiments are conducted on different families of graphs and with different types of cost. These results show that this new two-phase algorithm is correct, very easy to implement and it allows one to extract conclusions on the difficulty of finding the entire set of Pareto solutions of the BMST problem depending on the graph topology and the possible correlation of the edge costs.