An integer programming approach to the bandwidth packing problem

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 are-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.