A lazy divide & conquer approach to constraint solving

Abstract

Divide and conquer strategy enables a problem to be divided into subproblems, which are solved independently and later combined to form the solutions of the original problem. In solving constraint satisfaction problems, however, divide and conquer technique has not been shown to be effective. Because, it is not possible to cleanly divide a problem into independent subproblems in the presence of constraints that involve variables belonging to different subproblems. Consequently, solutions of one subproblem may prune some solutions of another subproblem, making those solutions of the latter subproblem redundant. In this paper, we propose a divide and conquer approach to constraint solving in a lazy evaluation framework. In this framework, a subproblem is solved on demand, which eliminates redundant consistency checks. Moreover, once solved, the solutions of a subproblem can be reused in the satisfaction of various global constraints connecting this subproblem with others, thus reducing the search space. We also demonstrate the effectiveness of our algorithm in solving a practical problem: finding all instances of a user-defined pattern in stock market price charts.