Population-based Gradient Descent Weight Learning for Graph Coloring Problems.

Graph coloring involves assigning colors to the vertices of a graph such that two vertices linked by an edge receive different colors. Graph coloring problems are general models that are very useful to formulate many relevant applications and, however, are computationally difficult. In this work, we present a general population-based weight learning framework for solving graph coloring problems. Unlike existing methods for graph coloring that are specific to the considered problem, our work targets a generic objective by introducing a unified method that can be applied to different graph coloring problems. This work distinguishes itself by its solving approach that formulates the search of a solution as a continuous weight tensor optimization problem and takes advantage of a gradient descent method implemented on GPU devices. The proposed approach is also characterized by its general global loss function that can easily be adapted to different graph coloring problems. We demonstrate the usefulness of the proposed approach by applying it to solve two typical graph coloring problems and performing large computational studies on popular benchmarks. We also report improved best-known results (new upper bounds) for several large graphs.