Abstraction via Approximate Symmetry

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. This paper describes how abstraction spaces can be characterized in terms of approximate symmetries of the original, concrete sear~h space. It defines two special types of approx1mate symmetry, called "range symmetry" and ~domain symmetry", which apply to function findmg problems. It also presents algorithms for automatically synthesizing hierarchic problem solvers b.ased on range or domain symmetry. The algonthms operate by analyzing declarative descriptions of classes of constraint satisfaction problems. Both algorithms have been fully implemented. This paper ~oncludes by present.ing data from experiments testmg the two synthes1s algorithms and the resulting problem solvers on NP-hard scheduling and partitioning problems.