A branch and price approach for the robust bandwidth packing problem with queuing delays

Seohee Kim and Chungmok Lee ()
Additional contact information
Seohee Kim: Hankuk University of Foreign Studies
Chungmok Lee: Hankuk University of Foreign Studies

Annals of Operations Research, 2021, vol. 307, issue 1, No 13, 275 pages

Abstract: Abstract This paper considers a variant of the bandwidth packing problem that determines paths for selected demands on a telecommunication network with given arc capacities to maximize the total revenue. Facilities on the arcs can be seen as M/M/1 queuing systems, which incur queuing delays that should be minimized by adding them to the objective function as a penalty. We also consider the case in which the demands are uncertain, so both the capacity and queuing delay of an arc should take the uncertainty of demand into account. The mathematical formulation for the problem is stated as a nonlinear integer programming problem due to the queuing delays added in the objective function. We first show that the formulation can be linearized to a mixed integer linear programming problem that can be solved by off-the-shelf MIP solvers like Cplex. We then propose a branch-and-price approach by showing that the column generation problem can be solved efficiently by a dynamic programming algorithm. Computational experiments with benchmark instances show that the proposed approach significantly outperforms the state-of-the-art MIP solver in terms of computational times. We also report a Monte-Carlo simulation study with randomly generated demand scenarios to assert the benefits of the robust approach.

Keywords: Bandwidth packing problem; Branch-and-price; Robust optimization; Queuing delay; Knapsack problem (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-021-04292-w 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:annopr:v:307:y:2021:i:1:d:10.1007_s10479-021-04292-w

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-021-04292-w

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().