Optimization Online


The Multi-Hour Bandwidth Packing Problem with Queuing Delays: Bounds and Exact Solution Approach

Navneet Vidyarthi(navneet.vidyarthi***at***gmail.com)
Arjun Bhardwaj(bhardwaj.arjun.14***at***gmail.com)
Niraj Sinha(nirajsinha***at***gmail.com)

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

Keywords: Bandwidth Packing, Telecommunication Networks, Time Varying Demand, Call Routing, Queueing Delays, Congestion, Linearization, Exact Approach

Category 1: Applications -- OR and Management Sciences


Download: [PDF]

Entry Submitted: 11/03/2014
Entry Accepted: 11/03/2014
Entry Last Modified: 11/03/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society