Evaluation of solving methods for conditional constraint satisfaction problem

Conditional constraint satisfaction problems (CondCSPs) adequately capture problem change at solving time by conditionally identifying those variables and constraints that are relevant to final solutions. Real-world tasks with dynamic behavior, such as configuration, design, diagnosis, planning, and hardware test generation, have been modeled more naturally with CondCSPs. Such interest has been matched by the development of more effective algorithms that depart from classical backtracking and incorporate local consistency checking. Although performance results have been reported for these specialized algorithms, the experimental analysis has been conducted separately, using different test suites, and little is known about the algorithms’ relative performance. In this abstract we present a CondCSP solver that implements direct and reformulation-based algorithms, each of which using forward checking and maintaining local consistency. In our experimental analysis we have considered randomly generated CondCSPs of diverse topologies in terms of problem density and satisfiability of the standard and conditional problem components. Execution time results show that there is not one winner but that reformulation solving in conjunction with forward checking performs better on problems with larger solution sets, while direct solving in conjunction with maintaining arc consistency is always preferred over direct solving using forward checking. A conditional constraint satisfaction problem (CondCSP) extends the standard CSP with a condition-based component that models problem change by allowing for “on-the-fly” selection of subsets of variables that participate in problem solutions. The formalism, introduced by (Mittal & Falkenhainer 1990) under the name of dynamic CSP, has been renamed to conditional CSP (Sabin & Freuder 1998) to qualify the control component that models dynamic changes of the solution space with predefined conditions. The original application domain in (Mittal & Falkenhainer 1990) is product configuration, in which a changing rather than fixed number of components are part of final solutions. Selecting optional components to assemble configuration variants is naturally represented in CondCSP with condition-based constraints. More recently, conditional constraint satisfaction has been adapted to the planning domain (Do & Kambhampati 2000; Copyright c © 2006, American Association for Artificial Intelligence (www.aaai.org). All rights reserved. Ambite et al. 2005; Miguel, Jarvis, & Shen 2000) and hardware test generation (Geller & Veksler 2005). Each application domain has produced specialized algorithms for solving CondCSPs. Following the example of standard CSP solving, local consistency methods have been incorporated in CondCSP solvers and improved performance results have been reported. Although this solving approach has been observed across application domains, little is known about the algorithms’ relative performance. Moreover, in striking contrast with the state-of-the-art of standard CSP solving, CondCSP class lacks systematic findings with regard to how algorithm efficiency correlates with problem topology, such as density, satisfiability, and conditionality. This challenge is compounded by an almost inexistent library of CondCSP benchmark problems. To address these challenges, we have developed a CondCSP solver that includes two representative algorithms that have initially been proposed, implemetned, and evaluated separately. One algorithm has direct solving methods that adapt standard consistency checking, such as forward checking and maintaining arc consistency, to the special constraints that enforce conditionality in a CondCSP (Sabin 2003; Sabin, Freuder, & Wallace 2003). The other algorithm reformulates the original problem into intermediate CondCSPs with incrementally lesser conditionality as they are ultimately transformed into standard CSPs. Standard consistency checking is interleaved with problem reformulation to eliminate inconsistent subproblems and solve the resulting standard CSPs (Gelle 1998; Gelle & Faltings 2003). To overcome the lack of publicly known benchmark problems, we have used random CondCSPs and designed test suites for both direct and reformulation solving algorithms. The first complete description of CondCSP backtrack search (Gelle 1998) solves a partially reformulated CondCSP, in which activity constraints of exclusion are rewritten as compatibility constraints. (Sabin 2003) proposed CondCSP analogs to CSP backtrack (CondBt), forward checking (CondFc), and maintaining arc consistency (CondMac) search algorithms. CondMac interleaves backtrack search with maintaining arc consistency (Mac) adapted to propagate consistency checking on both compatibility and activity constraints in the original CondCSP. Experimental evaluation on random CondCSPs (Wallace 1996) shows up to two orders of magnitude of efficiency improvement over plain