(PDF)
Xinguang Chen.
A theoretical comparison of selected CSP solving and modeling techniques.
PhD thesis,
University of Alberta, Department of Computing Science,
2000.
A constraint programming approach to problem solving usually goes through two phases: modeling the problem as a CSP and then solving the CSP. It has been recently recognized that both choosing the right solving algorithm and the right problem model are crucial for efficient problem solving. In the past, much of the research activities in the constraint community has been concentrated on developing various improving techniques to the naive backtracking algorithm (BT). These techniques can be classified as \emph{look-ahead} schemes and \emph{look back} schemes. Unfortunately, it has been observed by different researchers that the enhancement of look-ahead techniques is sometimes counterproductive to the effects of look-back techniques. In this thesis, we show theoretically that the effect of the backjumping will be diminished as a backtracking algorithm is equipped with an appropriate variable ordering heuristic or a certain level of local consistency enforcement. We propose a new algorithm, named \emph{GAC-CBJ}. In contrast to Bessi\`ere and R\'egin's conclusion (1996) that CBJ is useless to an algorithm maintaining arc consistency (MAC or GAC), our experiments in several problem domains show that the use of CBJ can provide significant improvements on the hard instances.
There also exists a variety of techniques to improve the quality of a CSP formulation. The dual graph transformation and hidden variable transformation are two important modeling techniques that translate a general CSP to an equivalent binary CSP. However, little has been known about how these transformations will influence the effectiveness of the CSP solving techniques. Some preliminary results include: Stergiou and Walsh (1999) study the the effectiveness of consistency techniques under the above transformations, and Bacchus and van Beek (1998) study how the two transformations will affect the performance of the forward checking algorithm (FC). In this thesis, we present a comprehensive theoretical comparison of these two transformations for BT, FC and MAC (GAC). Among other results, we show that FC applied on the hidden problem is only bounded worse than FC applied on the dual problem, and GAC applied on the original problem visits exactly the same nodes as MAC applied on the hidden problem.