A constructive matheuristic approach for the vertex colouring problem

Abstract

The vertex colouring problem is one of the most widely studied and popular problems in graph theory. In light of the recent interest in hybrid methods involving mathematical programming, this paper presents an attempt to design a matheuristic approach for the problem. A decomposition-based approach is introduced which utilizes an integer programming formulation to solve subproblems to optimality. A detailed study of two different decomposition strategies, vertex-based and colour-based, is discussed. The impact of algorithm design parameters on the decompositions used and their influence on final solution quality is explored. In addition to integer programming, a constraint programming is also employed to solve the subproblems.