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

10 Citations (Scopus)

Abstract

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 (http://www.csplib.org/), 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
PublisherSpringer
Pages229-243
Number of pages15
ISBN (Print)3540202021
DOIs
Publication statusPublished - 1 Dec 2003
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2003 - Kinsale, Ireland
Duration: 29 Sep 20033 Oct 2003
Conference number: 9th
https://link-springer-com.ezproxy.lib.monash.edu.au/book/10.1007/b13743 (Proceedings)

Publication series

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

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2003
Abbreviated titleCP 2003
CountryIreland
CityKinsale
Period29/09/033/10/03
Internet address

Cite this