Preprocessing versus search processing for constraint satisfaction problems
Loading...
Files
Published Version
Date
2016-11
Authors
Wallace, Richard J.
Journal Title
Journal ISSN
Volume Title
Publisher
Sun SITE Central Europe (CEUR) / RWTH Aachen University
Published Version
Abstract
A perennial problem in hybrid backtrack CSP search is how much local consistency processing should be done to achieve the best efficiency. This can be divided into two separate questions: (1) how much work should be done before the actual search begins, i.e. during preprocessing? and (2) how much of the same processing should be interleaved with search? At present there are two leading approaches to establishing stronger consistencies than the basic arc consistency maintenance that is done in most solvers. On the one hand there are various kinds singleton arc consistency that can be used; on the other there are several variants of restricted path consistency. To date these have not been compared directly. The present work attempts to do this for a variety of problems, and in so doing, it also provides an empirical evaluation of the preprocessing versus search processing issue. Comparisons are made using the domain/degree and domain/weighted degree variable ordering heuristics. In general, it appears that preprocessing with higher levels of consistency followed by hybrid-AC processing (i.e. MAC) gives the best results, especially when the weighted degree heuristic is used. For problems with n-ary constraints, this difference seems to be even more pronounced. In some cases, higher levels of consistency maintenance established during preprocessing leads to performance gains over MAC of several orders of magnitude.
Description
Keywords
Preprocessing , Search processing , Weighted degree
Citation
Wallace, R. J. (2016) ‘Preprocessing versus search processing for constraint satisfaction problems’ (from the Proceedings of the 23rd RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion 2016 (RCRA 2016), Genova, Italy, 28 November 2016), CEUR Workshop Proceedings, 1745, pp. 89-103.