An instance of adaptive constraint propagation

Hani El Sakkout, Mark G. Wallace, E. Barry Richards

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

13 Citations (Scopus)

Abstract

Constraint propagation algorithms vary in the strength of propagation they apply. This paper investigates a simple configuration for adaptive propagation-the process of varying the strength of propagation to reflect the dynamics of search. We focus on two propagation methods, Arc Consistency (AC) and Forward Checking (FC). AC-based algorithms apply a stronger form of propagation than FC-based algorithms; they invest greater computational effort to detect inconsistent values earlier. The relative payoff of maintaining AC during search as against FC may vary for different constraints and for different intermediate search states. We present a scheme for Adaptive Arc Propagation (AAP) that allows the flexible combination of the two methods. Meta-level reasoning and heuristics are used to dynamically distribute propagation effort between the two. One instance of AAP, Anti-Functional Reduction (AFR), is described in detail here. AFR achieves precisely the same propagation as a pure AC algorithm while significantly improving its average performance. The strategy is to gradually reduce the scope of AC propagation during backtrack search to exclude those arcs that may be subsequently handled as effectively by FC. Experimental results confirm the power of AFR and the validity of adaptive propagation in general.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming ― CP 1996 - 2nd International Conference, CP 1996, Proceedings
PublisherSpringer-Verlag London Ltd.
Pages164-178
Number of pages15
ISBN (Print)3540615512, 9783540615514
DOIs
Publication statusPublished - 1 Jan 1996
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 1996 - Cambridge, United States of America
Duration: 19 Aug 199622 Aug 1996
Conference number: 2nd

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1118
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 1996
Abbreviated titleCP 1996
CountryUnited States of America
CityCambridge
Period19/08/9622/08/96

Cite this