Boosting constraint satisfaction using decision trees

Constraint satisfaction is becoming the paradigm of choice for solving many real-world problems. To date, most approaches to constraint satisfaction have focused on solving a problem using some form of backtrack search. Furthermore, the typical view is that a constraint satisfaction problem will be solved only once. However, in many real-world contexts, problems are solved repeatedly over time. Also such problems often exhibit some structure. This motivates the application of some form of learning to improve the performance of search from previously discovered solutions. In this paper we present an approach that uses knowledge about known solutions to a problem to improve search. The approach we present is based on a combination of decision tree learning and constraint satisfaction. We demonstrate that significant improvements, almost an order-of-magnitude, in search effort can be achieved using this hybrid approach over traditional search. We also show that the space complexity using this approach is almost negligible. This work is of interest in domains such as product configuration, and interactive constraint solving in general where the system takes the initiative by asking questions.