Abstract
This dissertation presents several new algorithms and heuristics for constraint satisfaction problems, as well as an extensive and systematic empirical evaluation of these new techniques. The goal of the research is to develop algorithms which are effective on large and hard constraint satisfaction problems.

The dissertation presents several new combination algorithms. The BJ+DVO algorithm combines backjumping with a dynamic variable ordering heuristic that utilizes a forward checking style look-ahead. A new heuristic for selecting a value called Look-ahead Value Ordering (LVO) can be combined with BJ+DVO to yield BJ+DVO+LVO. A new learning, or constraint recording, technique called jumpback learning is described. Jump-back learning is particularly eective because it takes advantage of eort that has already been expended by BJ+DVO. This type of learning can be combined with either BJ+DVO or BJ+DVO+LVO. Learning is shown to be helpful for solving optimization problems that are cast as a series of constraint problems with successively tighter cost-bound constraints. The constraints recorded by learning are used in subsequent attempts to nd a solution with a lower cost-bound.