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

作者：Leggieri V^*; Haouari M; Triki C

来源：Optimization Letters, 2012, 6(8): 1753-1771.

DOI：10.1007/s11590-011-0368-1

• Steiner tree problem
• Delay constraints
• Branch-and-cut method

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.

• 出版日期2012-12