Extending Simple Tabular Reduction with Short Supports

Abstract

Constraint propagation is one of the key techniques in constraint programming, and a large body of work has built up around it. 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 still forms part of a solution to the constraint) for all other variables and values and save substantial work. Recently short supports have been used in general purpose propagators, and (when the constraint is amenable to short supports) speed ups of more than three orders of magnitude have been demonstrated. In this paper we present ShortSTR2, a development of the Simple Tabular Reduction algorithm STR2+. We show that ShortSTR2 is complementary to the existing algorithms ShortGAC and HaggisGAC that exploit short supports, while being much simpler. When a constraint is amenable to short supports, the short support set can be exponentially smaller than the full-length support set. Therefore ShortSTR2 can efficiently propagate many constraints that STR2+ cannot even load into memory. We also show that ShortSTR2 can be combined with a simple algorithm to identify short supports from full-length supports, to provide a superior drop-in replacement for STR2+.