|
|||||
|
|
A branch-and-cut algorithm for the Steiner tree problem with delays |
|
| Authors: | V Leggieri M Haouari C Triki |
| Institution: | 1. Faculty of Computer Science, Free University of Bozen-Bolzano, 39100, Bolzano, Italy 2. Dipartimento di Matematica, Universit?? del Salento, 73100, Lecce, Italy 3. Combinatorial Optimization Research Group, ROI, Ecole Polytechnique de Tunisie, BP 743, 2078, La Marsa, Tunisia 4. Department of Industrial Engineering, Faculty of Engineering, Ozyegin University, Istanbul, Turkey 5. Princess Fatimah Alnijris?? Research Chair for AMT, College of Engineering, King Saud University, Riyadh, Saudi Arabia 6. Dipartimento di Matematica, Universit?? del Salento, 73100, Lecce, Italy |
| 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. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |