Bi-Objective Minimum Spanning Tree Problem: a comparison between a distributed and a parallel approach

Multi-objective combinatorial programs are characterized by the simultaneous optimization of multiple objectives over a discrete feasible set. They are often NP-hard and the generation of their complete Pareto frontier is time consuming. This work presents a comparison between a distributed [1] and a parallel approach with respect to their sequential counterpart of a two-phase algorithm [3] for the bi-objective minimum spanning tree (BMST) problem [2]. They are designed to speed up the search for efficient solutions [4]. In the first phase, the extreme supported efficient solutions are computed by resorting to an algorithmic approach (Prim’s algorithm embedded in a parametric search implemented according to Aneja and Nair algorithm [5]). In the second phase, the non-extreme supported and non-supported efficient solutions are determined leveraging the information provided by the ones generated in the first phase. In the latter, both distributed and parallel approaches are adopted for the generation of all spanning trees of a connected graph. These are determined via a recursive procedure based on increasing evaluation of reduced costs of associated weighted linear programs. The strengths and potential bottlenecks of these approaches, which emerged during the computational experiments, are discussed. [1] Amorosi, L., Cairo, M., Dell’Olmo, P., Di Rocco, L., & Ferraro Petrillo, U., “Two-Phase Distributed Algorithm for Solving the Bi-Objective Minimum Spanning Tree Problem: A Preliminary Study” in Lecture Notes in Computer Science, vol. 15580, pp. 261–274, 2025. [2] Amorosi, L., & Puerto, J., “Two-phase strategies for the bi-objective minimum spanning tree problem”, International Transactions in Operational Research, vol. 29, no. 6, pp. 3435–3463, 2022. [3] Ulungu, E. L., & Teghem, J., “The two phases method: An efficient procedure to solve bi-objective combinatorial optimization problems”, Foundations of computing and decision sciences, vol. 20, no. 2, pp. 149–165, 1995. [4] Chaabane, K., Bouroubi, S., & Djellouli, Y., “Parallel implementation of an exact two-phase method for the bi-objective knapsack problem”, RAIRO - Operations Research, vol. 58, pp. 3347–3367, 2024. [5] Aneja, Y. P., & Nair, K. P. K., “Bicriteria Transportation Problem”, Management Science, vol. 25, no. 1, pp. 73–78, 1979.