Change search
ReferencesLink to record
Permanent link

Direct link
Dimensioning multicast-enabled communications networks
KTH, Superseded Departments, Mathematics.ORCID iD: 0000-0002-6252-7815
2002 (English)In: Networks, ISSN 0028-3045, E-ISSN 1097-0037, Vol. 39, no 4, 216-231 p.Article in journal (Refereed) Published
Abstract [en]

This paper concerns the network design problem of dimensioning capacity, available in discrete, nonuniform levels, for multicast traffic in a backbone communications network. An integer programming model, which includes embedded models for the Steiner tree problem in graphs, is proposed. A Lagrangian decomposition scheme based on variable splitting is suggested for computing lower bounds on the optimal objective function value. This decomposition gives a set of Steiner tree subproblems, which are solved using a branch-and-cut algorithm, and a set of capacity-level subproblems, which are solved as sequences of 0-1 knapsack problems. A method for finding good primal feasible solutions while solving the relaxed problem is suggested, and an overall branch-and-bound strategy on the variable split constraints is also proposed and implemented. Computational results are reported for two sets of test problems that have been generated from real problems. One set has real, nonuniform cost and capacities, while the other set has uniform costs and capacities. The results suggest that the main difficulty in the problem is the discrete, nonuniform capacity-level selection. The variable split relaxation lower bound is consistently superior to the bounds obtained from LP relaxation and a straight-forward Lagrangian relaxation for the test problems with a nonuniform cost and capacity structure.

Place, publisher, year, edition, pages
2002. Vol. 39, no 4, 216-231 p.
Keyword [en]
network optimization, telecommunications, multicast traffic, Lagrangian, decomposition, branch-and-cut, steiner tree problems
URN: urn:nbn:se:kth:diva-21679DOI: 10.1002/net.10026ISI: 000176621800005OAI: diva2:340377
QC 20100525Available from: 2010-08-10 Created: 2010-08-10Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Forsgren, Anders
By organisation
In the same journal

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 13 hits
ReferencesLink to record
Permanent link

Direct link