mercredi 29 septembre 2010

Getting all the solutions with google solver

Laurent explained to me how to get all the solutions in a more elegant way than with collectors and assignment. Here is the trick for the Dudeney problem:


solver.NewSearch(db)
while solver.NextSolution():
print nb
solver.EndSearch()


What I still have to discover is:
- How to get the fix point after each post in the python model ?
- How to implement a search (at least variable/value heuristic) in python ?
- How to make LNS and defining a fragment from python ?

mardi 28 septembre 2010

A Martin Gardner problem

Here is a Gardner problem that was posted today on this site
The solution I found manually is really ugly. I would be happy if someone could tell me an elegant way to solve it. In case you want to check your solution here is a google cp-solver model:

  
from constraint_solver import pywrapcp

solver = pywrapcp.Solver('Gardner')
dx = [solver.IntVar(range(10),'x'+str(i)) for i in range(2)]
dy = [dx[1],dx[0]]
x = solver.IntVar(range(1,100),'x'+str(i))
y = solver.IntVar(range(1,100),'x'+str(i))

m = solver.IntVar(range(1,100000),'m')

solver.Add(x == 10*dx[0]+dx[1])
solver.Add(y == 10*dy[0]+dy[1])

solver.Add(x*x - y*y == m*m)

solution = solver.Assignment()
solution.Add(x)
solution.Add(y)
solution.Add(m)
collector = solver.AllSolutionCollector(solution)

solver.Solve(solver.Phase(dx, solver.INT_VAR_DEFAULT,
solver.INT_VALUE_DEFAULT),[collector])

for i in range(collector.solution_count()):
current = collector.solution(i)
x = current.Value(x)
y = current.Value(y)
m = current.Value(m)
print "sol:",x+y+m,"x:",x,"y:",y,"m:",m

print "#fails:",solver.failures()
print "time:",solver.wall_time()

dimanche 26 septembre 2010

Where are CP people located ?

It's really funny that after a few posts on this blog, we can already see a trend.
For those familiar with the CP/CPAIOR conferences, this also confirms where the authors of the publications are mainly coming from. I guess our goal is to contaminate all the map ;-)


US
334
France
73
Canada
44
UK
41
Germany
31
Australia
29
Belgium
25
Sueden
17
Netherland
13
India
12

vendredi 24 septembre 2010

Dudeney number

I discovered yesterday Dudeney Numbers
A Dudeney Numbers is a positive integer that is a perfect cube such that the sum of its decimal digits is equal to the cube root of the number. There are only six Dudeney Numbers and those are very easy to find with CP.
I made my first experience with google cp solver so find these numbers (model below) and must say that I found it very convenient to build CP models in python!
When you take a close look at the line: solver.Add(sum([10**(n-i-1)*x[i] for i in range(n)]) == nb)
It is difficult to argue that it is very far from dedicated optimization languages!

from constraint_solver import pywrapcp



def dudeney(n):

solver = pywrapcp.Solver('Dudeney')

x = [solver.IntVar(range(10),'x'+str(i)) for i in range(n)]

nb = solver.IntVar(range(1,10**n),'nb')

s = solver.IntVar(range(1,9*n+1),'s')



solver.Add(nb == s*s*s)

solver.Add(sum([10**(n-i-1)*x[i] for i in range(n)]) == nb)

solver.Add(sum([x[i] for i in range(n)]) == s)



solution = solver.Assignment()

solution.Add(nb)

collector = solver.AllSolutionCollector(solution)



solver.Solve(solver.Phase(x, solver.INT_VAR_DEFAULT,

solver.INT_VALUE_DEFAULT),[collector])



for i in range(collector.solution_count()):

current = collector.solution(i)

nbsol = current.Value(nb)

print nbsol



print "#fails:",solver.failures()

print "time:",solver.wall_time()



if __name__ == '__main__':

dudeney(6)

lundi 20 septembre 2010

Decomposition of sortedness global constraint

A recent trend of CP that I noticed is the decomposition of global constraints.

See for instance the papers:

· Decomposition of the NValue Constraint. C. Bessiere, G. Katsirelos, N. Narodytska, C.G. Quimper, T. Walsh. Proceedings CP'10, St Andrews, Scotland, pages 114-128.

