×

Assumption-based pruning in conditional CSP. (English) Zbl 1153.68458

van Beek, Peter (ed.), Principles and practice of constraint programming – CP 2005. 11th international conference, CP 2005, Sitges, Spain, October 1–5, 2005. Proceedings. Berlin: Springer (ISBN 978-3-540-29238-8/pbk). Lecture Notes in Computer Science 3709, 241-255 (2005).
Summary: A conditional constraint satisfaction problem (CCSP) is a variant of the standard constraint satisfaction problem (CSP). CCSPs model problems where some of the variables and constraints may be conditionally inactive such that they do not participate in a solution. Recently, algorithms were introduced that use MAC at their core to solve CCSP. We extend MAC with a simple assumption-based reasoning. The resulting algorithm, Activity MAC (AMAC), is able to achieve significantly better pruning than existing methods. AMAC is shown to be more than two orders of magnitude more efficient than CondMAC on certain problem classes. Our algorithm is most naturally expressed using a variant of the CCSP representation that we refer to as Activity CSP (ACSP). ACSP introduces activity variables which explicitly control the presence of other variables in the solution. Common aspects of CCSP, such as activity clustering and disjunction, are easily captured by ACSP and contribute to improved pruning by AMAC.
For the entire collection see [Zbl 1140.68002].

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

Software:

CCSP
PDFBibTeX XMLCite
Full Text: DOI