Using Branch-and-Bound with Constraint Satisfaction in Optimization Problems

Abstract

This work 1 integrates three related AI search techniques -- constraint satisfaction, branch-and-bound and solution synthesis -- and applies the result to constraint satisfaction problems for which optimal answers are required. This method has already been shown to work well in natural language semantic analysis (Beale, et al, 1996); here we extend the domain to optimizing graph coloring problems, which are abstractions of many common scheduling problems of interest. We demonstrate that the methods used here allow us to determine optimal answers to many types of problems without resorting to heuristic search, and, furthermore, can be combined with heuristic search methods for problems with excessive complexity. Introduction Optimization problems can be solved using a number of different techniques within the constraint satisfaction paradigm. Full lookahead (Haralick & Elliott, 1980) is popular because it is easy to implement and works on a large variety of problems. Tsang and Foster...