nach oben

Soft Computing

Erschienen in:

13.11.2017 | Methodologies and Application

A parallel hybrid optimization algorithm for some network design problems

verfasst von: Ibrahima Diarrassouba, Mohamed Khalil Labidi, A. Ridha Mahjoub

Erschienen in: Soft Computing | Ausgabe 6/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel An extensive evaluation of search-based software testing: a review

Nächster Artikel Structure evolution-based design for low-pass IIR digital filters with the sharp transition band and the linear phase passband

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

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

CPLEX (12.5). IBM CPLEX. http://www-01.ibm.com/software/info/ilog

Dahl G, Gouveia L (2004) On the directed hop-constrained shortest path problem. Oper Res Lett 32(1):15–22MathSciNetMATHCrossRef

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 (2005) Design of survivable networks: a survey. Networks 46(1):1–21MathSciNetMATHCrossRef

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

TSPLIB (1995) Gerhard reinelt. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95. Accessed 13 Dec 2015

Winter P (1987) Steiner problem in networks: a survey. Networks 17(2):129–167MathSciNetMATHCrossRef

Titel: A parallel hybrid optimization algorithm for some network design problems
verfasst von: Ibrahima Diarrassouba
Mohamed Khalil Labidi
A. Ridha Mahjoub
Publikationsdatum: 13.11.2017
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 6/2019
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-017-2907-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 6/2019

Fusion linear representation-based classification

Discussing incomplete 2-tuple fuzzy linguistic preference relations in multi-granular linguistic MCGDM with unknown weight information

Hyperspectral imaging using notions from type-2 fuzzy sets

A new approach to construct similarity measure for intuitionistic fuzzy sets

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

Energy-aware virtual machine allocation and selection in cloud data centers

Premium Partner