Bandwidth packing problem with queueing delays: modelling and exact solution approach

Navneet Vidyarthi (), Sachin Jayaswal () and Vikranth Babu Tirumala Chetty ()
Additional contact information
Navneet Vidyarthi: Concordia University
Sachin Jayaswal: Indian Institute of Management
Vikranth Babu Tirumala Chetty: University of Washington

Journal of Global Optimization, 2016, vol. 65, issue 4, No 5, 745-776

Abstract: Abstract We present a more generalized model for the bandwidth packing problem with queuing delays under congestion than available in the extant literature. The problem, under Poison call arrivals and general service times, is set up as a network of spatially distributed independent M/G/1 queues. We further present two exact solution approaches to solve the resulting nonlinear integer programming model. The first method, called finite linearization method, is a conventional Big-M based linearization, resulting in a finite number of constraints, and hence can be solved using an off-the-shelve MIP solver. The second method, called constraint generation method, is based on approximating the non-linear delay terms using supporting hyperplanes, which are generated as needed. Based on our computational study, the constraint generation method outperforms the finite linearization method. Further comparisons of results of our proposed constraint generation method with the Lagrangean relaxation based solution method reported in the literature for the special case of exponential service times clearly demonstrate that our approach outperforms the latter, both in terms of the quality of solution and computation times.

Keywords: Bandwidth packing; Telecommunications; Call routing; Integer programming; Queuing delay; Finite linearization; Constraint generation (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-015-0399-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:65:y:2016:i:4:d:10.1007_s10898-015-0399-8

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-015-0399-8

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().