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

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
Event2nd International Conference on Principles and Practice of Constraint Programming, CP 1996 - Cambridge, United States
Duration: 19 Aug 199622 Aug 1996

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

Conference2nd International Conference on Principles and Practice of Constraint Programming, CP 1996
CountryUnited States
CityCambridge
Period19/08/9622/08/96

Cite this

Sakkout, H. E., Wallace, M. G., & Richards, E. B. (1996). An instance of adaptive constraint propagation. In Principles and Practice of Constraint Programming ― CP 1996 - 2nd International Conference, CP 1996, Proceedings (pp. 164-178). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1118). Springer-Verlag London Ltd.. https://doi.org/10.1007/3-540-61551-2_73
Sakkout, Hani El ; Wallace, Mark G. ; Richards, E. Barry. / An instance of adaptive constraint propagation. Principles and Practice of Constraint Programming ― CP 1996 - 2nd International Conference, CP 1996, Proceedings. Springer-Verlag London Ltd., 1996. pp. 164-178 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{83a29523202041b79e2c9e86ebddc35f,
title = "An instance of adaptive constraint propagation",
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.",
author = "Sakkout, {Hani El} and Wallace, {Mark G.} and Richards, {E. Barry}",
year = "1996",
month = "1",
day = "1",
doi = "10.1007/3-540-61551-2_73",
language = "English",
isbn = "3540615512",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag London Ltd.",
pages = "164--178",
booktitle = "Principles and Practice of Constraint Programming ― CP 1996 - 2nd International Conference, CP 1996, Proceedings",
address = "Germany",

}

Sakkout, HE, Wallace, MG & Richards, EB 1996, An instance of adaptive constraint propagation. in Principles and Practice of Constraint Programming ― CP 1996 - 2nd International Conference, CP 1996, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1118, Springer-Verlag London Ltd., pp. 164-178, 2nd International Conference on Principles and Practice of Constraint Programming, CP 1996, Cambridge, United States, 19/08/96. https://doi.org/10.1007/3-540-61551-2_73

An instance of adaptive constraint propagation. / Sakkout, Hani El; Wallace, Mark G.; Richards, E. Barry.

Principles and Practice of Constraint Programming ― CP 1996 - 2nd International Conference, CP 1996, Proceedings. Springer-Verlag London Ltd., 1996. p. 164-178 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1118).

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

TY - GEN

T1 - An instance of adaptive constraint propagation

AU - Sakkout, Hani El

AU - Wallace, Mark G.

AU - Richards, E. Barry

PY - 1996/1/1

Y1 - 1996/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84957865365&partnerID=8YFLogxK

U2 - 10.1007/3-540-61551-2_73

DO - 10.1007/3-540-61551-2_73

M3 - Conference Paper

SN - 3540615512

SN - 9783540615514

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 164

EP - 178

BT - Principles and Practice of Constraint Programming ― CP 1996 - 2nd International Conference, CP 1996, Proceedings

PB - Springer-Verlag London Ltd.

ER -

Sakkout HE, Wallace MG, Richards EB. An instance of adaptive constraint propagation. In Principles and Practice of Constraint Programming ― CP 1996 - 2nd International Conference, CP 1996, Proceedings. Springer-Verlag London Ltd. 1996. p. 164-178. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-61551-2_73