Abstract
Abstraction techniques are important for solving constraint satisfaction problems with global constraints and low solution density. In the presence of global constraints, backtracking search is unable to prune partial solutions. It therefore operates like pure generate-and-test. Abstraction improves on generate-and-test by enabling entire subsets of the solution space to be pruned early in a backtracking search process. Unfortunately, a suitable abstraction space may not be included in the problem description provided to a problem solving system. The benets of abstraction will not be available unless the system can automatically construct an abstraction space. This paper describes how abstraction spaces can be generated by clustering the ob jects appearing in a problem into classes that contain approximately equivalent ob jects. It presents a program synthesis algorithm for automatically building abstraction spaces and hierarchic problem solvers that exploit approximate equivalence of ob jects. The fully implemented synthesis algorithm operates by analyzing declarative descriptions of classes of constraint satisfaction problems. The paper presents data from experimental tests of the synthesis algorithm and the resulting problem solvers on the NP-hard Partition and Minimum Flow Cut problems.