Abstract

Several recent studies have shown the efficacy of unconstrained binary quadratic programming (UBQP) to model and solve many combinatorial problems. In this paper we are interested in the minimum sum coloring problem (MSCP), a new variant of the traditional graph coloring problem (GCP). We give a reformulation of the problem (MSCP) as an unconstrained binary quadratic binary programming, and we resolve it afterward by a genetic algorithms. The proposed algorithm is evaluated on the DIMACS challenge benchmarks and computational results show that the proposed UBQP model achieves highly competitive results, compared with 4 state-of-the-art algorithms.

This work is licensed under a Creative Commons Attribution 4.0 License.