Nov. 28, 2011

Recently I’ve been working on implementing AC2001 as and MAC.  The implementation of AC2001 went fairly smoothly especially since I had already implemented AC1 and AC3 previously this semester.  I had a few debugging problem most of which came from confusion about when to I was adding arcs to the queue. I tested my implementation of AC2001 on about 15 instances (including the 3,4,5,6-queens problems and a few different instances of the zebra problem).  The next step was implementing MAC (Maintaining Arc Consistency) with my currently implemented forward checking algorithm.  At first it seemed simple: run FC and if it does not fail form a queue with all constraints between the future variables and run AC2001.  This task has been a lot more challenging than I expected.   I currently have the algorithm working  correctly for finding one solution both with dynamic and static ordering.  I’ve noticed that in comparison to FC and FCCBJ, MAC seems to have quite a few more consistency checks but less nodes visited, backtracks, and CPU time.  Right now I am working on finding all solutions.

-Mary

Weeks 8 and 9

The last couple weeks have been spent mostly implementing the FC-CBJ algorithm.  We are testing this algorithm using both static and dynamic orderings and finding one and all solutions.  This algorithm has been particularly challenging to implement since it seems to have a few more methods to implement. Also, one of the most difficult parts about this assignment has been the dynamic ordering portion.  Once again, I learned the importance of good design!  I originally programmed using a static list of variables and simply ordered the list at the beginning then used the same ordering to solve the problem originally (I obviously was not thinking about having to eventually do dynamic ordering!).  It would have been a better idea to have two separate structures: one for the uninstantiated variables and one for the instantiated variables.  Static ordering for finding one solution was challenging, but I did not run into many debugging issues until I got to the portion of finding all solutions using dynamic ordering.  I found that my program found one complete solution, then found several partial solutions.  Again, this issue came back to the way I had originally designed my program to find all solution by simply using the static variable list.  Overall, this has been the most beneficial task so far!  I’m excited to continue learning about CSP’s and plan on designing my programs a little more carefully in the future.  

-Mary

October, 2011

The last several weeks, we’ve begun exploring and implementing our first CSP solvers. Our first solver implemented the simplest backtracking algorithm, BT, and used several forms of static variable ordering. We studied Patrick Prosser’s paper on types of back-checking, forward-checking, and hybrids of the two. 

We then began work on CBJ (Conflict-Directed Backjumping), one of the most efficient backtracking algorithms mentioned in Prosser’s paper. We are now moving on to forward checking and dynamic variable ordering, which I expect will be a lot more difficult to implement, but I am looking forward to the challenge. 

 The last few weeks, I have been spending some extra time improving and debugging by AC and NC algorithms from earlier. NC reduces a problem that has unary constraints, a case not handled by my AC algorithm, which is why it is important to run NC before AC, or your domains will not be properly filtered. I discovered a bug in my NC algorithm that I only discovered when testing on instances of the Zebra problem—our only test cases in which NC altered the resulting domains. 

Once correcting this, I was able to catch a bug in my implementation of AC-3 and work to correct it. Implementing algorithms is what I find to be the most time-consuming aspect of research, but also the most rewarding aspect. 

My main frustration lately has been time constraints—having a heavy course-load this semester makes it difficult to find extended periods of time to devote to coding and studying. I am happy to say that I have recently registered for spring classes, and have arranged for a lighter schedule that would allow me to devote more time to research. 

-Maggie

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