Short and Long Supports for Constraint Propagation
Source: AI Access Foundation
Special-purpose constraint propagation algorithms frequently make implicit use of short supports - by examining a subset of the variables, they can infer support (a justification that a variable-value pair may still form part of an assignment that satisfies the constraint) for all other variables and values and save substantial work - but short supports have not been studied in their own right. The two main contributions of this paper are the identification of short supports as important for constraint propagation and the introduction of HaggisGAC, an efficient and effective general purpose propagation algorithm for exploiting short supports. Given the complexity of HaggisGAC, the authors present it as an optimized version of a simpler algorithm ShortGAC.