The multi-hour bandwidth packing problem arises in telecommunication networks that span several time horizon. The problem seeks to select and route a set of messages from a given list of messages with prespecified requirement on demand for bandwidth under time varying traffic conditions on an undirected communication network such that the total profit is maximized. The total profit is computed based on the total revenue and the flow cost as well as communication delay cost. Under Poisson call arrival rates and exponential service time distributions on the links, the problem is setup as a network of spatially distributed M/M/1 queues and formulated as a nonlinear integer programming model. Using simple transformation and piecewise linearization, we present a linear mixed integer programming formulation of the model with large number of constraints. We derive lower and upper bounds for the linearized model and present a cutting plane algorithm based exact solution approach that makes successive improvements to the lower and corresponding upper bound as the iteration progresses. The extension of the proposed modelling framework and solution approach to generalized case with Poisson call arrival rates and general service time distributions on the links (M/G/1 case) is also presented. Computational results indicate that the exact method provides optimal solution in reasonable computational times.
View The Multi-Hour Bandwidth Packing Problem with Queuing Delays: Bounds and Exact Solution Approach