Tabu search for the cyclic bandwidth problem

International audience

<p>The Cyclic Bandwidth (CB) problem for graphs consists in labeling the vertices of a guest graph G by distinct vertices of a host cycle Cn (both of order n) in such a way that the maximum distance in the cycle between adjacent vertices in G is minimized. To the best of our knowledge, this is the first research work investigating the use of metaheuristic algorithms for solving this challenging combinatorial optimization problem in the case of general graphs.</p><p>In this paper a new carefully devised Tabu Search   algorithm, called TScb, for finding near-optimal solutions for the CB problem is proposed. Different possibilities for its key components and input parameter values were carefully analyzed and tuned, in order to find the combination of them offering the best quality solutions to the problem at a reasonable computational effort.</p><p>Extensive experimentation was carried out, using 113 standard benchmark instances, for assessing its performance with respect to a Simulated Annealing (SAcb) implementation. The experimental results show that there exists a statistically significant performance amelioration achieved by TScb with respect toSAcb in 90 out of 113 graphs (79.646%). It was also found that our TScb algorithm attains 56 optimal solutions and establishes new better upper bounds for the other 57 instances. Furthermore, these competitive results were obtained expending reasonable computational times.</p>