· Decompositions of All-Different, Global Cardinality and Related Constraints. Christian Bessière, George Katsirelos, Nina Narodytska, Claude-Guy Quimper, and Toby Walsh. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 09), pages 419-424, 2009.

· Decomposing Global Grammar Constraints. Claude-Guy Quimper and Toby Walsh. In Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming (CP 07), pages 590-604, 2007.

You can find these papers on the personal page of Claude Guy

I find these decompositions very useful since it can avoid the error prone task of implementing difficult algorithms for global constraints.

We will make an attempt of decomposing another global constraint: the sortedness constraint (I’m not aware of a decomposition of this one).

The paper describing bound-consistent filtering for this constraint is:

Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint, Kurt Melhorn and Sven Thiel, CP2000.

If you don’t know what the sortedness is about, here is a quick reminder:

sortedness(x[], s[],p[]) takes three f.d . var array as arguments and it enforces that s is a sorted version of x and p represents the permutation of the sort.

For instance sortedness(x[5,2,4,1,3],s[1,2,3,4,5],p[4,2,5,3,1]) is a valid instantiation.

If you don’t have the implementation of sortedness from the paper above at hand, here is what you usually do as a straightforward model:


post(s[i] == x[p[i]])
forall(i in 1..n-1) {
post(x[p[i]] <= x[p[i+1]])
post(s[i] <= s[i+1])
}
post(alldifferent(p))
Unfortunately the above model does not enforce bound consistency.

We will add redundant constraints to strengthen the decomposition and hopefully enforce bound consistency with the decomposition. The redundant constraints are based on the counting sort algorithm. Looking at our example sortedness(x[5,2,4,1,3],s[1,2,3,4,5],p[4,2,5,3,1]) the idea is the following:

How many values in x can be strictly smaller than s[i] (assuming indices starts at 1)? The answer is at most i-1 otherwise value s[i] would be at a greater index. This idea is the basis of the linear time counting sort algorithm. Here is how this idea is translated in CP terms:



minval = min(i in 1..n) x[i].min()
maxval = max(i in 1..n) x[i].max()
#define an array of variable occ with domains {0,...,n} that will represent the number of occurrences of each value
var occ [minval..maxval](0..n)
#gcc to count number of occurrences of each values in the array x
post(gcc(x,occ))
#same for the sorted ones, not sure it is useful
post(gcc(s,occ))
var nbBefore [minval..maxval](0..n) #nbBefore[i] = #{i | x[i]#obviously no values are smaller than minval
post(nbBefore[minval] == 0)
forall(i in minval+1..maxval) {
cp.post(nbBefore[i] == sum(j in minval..i-1) occ[j])
}
forall(i in 1..n) {
#there are strictly less than i values smaller than s[i]
cp.post(nbBefore[s[i]] < i)
}

I still need to prove formally but I think this decomposition achieves bound-consistency for sortedness. Any comments are welcome (if you find it useful, if you find a counter example or a better decomposition or if something is not clear…).

mercredi 15 septembre 2010

Google CP Solver is available!

This is my first scoop!
You can find the source code of the Google CP solver at this address
https://code.google.com/p/or-tools/
you can checkout a read only copy anonymously over HTTP:

svn checkout http://or-tools.googlecode.com/svn/trunk/ or-tools-read-only
If you want to be informed about the future development dont' forget to become a member of the or-tools group:

Now, you can ask for a review :-) or better tell me what you think (not discuss about the fact that you were already aware of this project)
 

Welcome!

Some people asked me to create a blog about constraint programming.
I thought it could be a hard task, because I already need to maintain my personnal webpage, my webpage for my students and the webpages of the 2nd year students at the university. Fortunately, someone (I decided to keep the names secret in this blog) gave me the Google url for managing easily a blog (https://www.blogger.com/start?hl=fr). Thus, I created this blog in 1 minute (plus 1 min due to an internal error) which seems to be better than using wordpress which claims to require only 5 minutes.

So, welcome to this blog where you are going to learn some news about constraint programming and certainly also about some other stuff because I am sure that I will not resist to speak about different thinks.