Week 7

This week, we continued working on our implementation of the CBJ algorithm.  We studied the hierarchy of algorithms based on consistency checks and also nodes visited.  We discovered that, overall; FC-CBJ performs the best!  We also began studying the similarities and differences between CSP's and Relational Databases.  We went through the differences in terminology as well as went through examples of projection, selection, intersection, join, and union.  Some of the main differences highlighted were:

CSP's have many relations while databases have only a few relations in a query, databases have a higher arity than CSP's typically, and databases have much larger domains than CSP's (to name a few!).  

This week we are planning to finish comparing our implementations of the CBJ algorithm and begin our implementation of the FC-CBJ algorithm (first with static ordering then with dynamic ordering).

-Mary Burke

Mary Burke Week 6

This last week we finished with our backtrack search algorithm.  I mentioned in my last post that we had issues comparing our search algorithms due to differentness in the way we implemented our search heuristics.  One of the problems we ran into was with using the degree heuristic.  I used the current degree, while my colleague used the future degree.  In my implementation, I simply searched through the list of variables for the variables and sorted them based on the number of ‘neighbors’ the variable had.  I the other implementation, after a variable is found to have the largest number of neighbors it is added to the list than its neighbors’ degree is decremented.  After we discovered this, we decided to run both types of degree orderings.  Additionally, we ran our backtrack search on random instances with varying tightness.  Since these instances were much larger, we had to obtain a special accounts and run our script on the supercomputer at UNL!

Also, during the course of the week, we studied more thoroughly the forward checking algorithm and its hybrids.  We went through the pseudocode of forward checking and studied the data structures and methods used in the algorithm.  We discussed sufficient conditions for the backtrack search, backjump search, conflict-direct backjump search, and forward checking search.  Finally, we began implementing the conflict directed backjump search and will compare results this week.

-Mary Burke

Week 5

During week 5 we began implementing the Backtrack search algorithm fo find one and all solutions to the CSP.  To compare results we implemented variable value ordering heuristics: lexicographically ordering, least domain ordering, ordering by the degree of the variable, and ordering based on the domain size divided by the degree of the variable.  Some of the issues arising in the debugging appear to have come from the ordering particularly when node consistency deleted some domain values.  We are still working on debugging the backtrack search algorithm particularily with the zebra problem CSPs.  Additionally, we also studied conflict directed backtracking, back marking, and discussed how to find all solutions using these search algorithms.

September, 2011

Research has been very engaging so far. Over the last month, I have been gradually learning the methods and processes of research as well as getting a lot of coding experience. First, we familiarized ourselves with the concept of the constraint satisfaction problem (CSP). We researched the structure of the problem and examined microstructures, macrostructures, graphs, networks, and hypergraphs used in CSP representation. We explored some of the applications for this type of problem as well. We then implemented code to parse and interpret an instance of a CSP and design a data structure for storing and manipulating it.  I used Java for this particular task, as Java lends itself well to object-oriented code and CSPs are very modular in nature.

We then developed methods for traversing the vertices of the CSP via its constraints. In my CSP data structure, I allowed each variable to have a set of pointers to each of the neighboring variables in order to make node-traversal simpler. We then expanded our code to include a dynamic domain for each variable of the CSP, allowing us to keep track of each variable’s initial domain as well as its current, modified domain. With this addition to the program, we were able to first implement a node-consistency algorithm to limit the domain of each variable (based on variable constraints), and then implement arc-consistency to eliminate elements of the domains for variable-value pairs based on their shared constraints. For this project, we limited ourselves to binary CSPs because they represent a wide variety of problems and can be more easily conceptualized.

We first implemented an arc-consistency algorithm called AC-1, which removes all inconsistent domain values but is not the most efficient algorithm, as it reiterates through all variable-value pairs each time a node’s domain is reduced. So, we implemented an algorithm called AC-3 which is an improvement on AC-1 in that it reduces the number of constraint checks for CSPs with a moderate tightness level. AC-3 implements a dynamic queue that minimizes the number of variable domains checked and additionally reduces CPU-time for moderately-difficult problems. AC-3 was also slightly more difficult to implement.

We then tested our algorithms through a graphical performance analysis on hundreds of random binary constraint satisfaction problems. We were able to graph this data to determine trends in the number of constraint checks and computation time for both algorithms. We were able to prove that AC-3 did, in fact, perform better than AC-1 in terms of handling moderately difficult problems. We performed a t-test on the number of constraint checks done by each algorithm at different tightness levels of the random CSP instances in order to show that AC-3 performed better on average for CSPs with a moderate-to-high tightness level. This testing was also a useful debugging tool, as it allowed us to ensure that both algorithms were removing the same number of values from the variable domains of the CSP instance.

As this is the first research project I have worked on, I still have much to learn about research methods and tons of background material to delve into. Nevertheless, I am looking forward to implementing new algorithms and gaining a lot from this research opportunity!

--Maggie Krause