https://dx.doi.org/10.1007/978-3-540-45193-8_44">
 

Abstract

A conditional constraint satisfaction problem (CCSP) extends a standard constraint satisfaction problem (CPS) with a condition-based component that controls what variables participate in problem solutions. CCSPs adequately represent configuration and design problems in which selected subsets of variables, rather than the entire variable set, are relevant to final solutions. The only algorithm that is available for CCSP and operates directly on the original, unreformulated CCSP statement has been basic backtrack search. Reformulating CCSPs into standard CSPs has been proposed in order to bring the full arsenal of CSP algorithms to bear. One reformulation approach adds null values to variable domains and transforms CCSP constraints into CSP constraints. However, a complete null-based reformulation of CCSPs has not been available. In this paper we provide more advanced algorithms for CCSP and a full null-based reformulation into standard CSP. Thorough testing reveals that the advanced algorithms perform up to two orders of magnitude better than plain backtracking, but that realizing practical advantages from reformulation is problematic. The advanced algorithms extend forward checking and maintaining arc consistency to CCSPs. The null-based reformulation improves on the preliminary findings in [1] by removing the limitation on multiple activation, and by localizing changes. It identifies and addresses a difficulty presented by activity cycles.

Publication Date

1-1-2003

Journal Title

International Conference on Principles and Practice of Constraint Programming

Publisher

Springer

Digital Object Identifier (DOI)

https://dx.doi.org/10.1007/978-3-540-45193-8_44

Document Type

Article

Rights

© Springer-Verlag Berlin Heidelberg 2003

Comments

This is an Accepted Manuscript. The final publication is available at Springer via https://dx.doi.org/10.1007/978-3-540-45193-8_44

Download

Share

COinS