Solving Steiner tree problems in graphs to optimality

Solving Steiner tree problems in graphs to optimality

0.00 Avg rating0 Votes
Article ID: iaor20022476
Country: United States
Volume: 32
Issue: 3
Start Page Number: 207
End Page Number: 232
Publication Date: Oct 1998
Journal: Networks
Authors: ,
Keywords: programming: branch and bound
Abstract:

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 nearly all problem instances discussed in the literature to optimality, including one problem that – to our knowledge – has not yet been solved. We also report on our computational experiences with some very large Steiner tree problems arising from the design of electronic circuits. All test problems are gathered in a newly introduced library called SteinLib that is accessible via the World Wide Web.

Reviews

Required fields are marked *. Your email address will not be published.