Coloring by Tabu branch and bound

We give an adaptive depth procedure for coloring a graph that combines elements of tabu search and branch and bound. The resulting tabu branch and bound method can execute searches of varying degrees of exhaustiveness at different stages and in different regions of the search space, ranging from pure heuristic search to pure tree search at the extremes. The goal is generally to find near optimal colorings efficiently, but with the ability to obtain optimal colorings if desired. We introduce new theoretical results concerning depth and width of local optima that motivate our approach, and employ a concept of color conditioned dependency to permit shrinking of the graph at appropriate stages. We also employ an associated notion of node danger to select a node to be colored and to determine the color assigned. Computational experiments show our method performs effectively for a variety of problem types, including those taken from real world applications, and notably in graphs that are not excessively dense (as is typical in practice). In general, our approach is significantly better than branch and bound coloring methods which are considered to be state-of-the-art, yet maintains a structure that likewise provides a theoretical ability to assure optimality (controlled by a choice parameter). We demonstrate the effectiveness of this approach by comparing the tabu branch and bound method in both heuristic and exact mode with an efficient implementation of the DSATUR branch and bound algorithm. We find that the tabu branch and bound approach is able to solve problem instances in 1/3 to 1/2400 of the time as DSATUR. Also, when run in a mode to identify near optimal colorings quickly, the tabu branch and bound method terminated with optimal solutions for 15 of 28 graphs taken from the DIMACS Challenge Benchmark (specially constructed to be difficult) for which optimal solutions are known. Additionally, by finding colorings of the same cardinality as lower bounds the method also identified, the method was able to verify the optimality of its solution in 12 of these 15 problems. 1991 Mathematics Subject Classification. Primary 90C35, 68R10; Secondary 05C85. This research was supported in part by AFOSR/ONR Contracts #F49620-90-C and #F49620-92-J-DEF. This paper is in final form and no version of it will be submitted for publication elsewhere. c ©0000 American Mathematical Society 0000-0000/00 $1.00 + $.25 per page