Exploiting subproblem dominance in constraint programming

Abstract

Many search problems contain large amounts of redundancy in the search. In this paper we examine how to automatically exploit subproblem dominance, which arises when different partial assignments lead to subproblems that dominate (or are dominated by) other subproblems. Subproblem dominance is exploited by caching subproblems that have already been explored by the search, using keys that characterise the subproblems, and failing the search when the current subproblem is dominated by a subproblem already in the cache. In this paper we show how we can automatically and efficiently define keys for arbitrary constraint problems using constraint projection. We show how, for search problems where ..