Synthesis of Abstraction Hierarchies for Constraint Satisfaction by Clustering Approximately Equivalent Objects

Abstract

Ion 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 benefits 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 objects appearing in a problem into classes that contain approximately equivalent objects. It presents a program synthesis algorithm for automatically building abstraction spaces and hierarchic problem solvers that exploit approximate equivalence of objects. 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.