Generating Special-Purpose Stateless Propagators for Arbitrary Constraints

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

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 overhead 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 implementations 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.
Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming – CP 2010
Subtitle of host publication16th International Conference, CP 2010, St. Andrews, Scotland, September 6-10, 2010. Proceedings
EditorsDavid Cohen
PublisherSpringer
Pages206-220
Number of pages15
Volume6308
ISBN (Electronic)978-3-642-15396-9
ISBN (Print)978-3-642-15395-2
DOIs
Publication statusPublished - 2010
Event16th Annual International Conference on the Principles and Practice of Constraint Programming - St Andrews
Duration: 6 Sept 201010 Sept 2010

Publication series

NameLecture Notes in Computer Science

Conference

Conference16th Annual International Conference on the Principles and Practice of Constraint Programming
CitySt Andrews
Period6/09/1010/09/10

Fingerprint

Dive into the research topics of 'Generating Special-Purpose Stateless Propagators for Arbitrary Constraints'. Together they form a unique fingerprint.

Cite this