2023/04/24 by Cyril Grelier, Grelier, Cyril, Olivier Goudet +3
Computer Science · Decision Sciences · #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Scheduling and Timetabling Solutions
paper · pdf · doi:10.48550/arxiv.2304.12146
openalex publication_date 2023/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This work investigates the Monte Carlo Tree Search (MCTS) method combined with dedicated heuristics for solving the Weighted Vertex Coloring Problem. In addition to the basic MCTS algorithm, we study several MCTS variants where the conventional random simulation is replaced by other simulation strategies including greedy and local search heuristics. We conduct experiments on well-known benchmark instances to assess these combined MCTS variants. We provide empirical evidence to shed light on the advantages and limits of each simulation strategy. This is an extension of the work of Grelier and al. presented at EvoCOP2022.