AbstractThis 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. © 2002 Wiley Periodicals, Inc.