A new iterated local search algorithm for the cyclic bandwidth problem

摘要

The Cyclic Bandwidth Problem is an important graph labeling problem with numerous applications. This work aims to advance the state-of-the-art of practically solving this computationally challenging problem. We present an effective heuristic algorithm based on the general iterated local search framework and integrating dedicated search components. Specifically, the algorithm relies on a simple, yet powerful local optimization procedure reinforced by two complementary perturbation strategies. The local optimization procedure discovers high-quality solutions in a particular search zone while the perturbation strategies help the search to escape local optimum traps and explore unvisited areas. We present intensive computational results on 113 benchmark instances from 8 different families, and show performances that are never achieved by current best algorithms in the literature.