Matheuristic Variants of DSATUR for the Vertex Coloring Problem

被引：0
作者：
Dupin, Nicolas [1 ]
机构：
[1] Univ Angers, LERIA, SFR MATHSTIC, F-49000 Angers, France
来源：
METAHEURISTICS, MIC 2024, PT II | 2024年 / 14754卷
关键词：
Matheuristic; Vertex Coloring; DSATUR; cliques; dual heuristic; ALGORITHM; GRAPH;
D O I：
10.1007/978-3-031-62922-8_7
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
This paper extends with matheuristic operators the seminal DSATUR heuristic for the Vertex Coloring Problem. Firstly, matheuristics are proposed to initialize saturation computing using a clique, a partial optimal coloring with selected vertices or combining both previous strategies. Secondly, an Integer Linear Programming formulation is designed to have larger local greedy optimization in DSATUR construction scheme. Thirdly, dual bounds are obtained with local optimization to improve first lower bounds implied by cliques. Computational results are provided to analyze inefficiency causes of DSATUR heuristic, highlighting the strengths and weaknesses of DSATUR heuristics.
引用
收藏
页码：96 / 111
页数：16
相关论文
共 21 条
  • [1] Matheuristics: survey and synthesis
    Boschetti, Marco A.
    Letchford, Adam N.
    Maniezzo, Vittorio
    [J]. INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2023, 30 (06) : 2840 - 2866
  • [2] Matheuristics: using mathematics for heuristic design
    Boschetti, Marco Antonio
    Maniezzo, Vittorio
    [J]. 4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2022, 20 (02): : 173 - 208
  • [3] NEW METHODS TO COLOR THE VERTICES OF A GRAPH
    BRELAZ, D
    [J]. COMMUNICATIONS OF THE ACM, 1979, 22 (04) : 251 - 256
  • [4] On the asymmetric representatives formulation for the vertex coloring problem
    Campelo, Manoel
    Campos, Victor A.
    Correa, Ricardo C.
    [J]. DISCRETE APPLIED MATHEMATICS, 2008, 156 (07) : 1097 - 1111
  • [5] Chandrasekharan R.C., 2021, 13 INT C PRACT THEOR, V1
  • [6] Chiarandini M., 2011, P 9 METAH INT C MIC, P461
  • [7] Solving vertex coloring problems as maximum weight stable set problems
    Cornaz, Denis
    Furini, Fabio
    Malaguti, Enrico
    [J]. DISCRETE APPLIED MATHEMATICS, 2017, 217 : 151 - 162
  • [8] Matheuristics and Column Generation for a Basic Technician Routing Problem
    Dupin, Nicolas
    Parize, Remi
    Talbi, El-Ghazali
    [J]. ALGORITHMS, 2021, 14 (11)
  • [9] Machine Learning-Guided Dual Heuristics and New Lower Bounds for the Refueling and Maintenance Planning Problem of Nuclear Power Plants
    Dupin, Nicolas
    Talbi, El-Ghazali
    [J]. ALGORITHMS, 2020, 13 (08)
  • [10] Matheuristics to optimize refueling and maintenance planning of nuclear power plants
    Dupin, Nicolas
    Talbi, El-Ghazali
    [J]. JOURNAL OF HEURISTICS, 2021, 27 (1-2) : 63 - 105
123