Abstract
Constraint Satisfaction Problems (CSPs) involve assigning values to a finite set of variables from their finite domains such that a finite set of constraints is satisfied. Graph coloring, Scheduling and Time-table design are some of the commonly occurring CSPs. All general solution procedures for CSPs are based upon a combinatorial enumeration of variable bindings, with the addition of clever devices to reduce the number of nodes explored in the corresponding search tree. CSPs, however, are NP-hard, and general-purpose search algorithms are slow. This research explores the application of problem decomposition to construct faster CSP solvers Previous applications of Problem Decomposition to CSPs have been based upon the representation of a CSP as a Constraint Graph, where nodes represent variables, and arcs represent constraints. A tree-shaped constraint graph, after some preprocessing on the nodes, can be solved without backtrack (Freuder, 82). Researchers have proposed different methods for reducing a constraint graph into a tree of node-clusters, with the cost of solution dependent on the size of the largest such cluster. Tree-clustering based methods of decomposition fail on CSPs with global constraints, where any cluster including the global constraint has to include all the problem's variables. This thesis proposes reducing redundant constraint-checks as an alternative motivation for problem decomposition in CSPs. The decomposition algorithms developed here are applicable to CSPs unrestricted on constraint arity. There are three major components to this research. The first is the development of a framework, named bottom-up solution, for solving a CSP through its decomposition. It is aimed at handling decompositions that do not completely partition a problem into independent components. The framework allows for the efficient handling of problem components dependent upon other subproblems. The bottom-up solution framework has been implemented on top of the basic Backtrack and Forward-Check search algorithms. The thesis then introduces two problem decomposition algorithms aimed directly at reducing redundant constraint checks. The main insight here is that redundant constraint tests are caused by artificial dependencies of constraints on non-argument variables, set up by the serial nature of combinatorial enumeration used as the basis for search algorithms. The decomposition algorithms seek to reduce artificial dependencies in a problem, and the resulting decompositions can be solved in the bottom-up solution framework. The third component of this thesis focuses on global and high-arity constraints. The complexity of a class of problems with a particular constraint topology is defined by the highest arity of its constraint set. This is reflected in the inability of search algorithms to take advantage of global constraints to reduce the size of the explored search space. This thesis proposes a procedure for the syntactic decomposition of a global constraint in a problem. This decomposition is used to define an abstract problem layer, and a new hierarchical problem which is equivalent to the original problem, and in which the global constraint is replaced with a set of smaller arity constraints. The problem decomposition techniques are evaluated on random problems and on some sample application domains. In general the decomposition is shown to be more beneficial for problems which, when solved in their original form, exhibit high artificial serial dependencies and produce bushier search trees. Global constraint decomposition is demonstrated on some sample application domains, and shown to significantly reduce search effort. Constraint satisfaction problems are difficult enough that there do not exist any reliable and effective general purpose problem solving heuristics and evaluation functions. It is therefore significant that the DOI decomposition algorithm proposed in this research is guaranteed never to make the problem harder to solve. The primary contribution of this research is in the form of new problem solving methods for general constraint satisfaction problems which significantly improve performance, particularly for harder problems. It also extends the current understanding of what makes constraint satisfaction problems difficult to solve and where search algorithms spend their effort. On the more general side, this thesis promotes a deeper understanding of the application and benefits of problem decomposition as a problem solving strategy.