A proper coloring of a given graph is an assignment of colors (integer numbers) to its vertices such that two adjacent vertices receives di different colors. This paper studies the Minimum Sum Coloring Problem (MSCP), which asks for fi nding a proper coloring while minimizing the sum of the colors assigned to the vertices. This paper presents the rst branch-and-price algorithm to solve the MSCP to proven optimality. The newly developed exact approach is based on an Integer Programming (IP) formulation with an exponential number of variables which is tackled by column generation. Extensive computational experiments, on synthetic and benchmark graphs from the literature, show that the new algorithm outperforms a natural compact IP formulations in terms of: (i) number of solved instances, (ii) running times and (iii) dual gaps obtained when optimality is not achieved. The new exact method is able to solve to optimality 8 out of the 17 (yet unclosed) hard DIMACS instances tested in this work.
Article
View A Branch-and-Price Algorithm for the Minimum Sum Coloring Problem