An Integer Programming Approach to the Bandwidth Packing Problem

Kyungchul Park, Seokhoon Kang and Sungsoo Park
Additional contact information
Kyungchul Park: Department of Industrial Engineering, Korea Advanced Institute of Science and Technology, Taejon 305-701, Korea
Seokhoon Kang: Department of Industrial Engineering, Korea Advanced Institute of Science and Technology, Taejon 305-701, Korea
Sungsoo Park: Telecom Business Department, Ssangyong Computer Systems Co., Seoul 105-705, Korea

Management Science, 1996, vol. 42, issue 9, 1277-1291

Abstract: 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.

Keywords: bandwidth packing; zero-one programming; polyhedral cuts; branch-and-cut (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (21)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.42.9.1277 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:42:y:1996:i:9:p:1277-1291

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().