Constraint Satisfaction Solver Projects

CSP Solver Projects

Several exciting research projects are available suitable for undergraduate and graduate students.

Prerequisites: If you would like to do one of those projects, please send mail to Karl Lieberherr.

An example of an earlier project on CSP solvers which resulted in a LNCS publication:

@ARTICLE{lieber-vavasis:dortmund,
AUTHOR = "Karl J. Lieberherr and
S. Vavasis",
TITLE = "Analysis of polynomial approximation algorithms for
constraint expressions",
JOURNAL = "Lecture Notes in Computer Science",
YEAR = 1983,
PAGES = "187-197",
VOLUME = 145,
NOTE="6th Gl-Conference Dortmund, January 5-7"
}

Steve Vavasis was back then an undergraduate at Princeton University and he is now a professor at Cornell.

Abbreviations used:
CSP =  Constraint Satisfaction Problem
SAT = Satisfiability

Projects related to publications http://www.ccs.neu.edu/research/demeter/papers/publications.html contains many ideas for projects. Take a look at the most recent papers from our research group and talk to me to identify a suitable project. (We are just writing the first paper in this space)

Compute P-optimal thresholds. Solve the MaxCSP game for relations of rank 3. Consider a set of relations Gamma and the CSP problem CSP(Gamma). Find the optimal solution for the MaxCSP game: Player One selects a CSP(Gamma) instance with less than one million variables and gives it to player Two. Two computes the maximal assignment and wins the fraction of the satisfied constraints in million of dollars. (if the fraction is 1/2 it is 1/2 million dollars). What is the optimal strategy for player One? This game is related to computing the P-optimal threshold t[Gamma]. We focus on computing the P-optimal thresholds for sets of relations Gamma that are of at most rank 3. Write a program that takes as input any subset Gamma of the 256 relations of rank 3. The output is a program that computes t[Gamma} to any desired accuracy. First consider a Gamma that contains exactly one relation. For example, t[{OneInThree}] = 4/9. Then consider pairs of relations and then triples. Etc.

Combining Superresolution and Optimally Biased Coins Develop an implementation based on superresolution and algorithm MAXMEAN that beats other CSP and SAT algorithms on several benchmarks. In other words, we want to translate the theoretical advantages (P-optimality, efficient relation manipulation, learning) into a practical advantage.