Bandwidth packing with queuing delay costs: Bounding and heuristic solution procedures

In this paper we propose a new formulation for the bandwidth packing problem (BWP) in telecommunications networks. This problem is one of selecting calls, from a list of requests, to be routed in the telecommunications network. We consider both revenue losses and costs associated with communications delay as parts of the objective. An efficient Lagrangean relaxation based heuristic procedure for finding bounds and problem solutions is demonstrated. Computational results from a large array of instances are reported. We demonstrate that the procedure is efficient in finding good solutions while expending a modest amount of computational effort.