Stochastic local search algorithms for graph set T-colouring and frequency assignment

The graph set T-colouring problem (GSTCP) generalises the classical graph colouring problem; it asks for the assignment of sets of integers to the vertices of a graph such that constraints on the separation of any two numbers assigned to a single vertex or to adjacent vertices are satisfied and some objective function is optimised. Among the objective functions of interest is the minimisation of the difference between the largest and the smallest integers used (the span). In this article, we present an experimental study of local search algorithms for solving general and large size instances of the GSTCP. We compare the performance of previously known as well as new algorithms covering both simple construction heuristics and elaborated stochastic local search algorithms. We investigate systematically different models and search strategies in the algorithms and determine the best choices for different types of instance. The study is an example of design of effective local search for constraint optimisation problems.