𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Tabu search for the Steiner problem in graphs

✍ Scribed by Celso C. Ribeiro; Maurício C. De Souza

Publisher
John Wiley and Sons
Year
2000
Tongue
English
Weight
143 KB
Volume
36
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Given an undirected graph with weights associated with its edges, the Steiner tree problem consists of finding a minimum-weighted subgraph spanning a given subset of nodes (terminals) of the original graph. In this paper, we describe a tabu search algorithm for the Steiner problem in graphs, based on a neighborhood defined by insertions and eliminations of Steiner nodes. Move estimations, elimination tests, and neighborhoodreduction techniques are used to speed up the local search, leading to a very fast algorithm with very good results in terms of solution quality. Computational experiments on benchmark problems are reported, comparing the behavior of the proposed tabu search algorithm with that of other heuristics from the literature. Tabu search clearly outperforms other heuristics in terms of computation times, obtaining better or comparable solutions.

📜 SIMILAR VOLUMES

A tabu search heuristic for the Steiner
A tabu search heuristic for the Steiner Tree Problem
✍ Gendreau, Michel; Larochelle, Jean-Francois; Sans�, Brunilde 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 342 KB 👁 1 views

The Steiner Tree Problem (STP) in graphs is a well-known NP-hard problem. It has regained attention due to the introduction of new telecommunication technologies, such as ATM, since it appears as the inherent mathematical structure behind multicast communications. In this paper, we present a tabu se

A branch and cut algorithm for the Stein
A branch and cut algorithm for the Steiner problem in graphs
✍ Lucena, A.; Beasley, J. E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB 👁 2 views

In this paper, we consider the Steiner problem in graphs, which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph with nonnegative edge costs. We use the formulation of this problem as a shortest spanning tree (SST) problem with additional constraint

Solving Steiner tree problems in graphs
Solving Steiner tree problems in graphs to optimality
✍ Koch, T.; Martin, A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 261 KB 👁 1 views

In this paper, we present the implementation of a branch-and-cut algorithm for solving Steiner tree problems in graphs. Our algorithm is based on an integer programming formulation for directed graphs and comprises preprocessing, separation algorithms, and primal heuristics. We are able to solve nea

A tabu search algorithm for the Capacita
A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem
✍ Sharaiha, Yazid M.; Gendreau, Michel; Laporte, Gilbert; Osman, Ibrahim H. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 1 views

The Capacitated Shortest Spanning Tree Problem consists of determining a shortest spanning tree in a vertex weighted graph such that the weight of every subtree linked to the root by an edge does not exceed a prescribed capacity. We propose a tabu search heuristic for this problem, as well as dynami

A new tabu search procedure for an audit
A new tabu search procedure for an audit-scheduling problem
✍ Peter Brucker; Doris Schumacher 📂 Article 📅 1999 🏛 Springer US 🌐 English ⚖ 141 KB

We consider the following version of the auditing problem. A set of jobs must be processed by auditors A , . . . , A K . Each job consists of several tasks and there may be precedence constraints between these tasks. There is a due date associated with each job. Each auditor is available during disj