An efficient solution approach for combinatorial bandwidth packing problem with queuing delays

Abstract

The Combinatorial bandwidth packing problem (CBPP), arising in a telecommunication network with limited bandwidth, is defined as: given a set of request, each with its potential revenue and consisting of calls with their bandwidth requirements, deciding (i) a subset of the requests to accept/reject, and (ii) a route for each call in an accepted request, so as to maximize total revenue earned. However, telecommunication networks are generally characterized by variability in the call (bits) arrival rates and service times, resulting in delays in the network. In this paper, we present a non-linear integer programming model for CBPP accounting for such delays. By using simple transformation and piecewise outer-approximation, we linearize the model, and present an efficient cutting plane based approach to solve the resulting linear mixed integer program to optimality.