A branch‐and‐cut algorithm for the Steiner tree problem with delays

A branch‐and‐cut algorithm for the Steiner tree problem with delays

0.00 Avg rating0 Votes
Article ID: iaor20127298
Volume: 6
Issue: 8
Start Page Number: 1753
End Page Number: 1771
Publication Date: Dec 2012
Journal: Optimization Letters
Authors: , ,
Keywords: branch-and-cut, Steiner problem, trees
Abstract:

In this paper, we investigate the Steiner tree problem with delays, which is a generalized version of the Steiner tree problem applied to multicast routing. For this challenging combinatorial optimization problem, we present an enhanced directed cut‐based MIP formulation and an exact solution method based on a branch‐and‐cut approach. Our computational study reveals that the proposed approach can optimally solve hard dense instances.

Reviews

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