Afficher la notice abrégée

Exact Algorithms for a Bandwidth Packing Problem with Queueing Delay Guarantees

hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
hal.structure.identifierKorea Advanced Institute of Science and Technology [KAIST]
dc.contributor.authorHAN, Jinil
hal.structure.identifierHankuk University of Foreign Studies [HUFS]
dc.contributor.authorLEE, Kyungsik
hal.structure.identifierElectronics and Telecommunications Research Institute [DaeJeon] [ETRI]
dc.contributor.authorLEE, Chungmok
hal.structure.identifierKorea Advanced Institute of Science and Technology [KAIST]
dc.contributor.authorPARK, Sungsoo
dc.date.accessioned2024-04-04T02:21:36Z
dc.date.available2024-04-04T02:21:36Z
dc.date.issued2013-08-01
dc.identifier.issn1091-9856
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/189589
dc.description.abstractEnThe 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.
dc.language.isoen
dc.publisherInstitute for Operations Research and the Management Sciences (INFORMS)
dc.subject.enbandwidth packing
dc.subject.enqueueing delay
dc.subject.entelecommunications networks
dc.subject.enbranch-and-price procedure
dc.subject.eninteger programming
dc.title.enExact Algorithms for a Bandwidth Packing Problem with Queueing Delay Guarantees
dc.typeArticle de revue
dc.identifier.doi10.1287/ijoc.1120.0523
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalINFORMS Journal on Computing
bordeaux.page585-596
bordeaux.volume25
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.issue3
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00857862
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00857862v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=INFORMS%20Journal%20on%20Computing&rft.date=2013-08-01&rft.volume=25&rft.issue=3&rft.spage=585-596&rft.epage=585-596&rft.eissn=1091-9856&rft.issn=1091-9856&rft.au=HAN,%20Jinil&LEE,%20Kyungsik&LEE,%20Chungmok&PARK,%20Sungsoo&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée