Article ID: | iaor20127298 |
Volume: | 6 |
Issue: | 8 |
Start Page Number: | 1753 |
End Page Number: | 1771 |
Publication Date: | Dec 2012 |
Journal: | Optimization Letters |
Authors: | Haouari M, Leggieri V, Triki C |
Keywords: | branch-and-cut, Steiner problem, trees |
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.