The Compact-Table (CT) algorithm is the current state-of-the-art algorithm for enforcing Generalized Arc Consistency (GAC) on table constraints during search. Recently, algorithms for enforcing Pair-wise Consistency (PWC), which is strictly stronger than GAC, were shown to be advantageous for solving difficult problems. However, PWC algorithms can be costly in terms of CPU time and memory consumption. As a result, their overhead may offset the savings of search-space reduction. In this paper, we introduce PW-CT, an algorithm that modifies CT to enforce full PWC. We show that PW-CT avoids the high memory requirements of prior PWC algorithms and significantly reduces the time required to enforce PWC.
展开▼
