Solving Graph Partitioning Problems with Parallel Metaheuristics

被引:4
|
作者
Kokosinski, Zbigniew [1 ]
Bala, Marcin [2 ]
机构
[1] Cracow Univ Technol, Fac Elect & Comp Engn, Ul Warszawska 24, PL-31155 Krakow, Poland
[2] Salumanus Sp Zoo, Ul Walerego Slawka 8a, PL-30633 Krakow, Poland
来源
RECENT ADVANCES IN COMPUTATIONAL OPTIMIZATION, WCO 2016 | 2018年 / 717卷
关键词
Simulated annealing; Tabu search; Parallel metaheuristic; Hybrid metaheuristic; Graph partitioning problem; Graph partitioning number;
D O I
10.1007/978-3-319-59861-1_6
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
In this article we describe computer experiments while testing a family of parallel and hybrid metaheuristics against a small set of graph partitioning problems like clustering, partitioning into cliques and coloring. In all cases the search space is composed of vertex partitions satisfying specific problem requirements. The solver application contains two sequential and nine parallel/hybrid algorithms developed on the basis of SA and TS metaheuristics. A number of tests are reported and conclusions concerning metaheuristics' performance that result from the conducted experiments are derived. The article provides a case study in which partitioning numbers psi(k)(G), k >= 2, of DIMACS graph coloring instances are evaluated experimentally by means of H-SP metaheuristic which is found to be the most efficient in terms of solution quality.
引用
收藏
页码:89 / 105
页数:17
相关论文
共 50 条
  • [31] Two metaheuristics approaches for solving the traveling salesman problem: an Algerian waste collection case
    Khalid Mekamcha
    Mehdi Souier
    Hakim Nadhir Bessenouci
    Mohammed Bennekrouf
    Operational Research, 2021, 21 : 1641 - 1661
  • [32] On a parallel genetic-tabu search based algorithm for solving the graph colouring problem
    Ben Mabrouk, Bchira
    Hasni, Hamadi
    Mahjoub, Zaher
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2009, 197 (03) : 1192 - 1201
  • [33] Solving large-scale time capacitated arc routing problems: from real-time heuristics to metaheuristics
    Jesica de Armas
    Peter Keenan
    Angel A. Juan
    Seán McGarraghy
    Annals of Operations Research, 2019, 273 : 135 - 162
  • [34] Parallel hybrid metaheuristics for the flexible job shop problem
    Bozejko, Wojciech
    Uchronski, Mariusz
    Wodecki, Mieczyslaw
    COMPUTERS & INDUSTRIAL ENGINEERING, 2010, 59 (02) : 323 - 333
  • [35] Solving large-scale time capacitated arc routing problems: from real-time heuristics to metaheuristics
    de Armas, Jesica
    Keenan, Peter
    Juan, Angel A.
    McGarraghy, Sean
    ANNALS OF OPERATIONS RESEARCH, 2019, 273 (1-2) : 135 - 162
  • [36] An experimental evaluation of local search heuristics for graph partitioning
    J. L. Ganley
    L. S. Heath
    Computing, 1998, 60 : 121 - 132
  • [37] An experimental evaluation of local search heuristics for graph partitioning
    Ganley, JL
    Heath, LS
    COMPUTING, 1998, 60 (02) : 121 - 132
  • [38] Parallel Metaheuristics for Shop Scheduling: enabling Industry 4.0
    Coelho, Pedro
    Silva, Cristovao
    PROCEEDINGS OF THE 2ND INTERNATIONAL CONFERENCE ON INDUSTRY 4.0 AND SMART MANUFACTURING (ISM 2020), 2021, 180 : 778 - 786
  • [39] Generic metaheuristics application to industrial engineering problems
    Fink, A
    Voss, S
    COMPUTERS & INDUSTRIAL ENGINEERING, 1999, 37 (1-2) : 281 - 284
  • [40] Tabu search for graph partitioning
    Rolland, E
    Pirkul, H
    Glover, F
    ANNALS OF OPERATIONS RESEARCH, 1996, 63 : 209 - 232