An improved Benders decomposition applied to a multi-layer network design problem

Fortz, Bernard; Poss, M.

doi:10.1016/j.orl.2009.05.007

Download

Article (Scientific journals)

An improved Benders decomposition applied to a multi-layer network design problem

Fortz, Bernard; Poss, M.

2009 • In Operations Research Letters, 37 (5), p. 359-364

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/324077

DOI
10.1016/j.orl.2009.05.007

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

Elsevier_30596_PostprintAuteur.pdf

Author postprint (380.97 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Multi-layer network design; Metric inequalities; Branch-and-cut

Abstract :

[en] Benders decomposition has been widely used for solving network design problems. In this paper, we use a branch-and-cut algorithm to improve the separation procedure of Gabrel et al. and Knippel et al. for capacitated network design. We detail experiments on bi-layer networks, comparing with Knippel’s previous results.

Disciplines :

Quantitative methods in economics & management

Author, co-author :

Fortz, Bernard ; Université de Liège - ULiège > HEC Liège Research > HEC Liège Research: Business Analytics & Supply Chain Mgmt

Poss, M.

Language :

English

Title :

An improved Benders decomposition applied to a multi-layer network design problem

Publication date :

2009

Journal title :

Operations Research Letters

ISSN :

0167-6377

eISSN :

1872-7468

Volume :

Issue :

Pages :

359-364

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://www.scopus.com/inward/record.uri?eid=2-s2.0-69549109987&doi=10.1016%2fj.orl.2009.05.007&partnerID=40&md5=0a91ed30790ce4cddddbaade3f581003

Available on ORBi :

since 05 November 2024

Statistics

Number of views

3 (1 by ULiège)

Number of downloads

0 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Pióro M., and Medhi D. Routing, Flow, and Capacity Design in Communication and Computer Networks (2004), Elsevier
D. Yuan, An annotated bibliography in communication network design and routing, Ph.D. Thesis, Institute of Technology, Linköpings Universitet, 2001
Dahl G., Martin A., and Stoer M. Routing through virtual paths in layered telecommunication networks. Operations Research 47 5 (1999) 693-702
S. Orlowski, R. Wessäly, An integer programming model for multi-layer network design, ZIB Preprint ZR-04-49, December 2004
P. Belotti, F. Malucelli, Row-column generation for multilayer network design, in: Proceedings, International Network Optimization Conference, Lisbon, Portugal, March 2005
A.M.C.A. Koster, S. Orlowski, C. Raack, R. Wessäly, Two-layer network design by branch-and-cut featuring MIP-based heuristics, in: Proceedings of INOC, Spa, Belgium, April 2007
G. Baier, T. Engel, A.M.C.A. Koster, S. Orlowski, C. Raack, R. Wessäly, Single-layer cuts for multi-layer network design problems, ZIB Report ZR-07-21, August 2007
A.M.C.A. Koster, S. Orlowski, C. Raack, R. Wessäly, Capacitated network design using general flow-cutset inequalities, ZIB Report 07-14, Networks (2007) (submitted for publication)
P. Belotti, A. Capone, G. Carello, F. Malucelli, F. Senaldi, A. Totaro, Mpls over transport network: Two layers approach to network design with statistical multiplexing, in: Conference on Next Generation Internet Design and Engineering, NGI 2006, Valencia, Spain, April 2006
A. Capone, G. Carello, R. Matera, Multi-layer network design with multicast traffic and statistical multiplexing, in: IEEE GLOBECOM 2007, Washington DC, USA, December 2007
E. Kubilinskas, M. Pióro, An ip/mpls over wdm network design problem, in: Proceedings of INOC, vol. 3, Lisbon, 2005
Holler H., and Voss S. A heuristic approach for combined equipment-planning and routing in multi-layer sdh/wdm networks. European Journal of Operational Research 127 3 (2006) 787-796
Gabrel V., Knippel A., and Minoux M. Exact solution of multicommodity network optimization problems with general step cost functions. Operations Research Letters 25 9 (1999) 15-23
Knippel A., and Lardeux B. The multi-layered network design problem. European Journal of Operational Research 127 1 (2007) 87-99
Geffard J., Lardeux B., and Nace D. Multiperiod network design with incremental routing. Networks 50 1 (2007) 109-117
A. Knippel, B. Lardeux, J. Geffard, Efficient algorithms for solving the 2-layered network design problem, in: Proceedings of INOC, Paris, 2003
Deza M., and Laurent M. Geometry of Cuts and Metrics, vol. 15 (1997), Springer
Costa A.M. A survey on benders decomposition applied to fixed-charge network design problems. Computers & Operations Research 32 6 (2005) 1429-1450
Avella P., Mattia S., and Sassano A. Metric inequalities and the network loading problem. Discrete Optimization 4 (2007) 103-114
Birge J.R., and Louveaux F.V. Introduction to Stochastic Programming. 2nd ed. (2008), Springer Verlag, New-York
T.G. Crainic, B. Gendron, Relaxations for multicommodity capacitated network design problems, Tech. Report Publication CRT-965, Centre de recherche sur les transports, Université de Montréal, 1994
S. Orlowski, M. Pióro, A. Tomaszewski, R. Wessäly, SNDlib 1.0 - Survivable network design library, in: Proceedings of INOC, Spa, Belgium, April 2007. http://sndlib.zib.de