Adaptive feasible and infeasible tabu search for weighted vertex coloring

The Weighted Vertex Coloring Problem of a vertex weighted graph is to partition the vertex set into k disjoint independent sets such that the sum of the costs of these sets is minimized, where the cost of each set is given by the maximum weight of a vertex (representative) in that set. To solve this NP-hard problem, we present the adaptive feasible and infeasible search algorithm (AFISA) that relies on a mixed search strategy exploring both feasible and infeasible solutions. From an initial feasible solution, AFISA seeks improved solutions by oscillating between feasible and infeasible regions. To prevent the search from going too far from feasibility boundaries, we introduce a control mechanism that adaptively makes the algorithm to go back and forth between feasible and infeasible solutions. To explore the search space, we use a tabu search optimization procedure to ensure an intensified exploitation of candidate solutions and an adaptive perturbation strategy to escape local optimum traps. We show extensive experimental results on 161 benchmark instances and present new upper bounds that are useful for future studies. We assess the benefit of the key features of the proposed approach. This work demonstrates that examining both feasible and infeasible solutions during the search is a highly effective search strategy for the considered coloring problem and could beneficially be applied to other constrained problems as well