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

Week 1-4

My group has begun our research by doing background reading in Rina Dechta’s book, Constraint Processing, on Constraint Satisfaction Problems (CSPs) and the SAT problem.   Our advisor, Dr. Choueiry, spent a fair amount of time during the first week making sure we had a clear understanding of these two problems.  Our next step entailed utilizing a java CSP parser and creating classes to store that the CSP.  This was a fairly simple task but came with a few issues mostly in trying to understand the parser.

With our initial program completed and thoroughly tested, we moved to studying Arc Consistency.  In particular we studied the AC1, AC3, and AC2001 algorithms.  We went through the pseudo code of all three of these algorithms and implemented AC1 and AC3.  Each of us implemented these algorithms and recorded the number of consistency check, how many domain values were removed, the CPU time, and other information for each CSP instance.  Once we separately implemented these algorithms, we compared results to make sure our implementations were correct and our results were consistent.  We ran into quite a few issues with this and spent ample time debugging our programs and going through smaller problems manually to see what see what the actual number results should be.

After this step, we ran both AC3 and AC1 algorithms on 800 randomly created instances: we varied the tightness of the CSP and created 50 instances of each of these tightnesses.  We compared the results of the CPU time and the consistency checks of both AC1 and AC3.  We graphed the averages and ran the t test on each of the tightnesses.  Our results showed that indeed AC3 performs better than AC1.

Our next step was to study algorithms to search for solutions to the CSP instances.  We studied Patrick Prosser’s paper, “Hybrid Algorithms for the Constraint Satisfaction Problems”.  We are in the process of implementing the backtrack search algorithm.

(We will be posting weekly on our progress)

-Mary Burke

First Week

Looking forward to a great semester working with Courtney, Maggie and Mary on characterizing and solving constraints in program analysis.