Metaheuristics for the Network Steiner Tree Problem

kapitola v knize

en

The network Steiner tree problem (or Steiner tree problem in graphs) finds a shortest tree spanning a given vertex subset within a network. For exact solutions, a mixed integer programming model is proposed and checked in GAMS optimization package. However, the studied problem is NP-complete and therefore, for large scaled instances, the optimal solution cannot be found in a reasonable amount of time. In this case it is usually solved by approximation or deterministic heuristic methods. This paper proposes an approach that is based on simple approximations in a hybrid combination with stochastic heuristic methods (genetic algorithms and simulated annealing) applied to a binary string representation of Steiner vertex candidates. These methods are tested on standard benchmarks from OR-Library and suitable parameter settings are recommended to achieve good solutions. It was shown that by this approach, we can achieve near-optimal results for instances of up to 100 vertices, 200 edges and 50 terminals in no more than a few minutes. This is very competitive with the best results known from literature. In a comparison with complex specialized approximation algorithms, our approach is compatible with the general framework of genetic algorithms and simulated annealing. It has a modular structure and by setting a few parameters it can be easily controlled to provide good solutions

The network Steiner tree problem (or Steiner tree problem in graphs) finds a shortest tree spanning a given vertex subset within a network. For exact solutions, a mixed integer programming model is proposed and checked in GAMS optimization package. However, the studied problem is NP-complete and therefore, for large scaled instances, the optimal solution cannot be found in a reasonable amount of time. In this case it is usually solved by approximation or deterministic heuristic methods. This paper proposes an approach that is based on simple approximations in a hybrid combination with stochastic heuristic methods (genetic algorithms and simulated annealing) applied to a binary string representation of Steiner vertex candidates. These methods are tested on standard benchmarks from OR-Library and suitable parameter settings are recommended to achieve good solutions. It was shown that by this approach, we can achieve near-optimal results for instances of up to 100 vertices, 200 edges and 50 terminals in no more than a few minutes. This is very competitive with the best results known from literature. In a comparison with complex specialized approximation algorithms, our approach is compatible with the general framework of genetic algorithms and simulated annealing. It has a modular structure and by setting a few parameters it can be easily controlled to provide good solutions

Minimum spanning tree, Steiner tree problem, metaheuristic, genetic algorithm, simulated annealing

2002

10.10.2002

DAAAM International, Wien

Wien (Austria)

3-901509-30-5

Katalinic, B. (ed.): DAAAM International Scientific Book 2002

14