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, a
general population-based weight learning framework for solving graph coloring
problems is presented. Unlike existing methods for graph coloring that are
specific to the considered problem, the presented 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 computed
in parallel on graphics processing units. The proposed approach is also
characterized by its general global loss function that can easily be adapted to
different graph coloring problems. The usefulness of the proposed approach is
demonstrated by applying it to solve two typical graph coloring problems and
performing large computational studies on popular benchmarks. Improved
best-known results (new upper bounds) are reported for several large graphs.
