Article at Computational Optimization and Applications

Article “Finding multi-objective supported efficient spanning trees”, P. Correia, L. Paquete, J.R. Figueira, was accepted to Computational Optimization and Applications.

Abstract:

This article introduces a new algorithm for computing the set of supported nondominated points in the objective space and all the corresponding efficient solutions in the decision space for the multi-objective spanning tree (MOST) problem. This algorithm is based on the connectedness property of the set of efficient supported solutions and uses a decomposition of the weight set in the weighting space defined for a parametric version of the MOST problem. This decomposition is performed through a space reduction approach until an indifference region for each supported nondominated point is obtained. An adjacency relation defined in the decision space is used to compute all the supported efficient spanning trees associated to the same nondominated supported point as well as to define the indifference region of the next points. An in-depth computational analysis of this approach for different types of networks with three objectives is also presented.