EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2979. Solving the Rainbow Steiner Tree Problem using Kernel Search

Invited abstract in session MA-26: Combinatorial optimization topics in transportation, stream Combinatorial Optimization.

Monday, 8:30-10:00
Room: 012 (building: 208)

Authors (first author is the speaker)

1. Lorenzo Tomasetti
Department of Information Engineering, University of Brescia
2. Francesco Carrabs
Department of Mathematics, University of Salerno
3. Renata Mansini
Department of Information Engineering, University of Brescia
4. Lorenzo Moreschini
Department of Information Engineering, University of Brescia

Abstract

Given an undirected edge-colored graph with non-negative edge length, the aim is to find a minimum Steiner Tree that uses at most one edge for each color.
The problem, called Rainbow Steiner Tree Problem (RSTP), is known to be NP-hard and can be used to model different real-world applications such as in wireless connectivity.
Given the complexity of the underlying problem, we develop a simple variant of the Kernel Search algorithm based on the multicommodity flow formulation with rainbow constraints.
Comprehensive work has been done on the Kernel search framework to enhance its effectiveness over the discussed problem. We test our approach on benchmark instances and compare its performance with both state-of-the-art algorithms and MIP solvers. Preliminary results are very promising.

Keywords

Status: accepted

Back to the list of papers