Conference Proceedings

Automatically Exploiting Subproblem Equivalence in Constraint Programming

Geoffrey Chu, Maria Garcia de la Banda, Peter J Stuckey, A Lodi (ed.), M Milano (ed.), P Toth (ed.)

Lecture Notes in Computer Science: International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems 7th International Conference 2010 | SPRINGER-VERLAG BERLIN | Published : 2010

Abstract

Many search problems contain large amounts of redundancy in the search. In this paper we examine how to automatically exploit remaining subproblem equivalence, which arises when two different search paths lead to identical remaining subproblems, that is the problem left on the remaining unfixed variables. Subproblem equivalence is exploited by caching descriptions, or keys, that define the subproblems visited, and failing the search when the key for the current subproblem already exists in the cache. In this paper we show how to automatically and efficiently define keys for arbitrary constraint problems. We show how a constraint programming solver with this capability can solve search proble..

View full abstract

Grants

Funding Acknowledgements

NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council.