6. Conclusions and Future Work

This paper studied a number of hypothesis, and in the process developed some algorithms. The algorithms for generating random problems proved to be harder to develop than expected. Original attempts involved attempts to use a heuristic rather than solving the bcsp for each new addition of a constraint, but that failed so the currerent solution (using AC-3 for strongly k-consistent generation and CBJ-Multi for 'totally random' problems) was developed.

The genetic algorithm development proved easier although a genetic algorithm which bested BM-CBJ2 was not found in producing this paper (a possible route to take for this is to make the chromosones more complex, rather than simply being the solution to the bcsp). BM-CBJ2 proved to be the best complete (i.e. works for all problems) algorithm as AC-3 cannot always find a solution, but for strongly k-consistent problems AC-3 was found to be the better choice for both the Zebra and the Sherlock problems. If determining k-consistency before solving the problem proves to be both possible and efficient a hybrid approach could prove to be ideal.

Further work on random problem generation is needed. It would, example, be useful to test the 'totally random' problems to determine if they are a good cross-section of real-world problems, or if they tend to cluster around a particular type of problem. In addition, it could be informative to determine how many of good random selection of problems are strongly k-consistent (and therefore solveable by AC-3).

Additional questions include the value of AC-3 preprocessing, which according to [Kumar92] is a common practise, and how BM-CBJ2 stacks up against both other backtracking algorithms ([Kondrak97]proves that BM-CBJ2 performs fewer constraint checks but whether is is faster depends on whether the reduction in constraint checking comes with a greater overhead cost). BM-CBJ2 also needs to be compared to other algorithms out there. In addition, this paper makes no attempt to compare variable instantiation orders for BM-CBJ2, and it is known that variable instantiation order can have a significant performance impact on backtracking and backjumping algorithms [Prosser93].