The bi-objective minimum spanning tree problem: a parallel approach

Multi-objective combinatorial programs, optimization problems characterized by the simultaneous optimization of multiple objectives over a discrete feasible set, are often NP-hard and the generation of their complete Pareto frontier is time consuming. This talk presents a preliminary work on a parallel two-phase algorithm for the bi-objective minimum spanning tree (BMST) problem designed to speed up the search for efficient solutions. In the first phase, the extreme supported efficient solutions are computed by resorting to an algorithmic approach (Prim embedded in a dichotomic search); in the second phase, the non-extreme supported and non-supported efficient solutions are determined. In this latter phase, a parallel approach for the generation of all spanning trees of a connected graph through edge interchanges based on increasing evaluation of reduced costs of associated weighted linear programs is adopted. The results of preliminary computational experiments will be presented.