Solving the Fixed Graph Coloring Problem by Simulated Annealing and Greedy Search

Local search techniques, such as simulated annealing and greedy search, have been used to solve various NP-hard problems, and it is well known that the graph coloring problem (GCP) is one of the most studied NP-hard optimization problems. In this paper, an adaptive local search algorithm is proposed to solve the GCP. The proposed algorithm is based on the standard simulated annealing technique, and makes the best of greedy search technique and search local strategy to speed up the convergence rate. Aim at the greedy search parameters, the run time for given benchmark instance, annealing temperature and its cool coefficient, adaptive control of the parameters and multistage simulated annealing are designed in order to improve quality-time trade-off of the proposed local search algorithm. As a result, our algorithm achieves a reasonable trade-off between computation time, solution quality, and complexity of implementation, and simulation results indicate that the proposed algorithm performs well on a set of 119 benchmark instances.