HAN, Jinil; LEE, Kyungsik; LEE, Chungmok; PARK, Sungsoo

doi:10.1287/ijoc.1120.0523

Métadonnées

Licence d’utilisation du document

HAN, Jinil
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Korea Advanced Institute of Science and Technology [KAIST]

LEE, Kyungsik
Hankuk University of Foreign Studies [HUFS]

LEE, Chungmok
Electronics and Telecommunications Research Institute [DaeJeon] [ETRI]

Langue

Article de revue

Ce document a été publié dans

INFORMS Journal on Computing. 2013-08-01, vol. 25, n° 3, p. 585-596

Institute for Operations Research and the Management Sciences (INFORMS)

Résumé en anglais

The bandwidth packing problem (BWP) concerns the selection of calls from a given set and the assignment of one path to each selected call. The ultimate aim of the BWP is to maximize profit while the routings of the selected calls observe the capacity constraints of the links. Here, we additionally consider queueing delays in the network, which may cause a deterioration in the quality of service to users if they exceed the acceptable limits. The integer programming formulation for the BWP with the queueing delay restriction contains a nonlinear constraint that is intrinsic to the model. We apply the Dantzig-Wolfe decomposition to this nonlinear constraint, and since the Dantzig-Wolfe decomposition has exponentially many variables, we propose the branch-and-price procedure to find optimal solutions. We also propose a generalized Dantzig-Wolfe reformulation based on the aggregation of variables, which makes our branch-and-price algorithm more competitive. Computational results on cases of randomly generated networks and some real-life telecommunication networks demonstrate that our algorithm performs well for large networks.< Réduire

Mots clés en anglais

bandwidth packing

queueing delay

telecommunications networks

branch-and-price procedure

integer programming

Métadonnées

Partager cette publication !

Licence d’utilisation du document

Exact Algorithms for a Bandwidth Packing Problem with Queueing Delay Guarantees

Langue

Ce document a été publié dans

Résumé en anglais

Mots clés en anglais

URI

DOI

Origine

Unités de recherche