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.
|Title of host publication
|Principles and Practice of Constraint Programming ― CP 1996 - 2nd International Conference, CP 1996, Proceedings
|Springer-Verlag London Ltd.
|Number of pages
|Published - 1 Jan 1996
|International Conference on Principles and Practice of Constraint Programming 1996 - Cambridge, United States of America
Duration: 19 Aug 1996 → 22 Aug 1996
Conference number: 2nd
|Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
|International Conference on Principles and Practice of Constraint Programming 1996
|United States of America
|19/08/96 → 22/08/96