Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Soft Computing
Published in: Soft Computing 6/2019

13-11-2017 | Methodologies and Application

A parallel hybrid optimization algorithm for some network design problems

Authors: Ibrahima Diarrassouba, Mohamed Khalil Labidi, A. Ridha Mahjoub

Published in: Soft Computing | Issue 6/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Network design problems have been widely studied in the last decades due to the importance of ICT in our daily life and are still the subject of extensive researches. Network design covers a large family of problems, and several algorithms, both exact and heuristic methods, have been proposed to address each of them. In this paper, we consider two variants of the so-called survivable network design problem and propose a generic parallel hybrid algorithm to solve them. The algorithm is based on the hybridization of a Lagrangian relaxation algorithm, a greedy algorithm and a genetic algorithm. We present, for each variant, a computational study showing the efficiency of our approach in producing both lower and upper bounds for the optimal solution.
previous article An extensive evaluation of search-based software testing: a review
next article Structure evolution-based design for low-pass IIR digital filters with the sharp transition band and the linear phase passband

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: theory, algorithms, and applications. Prentice-Hall Inc., Upper Saddle RiverMATH
Beasley J E (1993) Modern heuristic techniques for combinatorial problems. Chapter lagrangian relaxation. Wiley, New York, pp 243–303
Bendali F, Diarrassouba I, Didi Biha M, Mahjoub AR, Mailfert J (2010) A branch-and-cut algorithm for the \(k\)-edge connected subgraph problem. Networks 55(1):13–32MathSciNetMATHCrossRef
Botton Q, Fortz B, Gouveia L, Poss M (2013) Benders decomposition for the hop-constrained survivable network design problem. INFORMS J Comput 25(1):13–26MathSciNetCrossRef
Diarrassouba I, Gabrel V, Gouveia L, Mahjoub AR, Pesneau P (2016a) Integer programming formulations for the \(k\)-edge-connected 3-hop-constrained network design problem. Networks 67(2):148–169MathSciNetMATHCrossRef
Diarrassouba I, Mahjoub AR, Kutucu H (2016b) Two node-disjoint hop-constrained survivable network design and polyhedra. Networks 67(4):316–337MathSciNetMATHCrossRef
Diarrassouba I, Mahjoub AR, Yaman H (2017) Integer programming formulations for \(k\)-node-connected hop-constrained survivable network design problem. In: Cahier du LAMSADE, vol 382
Goemans MX, Bertsimas DJ (1993) Survivable networks, linear programming relaxations and the parsimonious property. Math Program 60(1–3):145–166MathSciNetMATHCrossRef
Grötschel M, Monma CL (1990) Integer polyhedra arising from certain network design problems with connectivity constraints. SIAM J Discrete Math 3(4):502–523MathSciNetMATHCrossRef
Grötschel M, Monma CL, Stoer M (1992) Facets for polyhedra arising in the design of communication networks with low-connectivity constraints. SIAM J Optim 2(3):474–504
Held M, Karp RM (1971) The traveling-salesman problem and minimum spanning trees: part ii. Math Program 1(1):6–25MATHCrossRef
Huygens D, Labbé M, Mahjoub AR, Pesneau P (2007) The two-edge connected hop-constrained network design problem: valid inequalities and branch-and-cut. Networks 49(1):116–133MathSciNetMATHCrossRef
Kerivin H, Mahjoub AR, Nocq C (2004) (1, 2)-Survivable networks: facets and branch-and-cut. In: Grötschel M (ed) The Sharpest Cut, MPS-SIAM series in Optimization. SIAM, pp 121–152
Magnanti TL, Raghavan S (2005) Strong formulations for network design problems with connectivity requirements. Networks 45(2):61–79MathSciNetMATHCrossRef
Steiglitz K, Weiner P, Kleitman D (1969) The design of minimum-cost survivable networks. IEEE Trans Circuit Theory 16(4):455–460MathSciNetCrossRef
Talbi E-G (2002) A taxonomy of hybrid metaheuristics. J Heuristics 8(5):541–564CrossRef
Metadata
Title
A parallel hybrid optimization algorithm for some network design problems
Authors
Ibrahima Diarrassouba
Mohamed Khalil Labidi
A. Ridha Mahjoub
Publication date
13-11-2017
Publisher
Springer Berlin Heidelberg
Published in
Soft Computing / Issue 6/2019
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-017-2907-x

Other articles of this Issue 6/2019

Soft Computing 6/2019 Go to the issue

Methodologies and Application

Modeling and comparison of the series systems with imperfect coverage for an unreliable server

Methodologies and Application

Efficient obfuscation for CNF circuits and applications in cloud computing

Focus

A new edge detection method based on global evaluation using fuzzy clustering

Editorial

Editorial to image processing with soft computing techniques

Focus

An image segmentation technique using nonsubsampled contourlet transform and active contours

Focus

Total variation with nonlocal FT-Laplacian for patch-based inpainting

Premium Partner

    Image Credits