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

V. Leggieri*, M. Haouari, C. Triki

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)1753-1771
Number of pages19
JournalOptimization Letters
Issue number8
Publication statusPublished - Nov 2012


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

ASJC Scopus subject areas

  • Control and Optimization


Dive into the research topics of 'A branch-and-cut algorithm for the Steiner tree problem with delays'. Together they form a unique fingerprint.

Cite this