On Monte Carlo Tree Search for Weighted Vertex Coloring
This work addresses a combinatorial optimization problem for researchers in algorithms and operations research, but it is incremental as it adapts existing MCTS methods to a specific domain.
The authors tackled the Weighted Vertex Coloring Problem by applying Monte Carlo Tree Search (MCTS) combined with heuristics, achieving results evaluated on benchmark instances to compare different algorithmic variants.
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.