ALCOMFT-TR-02-109

Meinolf Sellmann and Warwick Harvey
Heuristic Constraint Propagation (Using Local Search for Incomplete Pruning and Domain Filtering of Redundant Constraints for the Social Golfer Problem)
Paderborn. Work packages 3 and 4. May 2002.

Abstract: For NP-hard constraint satisfaction problems the existence of a feasible solution cannot be decided efficiently. Applying a tree search often results in the exploration of parts of the search space that do not contain feasible solutions at all. Redundant constraints can help to detect inconsistencies of partial assignments higher up in the search tree. Using the social golfer problem as an example we show how redundant constraints that are potentially NP-hard themselves can be propagated incompletely using local search heuristics.

Postscript file: ALCOMFT-TR-02-109.ps.gz (99 kb).