Tabu search with feasible and infeasible searches for equitable coloring

摘要

The equitable coloring problem is a variant of the classical graph coloring problem that arises from a number of real-life applications where the cardinality of color classes must be balanced. In this paper, we present a highly effective hybrid tabu search method for the problem. Based on three complementary neighborhoods, the algorithm alternates between a feasible local search phase where the search focuses on the most relevant feasible solutions and an infeasible local search phase where a controlled exploration of infeasible solutions is allowed by relaxing the equity constraint. A novel cyclic exchange neighborhood is also proposed in order to enhance the search ability of the hybrid tabu search algorithm. Experiments on a set of 73 benchmark instances in the literature indicate that the proposed algorithm is able to find improved best solutions for 15 instances (new upper bounds) and matches the best-known solutions for 57 instances. Additional analyses show the interest of the cyclic exchange neighborhood and the hybrid scheme combining both feasible and infeasible local searches.