Constraint propagation as an embedded filtering technique for solving constraint satisfaction problems

The use of constraint propagation as a pre-processing technique to guarantee backtrack-free search for constraint satisfaction problems is not practical for most real world problems because it requires a time-consuming high-order consistency algorithm (FREUDER 82). The theme of this dissertation is to investigate how the constraint propagation technique can be used as a embedded filtering technique so that a low-order consistency algorithm can be used to achieve the pruning power of higher consistency algorithms. The effectiveness of constraint propagation as an embedded filtering technique in solving constraint satisfaction problems is studied by applying it to different types of constraint satisfaction problems. The graph coloring problem and zebra problem are used as examples of discrete constraint satisfaction problems, while the job shop scheduling is used as an example of temporal constraint satisfaction problems. By experimenting with these different types of constraint satisfaction problems, it was found that if constraint propagation, achieved by arc consistency, is used as an embedded filtering technique in conjunction with some simple search algorithms, the problem solving power of these algorithms for solving constraint satisfaction problems can be increased significantly. We further showed that constraint propagation as an embedded filtering technique is effective in finding optimal solutions for an optimization problem such as the object allocation problem for distributed databases. We also showed that computation time can be reduced by adding heuristic constraints to the problem domain without any practical loss in optimality.