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 条
  • [41] The price of connectedness in graph partitioning problems
    Martin, Nicolas
    Frasca, Paolo
    Ishizaki, Takayuki
    Imura, Jun-Ichi
    Canudas-de-Wit, Carlos
    2019 18TH EUROPEAN CONTROL CONFERENCE (ECC), 2019, : 2313 - 2318
  • [42] EXPECTED COMPLEXITY OF GRAPH PARTITIONING PROBLEMS
    KUCERA, L
    DISCRETE APPLIED MATHEMATICS, 1995, 57 (2-3) : 193 - 212
  • [43] Parameterized Algorithms for Graph Partitioning Problems
    Shachnai, Hadas
    Zehavi, Meirav
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2014, 8747 : 384 - 395
  • [44] Solving molecular flexible docking problems with metaheuristics: A comparative study
    Lopez-Camacho, Esteban
    Garcia Godoy, Maria Jesus
    Garcia-Nieto, Jose
    Nebro, Antonio J.
    Aldana-Montes, Jose F.
    APPLIED SOFT COMPUTING, 2015, 28 : 379 - 393
  • [45] On the adoption of Metaheuristics for Solving 0-1 Knapsack Problems
    Qiu, Yang
    Li, Haomiao
    Wang, Xiao
    Dib, Omar
    PAAP 2021: 2021 12TH INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES, ALGORITHMS AND PROGRAMMING, 2021, : 56 - 61
  • [46] Solving permutational routing problems by population-based metaheuristics
    Bozejko, Wojciech
    Wodecki, Mieczyslaw
    COMPUTERS & INDUSTRIAL ENGINEERING, 2009, 57 (01) : 269 - 276
  • [47] A Multiagent Architecture for solving Combinatorial Optimization Problems through Metaheuristics
    Fernandes, Filipe Costa
    de Souza, Sergio Ricardo
    Lopes Silva, Maria Amelia
    Borges, Henrique Elias
    Ribeiro, Fabio Fernandes
    2009 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS (SMC 2009), VOLS 1-9, 2009, : 3071 - 3076
  • [48] Solving vehicle routing problems using constraint programming and metaheuristics
    Backer, BD
    Furnon, V
    Shaw, P
    Kilby, P
    Prosser, P
    JOURNAL OF HEURISTICS, 2000, 6 (04) : 501 - 523
  • [49] Parameterized Algorithms for Graph Partitioning Problems
    Shachnai, Hadas
    Zehavi, Meirav
    THEORY OF COMPUTING SYSTEMS, 2017, 61 (03) : 721 - 738
  • [50] Solving Vehicle Routing Problems Using Constraint Programming and Metaheuristics
    Bruno De Backer
    Vincent Furnon
    Paul Shaw
    Philip Kilby
    Patrick Prosser
    Journal of Heuristics, 2000, 6 : 501 - 523