Generating Special-Purpose Stateless Propagators for Arbitrary Constraints

Generating Special-Purpose Stateless Propagators for Arbitrary Constraints,10.1007/978-3-642-15396-9_19,Ian P. Gent,Christopher Jefferson,Ian Miguel,P

Generating Special-Purpose Stateless Propagators for Arbitrary Constraints  
BibTex | RIS | RefWorks Download
Given an arbitrary constraint c on n variables with domain size d, we show how to generate a custom propagator that establishes GAC in time O(nd) by precomputing the propagation that would be performed on every reachable subdomain of scope(c). Our propagators are stateless: they store no state between calls, and so incur no over- head in storing and backtracking state during search. The preprocessing step can take exponential time and the custom propagator is potentially exponential in size. However, for small constraints used repeatedly, in one problem or many, this technique can provide substantial practical gains. Our experimental results show that, compared with optimised im- plementations of the table constraint, this technique can lead to an order of magnitude speedup, while doing identical search on realistic problems. The technique can also be many times faster than a decomposition into primitive constraints in the Minion solver. Propagation is so fast that, for constraints available in our solver, the generated propagator compares well with a human-optimised propagator for the same constraint.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.