CSG260 Advanced Software Development
Karl Lieberherr
Fall 2006

Homework 5
---------------------------------------------------------------------

Due date: Oct. 17, 2006

Now that we have algorithm MAXMEAN implemented for MaxCSP
with all the polynomial 
manipulation software, we want to explore new territory with it.
The first is the territory called SLS (Stochastic Local Search).
There are entire books on this topic: 

http://www.sls-book.net/
Stochastic Local Search
Foundations and Applications
by Holger H. Hoos & Thomas Stützle
Morgan Kaufmann / Elsevier, 2004 

Other websites offer implementations of SLS based CSP solvers,
such as this one at UBC:
http://www.cs.ubc.ca/labs/lci/CIspace/Version4/hill/

The second one is the territory of finding all 
assignments satisfying all constraints of a CSP problem.
This application is useful in inference from Bayesian networks.

Here is a summary of local search for SAT:

Make a guess (smart or dumb) about values of the variables
repeat
 How is the current assignment?
 Try flipping a variable to make things better.
until satisfied

Algorithms differ on which variable to flip.

Algorithms usually get stuck in local optima.
No neighbor is better, but not at global optimum. 

How to escape local optima?
Restart every so often.
Don't be so greedy (more randomness)
With some probability, flip a randomly chosen variable 
instead of a best-improving variable.

We will use MAXMEAN ideas for local search as follows:

By a renaming of a formula we mean a formula where some of the
variables x are flipped: x -> x' (x is replaced by the negation of x).
Note that this will change the polynomials associated with the formula.

We start with a random renaming of the formula f
and compute maxappmean(Ren(f)) = HDID. 
If there is a renaming Ren'(f) that differs only
in one variable y and so that maxappmean(Ren'(f)) > HDID
then we choose this renaming and continue the local search
(also called hill climbing).
With a certain probability we rename a random variable instead
of choosing a variable that improves maxappmean.
Let's call this algorithm SLS-MAXMEAN.

PART 1:
-------

Implement stochastic local search for MaxCSP. As a subalgorithm you need 
a function 

int rename(int relationNumber, int variableNumber)   
which returns the relationNumber of the renamed relation 
when variableNumber is flipped.

SLS-MAXMEAN is interesting in that it does not use the weight
of the satisfied clauses as guide but the weight of the satisfied clauses that
maxappmean predicts.

Can a generic local search algorithm be modified into 
SLS-MAXMEAN by using an aspect?



PART 2:
-------

Extend algorithm MAXMEAN to count the number of satsifying 
assignments of a CSP instance.
A good approach is probably to extend superresolution so that
when a satisfying assignment is found, a "minimal" clause is learned
which prevents that the same assignment is considered again.
In this case, adding this learned clause might change the satisfiability
of the formula.

The hope is that the use of MAXMEAN will "quickly" find all
satisfying assignments.

Can the transition from: "find at least one satisfying assignment"
to "find all satisfying assignments" be done using an aspect 
without changing the base code?