An Iterated Three-Phase Search Approach for Solving the Cyclic Bandwidth Problem

International audienceThe cyclic bandwidth problem (CBP) was initially introduced in the context of designing ring interconnection networks and has a number of other relevant applications, such as the design of computer networks and minimization of wire lengths in VLSI layout. However, the problem is computationally challenging since it belongs to the class of NP-hard problems. Existing studies on the CBP mainly focus on theoretical issues, and there are still very few practical methods devoted to this important problem. This paper fills the gap by introducing an iterated three-phase search approach for solving the CBP effectively. The proposed algorithm relies on three complementary search components to ensure a suitable balance of search intensification and diversification, guided by an enriched evaluation function. Computational assessments on a test-suite of 113 popular benchmark instances in the literature demonstrate the effectiveness of the proposed algorithm. In particular, it improves on 19 best-known computational results of the current best-performing algorithm for the problem and discovers 12 new record results (updated upper bounds). The key components of the proposed algorithm are investigated to shed light on their influences over the performance of the algorithm