Effective Learning-Based Hybrid Search for Bandwidth Coloring

The bandwidth coloring problem (BCP) and the bandwidth multicoloring problem (BMCP) are two important generalizations of the classical vertex coloring problem. This paper presents learning-based hybrid search (LHS) for BCP and BMCP. LHS combines a construction phase to progressively build feasible (partial) colorings and a local search phase to reestablish feasibility when an illegal partial solution is encountered. The construction phase relies on a learning-based guiding function to determine the next vertex for color assignment while the local search phase uses a tabu search repair procedure to resolve coloring conflicts. Experiments on a set of 33 well-known benchmarks for BCP and a set of 33 benchmarks for BMCP demonstrate that the proposed LHS approach can match the best known solution for most benchmarks. In particular, LHS finds an improved best solution for 14 instances.