Park, Kyungchul; Kang, Seokhoon; Park, Sungsoo An integer programming approach to the bandwidth packing problem. (English) Zbl 0880.90043 Manage. Sci. 42, No. 9, 1277-1291 (1996). Summary: We consider the bandwidth packing problem arising from telecommunication networks. The problem is to determine the set of calls and an assignment of them to the paths in an arc-capacitated network to maximize profit. We propose an algorithm to solve the integer programming formulation of the problem. An efficient column generation technique to solve the linear programming relaxation is proposed, and a modified cover inequality is used to strengthen the IP formulation. The algorithm incorporates the column generation technique and the strong cutting plane approach into a branch-and-bound scheme. We test the proposed algorithm on some random problems. The results show that the algorithm can be used to solve the problems within reasonably small time limits. Cited in 17 Documents MSC: 90B18 Communication networks in operations research 90C10 Integer programming Keywords:polyhedral cuts; branch-and-cut; bandwidth packing; arc-capacitated network; branch-and-bound PDFBibTeX XMLCite \textit{K. Park} et al., Manage. Sci. 42, No. 9, 1277--1291 (1996; Zbl 0880.90043) Full Text: DOI