A min-max regret approach for the Steiner Tree Problem with Interval Costs

Let G=(V,E) be a connected graph, where V and E represent, respectively, the node-set and the edge-set. Besides, let Q \subseteq V be a set of terminal nodes, and r \in Q be the root node of the graph. Given a weight c_{ij} \in \mathbb{N} associated to each edge (i,j) \in E, the Steiner Tree Problem...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-01
Main Authors: Carvalho, Iago A, Coco, Amadeu A, Noronha, Thiago F, Duhamel, Christophe
Format: Article
Language:English
Subjects:
Algorithms
Graph theory
Graphs
Minimum weight
Nodes
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G=(V,E) be a connected graph, where V and E represent, respectively, the node-set and the edge-set. Besides, let Q \subseteq V be a set of terminal nodes, and r \in Q be the root node of the graph. Given a weight c_{ij} \in \mathbb{N} associated to each edge (i,j) \in E, the Steiner Tree Problem in graphs (STP) consists in finding a minimum-weight subgraph of G that spans all nodes in Q. In this paper, we consider the Min-max Regret Steiner Tree Problem with Interval Costs (MMR-STP), a robust variant of STP. In this variant, the weight of the edges are not known in advance, but are assumed to vary in the interval [l_{ij}, u_{ij}]. We develop an ILP formulation, an exact algorithm, and three heuristics for this problem. Computational experiments, performed on generalizations of the classical STP instances, evaluate the efficiency and the limits of the proposed methods.
ISSN:2331-8422