Solving the Quality of Service Multicast Tree Problem
https://doi.org/10.15514/ISPRAS-2021-33(2)-10
Abstract
This article presents a flow-based mixed integer programming formulation for the Quality of Service Multicast Tree problem. This is a relevant problem related to nowadays telecommunication networksto distribute multimedia over cloud-based Internet systems. To the best of our knowledge, no previous mixed integer programming formulation was proposed for Quality of Service Multicast Tree Problem. Experimental evaluation is performed over a set of realistic problem instances from SteinLib, to prove that standard exact solvers can find solutions to real-world size instances. Exact method is applied for benchmarking the proposed formulations, finding optimal solutions and low feasible-to-optimal gaps in reasonable execution times.
About the Authors
Claudio Enrique RISSO-MONTALDO
Universidad de la Republica Uruguay
Uruguay
Uruguay
Ph.D., Researcher
Franco Rafael ROBLEDO-AMOZA
Universidad de la Republica Uruguay
Uruguay
Uruguay
Ph.D., Full Professor
Sergio Enrique NESMACHNOW-CÁNOVAS
Universidad de la Republica Uruguay
Uruguay
Uruguay
Ph.D. in Computer Sciences, Full Professor and Researcher
References
1. Michel Goemans and Young-Soo Myung. A catalog of Steiner tree formulations. Networks, vol. 23, no.1, 1993, pp. 19-28.
2. Mathias Hauptmann and Marek Karpinski. A Compendium on Steiner Tree Problems. Technical report. Department of Computer Science and Hausdorff Center for Mathematics, University of Bonn, 2014.
3. Marek Karpinski, Ion Mandoiu, Alexander Olshevsky, and Alexander Zelikovsky. Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem. Algorithmica, vol. 42, no. 2, 2005, pp. 109-120.
4. Richard Karp. Reducibility among Combinatorial Problems. In Complexity of Computer Computations. The IBM Research Symposia Series. Springer, 1972, pp. 85-103.
5. Lester Ford and Delbert Fulkerson. Flows in Networks. Princeton University Press, 2010. 212 p.
6. Narendra Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, vol. 4, no. 4, 1984, pp. 373-395.
7. Thorsten Koch, Alexander Martin, and Stefan Voß. SteinLib: An Updated Library on Steiner Tree Problems in Graphs. Combinatorial Optimization, vol. 11, 2001, pp. 285-325.
8. Claudio Risso, Sergio Nesmachnow, and Franco Robledo. Mixed Integer Programming Formulations for Steiner Tree and Quality of Service Multicast Tree problems. Programming and Computer Software, vol. 46, no. 8, 2020, pp. 661–678.
Review
For citations:
RISSO-MONTALDO C., ROBLEDO-AMOZA F., NESMACHNOW-CÁNOVAS S. Solving the Quality of Service Multicast Tree Problem. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2021;33(2):163-172. (In Russ.) https://doi.org/10.15514/ISPRAS-2021-33(2)-10
Email this article 