Propagation redundancy in redundant modelling

Chiu Wo Choi, Jimmy Ho Man Lee, Peter J. Stuckey

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

13 Citations (Scopus)


Combining mutually redundant models with channelling constraints increases constraint propagation. However, the extra computation efforts of the additional variables and constraints may outweigh the gain of reduction in search space. In fact, many of the constraints in redundant modelling are not only logically redundant but also propagation redundant and hence cannot further reduce search space. We give general theorems for proving propagation redundancy of one constraint with respect to channelling constraints and constraints in the other model. We define a broad form of channelling constraints that are covered by our approach. We illustrate, using problems from CSPLib (, how detecting and removing propagation redundant constraints can significantly speed up solving behaviour.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming – CP 2003
Subtitle of host publication9th International Conference, CP 2003 Kinsale, Ireland, September 29 – October 3, 2003 Proceedings
EditorsFrancesca Rossi
Place of PublicationBerlin Germany
Number of pages15
ISBN (Print)3540202021
Publication statusPublished - 1 Dec 2003
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2003 - Kinsale, Ireland
Duration: 29 Sept 20033 Oct 2003
Conference number: 9th (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


ConferenceInternational Conference on Principles and Practice of Constraint Programming 2003
Abbreviated titleCP 2003
Internet address

Cite this