Reformulation and Decomposition Approaches for Traffic Routing in Optical Networks
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport [CIRRELT] | |
| dc.contributor.author | VIGNAC, Benoit | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | VANDERBECK, François | |
| hal.structure.identifier | Concordia Institute for Information Systems Engineering [CIISE] | |
| dc.contributor.author | JAUMARD, Brigitte | |
| dc.date.accessioned | 2024-04-04T03:16:54Z | |
| dc.date.available | 2024-04-04T03:16:54Z | |
| dc.date.created | 2015-11-27 | |
| dc.date.issued | 2016-07-01 | |
| dc.identifier.issn | 0028-3045 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/194258 | |
| dc.description.abstractEn | We consider a multi-layer network design model arising from a real-life telecommunication application where traffic routingdecisions imply the installation of expensive nodal equipment. Customer requests come in the form of bandwidthreservations for a given origin destination pair. Bandwidth demands are expressed as multiples of nominal granularities. Each request must be single-path routed. Grooming several requests on the same wavelength and multiplexing wavelengths in the same optical stream allow a more efficient use of network capacity. However, each addition or withdrawal of a request from a wavelength requires optical to electrical conversion and the use of cross-connect equipment with expensive ports of high densities. The objective is to minimize the number of required ports of the cross-connect equipment. We deal with backbone optical networks, therefore with networks with a moderate number of nodes (14 to 20) but thousands of requests. Further difficulties arise from the symmetries in wavelength assignment and traffic loading. Traditional multi-commodity network flowapproaches are not suited for this problem. Instead, four alternative models relying on Dantzig-Wolfe and/or Benders' decomposition areintroduced and compared. The formulations are strengthened using symmetry breaking restrictions, variable domain reduction, zero-onediscretization of integer variables, and cutting planes. The resulting dual bounds are compared to the values of primal solutions obtained through hierarchical optimization and rounding procedures. For realistic size instances, our best approaches provide solutions with optimality gap of approximately 5% on average in around two hours of computing time. | |
| dc.language.iso | en | |
| dc.publisher | Wiley | |
| dc.title.en | Reformulation and Decomposition Approaches for Traffic Routing in Optical Networks | |
| dc.type | Article de revue | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | Networks | |
| bordeaux.page | 277-298 | |
| bordeaux.volume | 67 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 4 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | inria-00392256 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00392256v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Networks&rft.date=2016-07-01&rft.volume=67&rft.issue=4&rft.spage=277-298&rft.epage=277-298&rft.eissn=0028-3045&rft.issn=0028-3045&rft.au=VIGNAC,%20Benoit&VANDERBECK,%20Fran%C3%A7ois&JAUMARD,%20Brigitte&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||