2022/02/03 by Cyril Grelier, Olivier Goudet, Grelier, Cyril +4
Computer Science · Decision Sciences · #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Machine Learning (cs.LG) #Scheduling and Timetabling Solutions #cs.LG
paper · pdf · doi:10.48550/arxiv.2202.01665
16 pages, 2 tables, 4 plots
openalex publication_date 2022/02/03 · arxiv created 2022/04/07 · arxiv updated 2022/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This work presents the first study of using the popular Monte Carlo Tree Search (MCTS) method combined with dedicated heuristics for solving the Weighted Vertex Coloring Problem. Starting with the basic MCTS algorithm, we gradually introduce a number of algorithmic variants where MCTS is extended by various simulation strategies including greedy and local search heuristics. We conduct experiments on well-known benchmark instances to assess the value of each studied combination. We also provide empirical evidence to shed light on the advantages and limits of each strategy.