Midyear Summary

The end of the semester was spent implementing more complex look-ahead schemas with better backtracking algorithms. This included implementing FC (Forward-Checking), FC-CBJ, and AC-2001, an improved arc-consistency algorithm.

FC is one of the best look-ahead schemas for CSPs—it is strong when dealing with CSPs of low tightness (few constraints) as well as CSPs with high tightness and high density (many constraints, many variables). When FC is paired with CBJ, it can be a very powerful search tool. This is due to the fact that FC is good at eliminating future paths in the search space, while CBJ is good at reducing the number of backtracks that occur during the search, making for a faster search all-around.

FC is a difficult algorithm to implement at first—its methods are somewhat different from your typical backtracking algorithms. In FC, you are using the current assignment of variables to eliminate future assignments that are not consistent with the partial assignment. It is also important to ensure that FC backtracks properly when domain wipe-out occurs—that is, if a certain assignment of variables causes a future assignment of a variable to be inconsistent, the algorithm must backtrack and form a new partial assignment. In my opinion, the most difficult part of implementing FC is managing domain values. It is a little tricky combining FC and CBJ, but is a lot easier if both are implemented separately first.

Another method of look-ahead is MAC (Maintaining Arc-Consistency). MAC performs a look-ahead in which a form of AC is run on the uninstantiated variables of the CSP. However, MAC is much more expensive than FC and performs better on CSPs of low density and high tightness. However, when graphically comparing the performances of FC and MAC, it is apparent that MAC uses more resources for problems with very low and very high tightness. MAC tends to make more constraint checks during look-ahead that save on backtracking, but do not make it a more efficient algorithm than FC.

We explored many other topics as well, such as search orders in CSPs. Search order can refer to variable order or value order, and the order in which variables are instantiated or values are chosen can have a great impact on the speed of an algorithm. A few ordering heuristics include min-conflict, cruciality, and promise. We implemented many ordering heuristics in our CSP solvers in order to compare the performance of our algorithms on random instances using different variable orderings.

We also examined GAC (Generalized Arc-Consistency) and studied Regín’s algorithm for applying it to a CSP with an All different constraint applying to its variables. The algorithm requires that the CSP be represented as a bipartite graph consisting of variables and the set union of all domain values. Then, a maximal matching must be found such that no two edges share a vertex. A value can be removed from the domain if its edge is not part of the matching, if it is not a strongly connected component, and if it does not begin at a free vertex.  

All in all, I felt that I learned much this semester. While my main struggle was debugging my code and finding time in my busy schedule to do so, I feel that my programming and reasoning skills have improved and that this research opportunity has been very positive. I look forward to continuing next semester!

-Maggie