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.
Similar content being viewed by others
References
Achterberg T., Koch T., Martin A.: Branching rules revisited. Oper. Res. Lett. 33(1), 42–54 (2005)
Althaus, E., Polzin, T., Daneshmand, S.V.: Improving linear programming approaches for the Steiner tree problem. In: Experimental and efficient algorithms. Lecture Notes in Computer Science, vol. 2647, pp. 1–14. Springer, Berlin (2003)
Aneja Y.P.: An integer linear programming approach to the Steiner problem in graphs. Networks 10(2), 167–178 (1980)
Applegate, D., Bixby, R., Cook W.: Finding cuts in the tsp (a preliminary report) (1995)
Ascheuer N., Fischetti M., Grötschel M.: Solving the asymmetric travelling salesman problem with time windows by branch-and-cut. Math. Program. 90(3, Ser. A), 475–506 (2001)
Ascheuer N., Fischetti M., Grötschel M.: A polyhedral study of the asymmetric traveling salesman problem with time windows. Networks 36(2), 69–79 (2000)
Costa A.M., Cordeau J.-F., Laporte G.: Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints. Eur. J. Oper. Res. 190(1), 68–78 (2008)
Costa A.M., Cordeau J.F., Laporte G.: Models and branch-and-cut algorithms for the Steiner tree problem with revenues, budget and hop constraints. Networks 53(2), 141–159 (2009)
Du, D.Z., Lu, B., Ngo, H., Pardalos, P.M.: Steiner tree problems. In: Floudas, C., Pardalos, P. (eds.) Encyclopedia of Optimization, vol. 5, pp. 227–290 (2001)
Ghaboosi N., Haghighat A.T.: Tabu search based algorithms for bandwidth-delay-constrained least-cost multicast routing. Telecommun. Syst. 34(3–4), 147–166 (2007)
Ghanwani A.: Neural and delay based heuristics for the Steiner problem in networks. Eur. J. Oper. Res. 108(2), 241–265 (1998)
Gouveia L.: Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints. Comput. Oper. Res. 22(9), 959–970 (1995)
Johnson E.L., Nemhauser G.L., Savelsbergh M.W.P.: Progress in linear programming-based algorithms for integer programming: an exposition. INFORMS J. Comput. 12, 2–23 (2000)
Koch T., Martin A.: Solving Steiner tree problems in graphs to optimality. Networks 32(3), 207–232 (1998)
Koch, T., Martin, A., Voβ, S.: SteinLib. http://elib.zib.de/steinlib
Kompella V.P., Pasquale J., Polyzos G.C.: Multicast routing for multimedia communication. IEEE/ACM Trans. Netw. 1(3), 286–292 (1993)
Kun Z., Heng W., Liu F.Y.: Distributed multicast routing for delay and delay variation-bounded Steiner tree using simulated annealing. Comput. Commun. 28(11), 1356–1370 (2005)
Leggieri, V., Haouari, M., Layeb, S., Triki, C. The Steiner tree problem with delays: a compact formulation and reduction procedures. Discret. Appl. Math. (2011, in press)
Miller C.E., Tucker A.W., Zemlin R.A.: Integer programming formulation of traveling salesman problems. J. Assoc. Comput. Mach. 7(4), 326–329 (1960)
Nemhauser G.L., Wolsey L.A.: Integer and combinatorial optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., New York (1988)
Oliveira C.A.S., Pardalos P.M.: A survey of combinatorial optimization problems in multicast routing. Comput. Oper. Res. 32(8), 1953–1981 (2005)
Oliveira C.A.S., Pardalos P.M.: Construction algorithms and approximation bounds for the streaming cache placement problem in multicast networks. Cybern. Syst. Anal. 41(6), 898–908 (2005)
Polzin T., Daneshmand S.V.: A comparison of Steiner tree relaxations. Discret. Appl. Math. J. Comb. Algorithms Inform. Comput. Sci. 112(1–3), 241–261 (2001)
Santos M., Drummond L.M.A., Uchoa E.: A distributed dual ascent algorithm for the hop-constrained Steiner tree problem. Oper. Res. Lett. 38(1), 57–62 (2010)
Sriram R., Manimaran G., Ram Murthy C.S.: Algorithms for delay-constrained low-cost multicast tree construction. Comput. Commun. 21(18), 1693–1706 (1998)
Wolsey L.A.: Integer Programming. Wiley-Interscience, New York (1998)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Leggieri, V., Haouari, M. & Triki, C. A branch-and-cut algorithm for the Steiner tree problem with delays. Optim Lett 6, 1753–1771 (2012). https://doi.org/10.1007/s11590-011-0368-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-011-0368-1