A branch and cut algorithm for a Steiner tree-star problem

A branch and cut algorithm for a Steiner tree-star problem

0.00 Avg rating0 Votes
Article ID: iaor19982933
Country: United States
Volume: 8
Issue: 3
Start Page Number: 194
End Page Number: 201
Publication Date: Jun 1996
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: networks
Abstract:

This paper deals with a Steiner tree-star problem that is a special case of the degree constrained node-weighted Steiner tree problem. This problem arises in the context of designing telecommunications networks for digital data service, provided by regional telephone companies. In this paper, we develop an effective branch and cut procedure coupled with a suitable separation procedure that identifies violated facets for fractional solutions to the relaxed formulation. Computational results indicate that large problem instances with up to 200 nodes can be solved within acceptable time bounds.

Reviews

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