Dynamic variable elimination during propagation solving

Christian Schulte, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

Constraint propagation solvers interleave propagation (removing impossible values from variables domains) with search. Propagation is performed by executing propagators (removing values) implementing constraints (defining impossible values). In order to specify constraint problems with a propagation solver often many new intermediate variables need to be introduced. Each variable plays a role in calculating the value of some expression. But as search proceeds not all of these expressions will be of interest any longer, but the propagators implementing them will remain active. In this paper we show how we can analyse the propagation graph of the solver in linear time to determine intermediate variables that can be removed without effecting the result. Experiments show that applying this analysis can reduce the space and time requirements for constraint propagation on example problems.

Original languageEnglish
Title of host publicationPPDP'08 - Proceedings of the 10th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming
Pages247-257
Number of pages11
DOIs
Publication statusPublished - 17 Dec 2008
Externally publishedYes
EventPPDP 2008: 10th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming - Valencia, Spain
Duration: 15 Jul 200817 Jul 2008

Publication series

NamePPDP'08 - Proceedings of the 10th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming

Conference

ConferencePPDP 2008: 10th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming
CountrySpain
CityValencia
Period15/07/0817/07/08

Keywords

  • Analysis
  • Constraint (logic) programming
  • Constraint propagation
  • Redundancy

Cite this