Exact weighted vertex coloring via branch-and-price

We consider the Weighted Vertex Coloring Problem (WVCP), in which a positive weight is associated to each vertex of a graph. In WVCP, one is required to assign a color to each vertex in such a way that colors on adjacent vertices are different, and the objective is to minimize the sum of the costs of the colors used, where the cost of each color is given by the maximum weight of the vertices assigned to that color. This NP-hard problem arises in practical scheduling applications, where it is also known as Scheduling on a Batch Machine with Job Compatibilities. We propose the first exact algorithm for the problem, which is based on column generation and branch-and-price. Computational results on a large set of instances from the literature are reported, showing excellent performance when compared with the best heuristic algorithms from the literature. (C) 2012 Elsevier B.V. All rights reserved.