CSG260 Advanced Software Development
Karl Lieberherr
Fall 2006

Homework 3
---------------------------------------------------------------------

Due date: Oct. 3, 2006

Part 1:
=======

We are now ready to implement the P-optimal algorithm MAXMEAN(A)
for the CSP problem over domain (0,1) for any set
A of relations of rank 1, 2 or 3. MAXMEAN(A) guarantees
to satisfy the fraction t[A] of the constraints for any set
of relations A and if we could satisfy one trillionth
more in polynomial time, we would earn one millian dollars:
http://www.claymath.org/millennium/

We will use an algorithm that for relation reduction that 
Ahmed Abdel Mohsen developed:

https://www.ccs.neu.edu/course/csg260/ssl/RelationReduction/

With his algorithm you can go, for example, from a relation 
R23(x1, x2, x3) to a relation R78(x2, x3) if we know that x1 = true.

In the following I refer to:
http://www.ccs.neu.edu/home/lieber/p-optimal/partial-sat-II/Partial-SAT2.pdf

We need such reductions to compute the polynomials 
mean(S[x=1]) and mean(S[x=0]) since we need to compute:
mean[k-1](S[x=1]) < mean[k](S[x=0])
as part of MAXMEAN.

Note that the polynomial in x:

appmean[x] = sum from 1 to m t[R[i]] appSAT[x](R[i]) is of degree 3.
It is derivative is of degree two and the second derivative
is linear. So the maximum between 0 and 1 of mean[x]
is easily computed.

Once you have x, multiply it by n to get k.

Part 2:
=======

In order to speed up your program, is it worthwhile to
use a two phase approach? When you know the set of
relations involved, can you precompute some values that will be looked
up in the second phase?

http://en.wikipedia.org/wiki/Partial_evaluation
Partial evaluation is a technique that is useful in this context.


Part 3:
=======

Now we want to add a feature to the algorithm from Part 1:
variable ordering. Choose the next variable y to be set to h
so that for S[x=h] maxmean has the best value over all variables and their
assignments. Implement this feature as an aspect.
Document the aspect interface: What kind of assumptions do you make about
the base code for the aspect to work properly?

Part 4:
=======

From the paper from hw 1 we learned that clause learning is an
important technique in modern SAT solvers. 30 years ago I developed the concept of
superresolution to formalize the 
learning-from-mistakes-process in the form of a proof system.

The algorithm we have so far cannot learn from "mistakes"
it has made. Use aspects to add a learning component based on superresolution
to your algorithm. How can you reduce the learned clauses
of length longer than 3 to length 3
or shorter? Hint: introduce new variables.
My superresolution paper is here:
http://www.ccs.neu.edu/research/demeter/biblio/clause-learning.html
You can also find it on SAT Live.

For this part only, assume that you solve the CSP problem and not the
MaxCSP problem, i.e., we want to satisfy all the constraints.

Again define the aspect interface.

Part 5:
=======

This is not a programming task: How would you generalize
superresolution so that it works for MaxCSP?

superresolution to CSP
Max-superresolution to MaxCSP

Define Max-Superresolution.