Stephen Beale
Computing Research Laboratory
Box 30001
New Mexico State University
Las Cruces, New Mexico 88003
sb@crl.nmsu.edu
In Proceedings AAAI-97, Providence, Rhode Island, 1997
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.