Given an undirected and edge-colored graph with non-negative edge lengths, the aim of the Rainbow Steiner Tree Problem (RSTP) is to find a minimum Steiner Tree that uses at most one edge for each color. In this paper, the RSTP is introduced, a mathematical model is proposed to formally represent the problem and its theoretical properties are investigated. Since the RSTP belongs to the NP-class, two heuristic methods are designed: a Lagrangian relaxation approach and a multistart algorithm. Extensive computational experiments are carried out on a significant set of test problems to empirically evaluate the performance of the proposed approaches. The computational results show that the two approaches are both effective and efficient compared to the ILOG CPLEX solver.
The Rainbow Steiner Tree Problem
Ferone D.;Festa P.;Guerriero F.
2022-01-01
Abstract
Given an undirected and edge-colored graph with non-negative edge lengths, the aim of the Rainbow Steiner Tree Problem (RSTP) is to find a minimum Steiner Tree that uses at most one edge for each color. In this paper, the RSTP is introduced, a mathematical model is proposed to formally represent the problem and its theoretical properties are investigated. Since the RSTP belongs to the NP-class, two heuristic methods are designed: a Lagrangian relaxation approach and a multistart algorithm. Extensive computational experiments are carried out on a significant set of test problems to empirically evaluate the performance of the proposed approaches. The computational results show that the two approaches are both effective and efficient compared to the ILOG CPLEX solver.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
