My Constraint Programming Blog

The last week I have tested the equation discovery system Eureqa which uses genetic programming (symbolic regression). Hopefully it may be of some interest.

Today I blogged about my (simple) experiments on my Swedish blog Eureqa: equation discovery med genetisk programmering. Google translation to English: Eureqa: equation discovery with genetic programming.

Also, see My Eureqa page.

Posted by hakank at 09:22 AM | Permalink | Comments (2)

The last week I have solved some (more) of New Scientist's Enigma problems. Note: You may have to be a subscriber to read all the articles, however there is a grace period with some free peeks (7 it seems to be).

Enigma problems

Here are the new models of Enigma problems. All are written in MiniZinc.

• enigma_counting_pennies.mzn: Enigma Counting pennies (from 2005)
  Here all the 24 ways of permuting a list of 4 items are needed. Instead of calculating them, I simply listed all the variants and used them later as index.
• enigma_843.mzn: Enigma How many are whole? (#843)
  In this model there was problem using the following type of reifications:

    square(ONE) /\ ( square(TWO) \/ square(THREE) \/ square(FOUR)) % /\ ..
    % or
    (square(ONE) /\ ( bool2int(square(TWO)) + bool2int(square(THREE)) + bool2int(square(FOUR)) = 1) % /\ ...
  

  where square is defined as:

  predicate square(var int: y) =
    let {
       var 1..ceil(sqrt(int2float(ub(y)))): z
    } in
     z*z = y;
  

  In some of the later versions of MiniZinc (probably 1.0.2), the handling of reification was changed. My fix was to add a boolean matrix which handled the boolean constraints. It is not beatiful:

     % In the list ONE TWO THREE FOUR just the first and one other are perfect squares.
     square(ONE) /\ 
     [bools[1,j] | j in 1..4] = [square(ONE),square(TWO),square(THREE),square(FOUR)] /\
     sum([bool2int(bools[1,j]) | j in 1..4]) = 2 /\
     % ...
  

• enigma_1530.mzn: Enigma Tom Daley (#1530)
  A simple alphametic puzzle.
• enigma_1535.mzn: Enigma Back to front (#1535)
  Magic square with some more constraints.
• enigma_1555.mzn: Enigma Not a square (#1555)
  Another alphametic puzzle on a grid.
• enigma_1557.mzn: Enigma Reverse Division (#1557)
  Division and reversing some numbers.
• enigma_1568.mzn: Enigma Odd puzzle (#1568)
  Long multipication alphametic puzzle.
• enigma_1570.mzn: Enigma Set of cubes (#1570)
  Pandigital problem over at set of cubes. Here I simply listed the cubes between 0^3 and 1000^3 instead of calculating them. This may be consider cheating...
• enigma_1575.mzn: Enigma All our days (#1575)
  Another alphametic puzzle with some more constraints.

Some of these problem may have been better solved using other means, e.g. pure (or not so pure) mathematics, but this is after all a blog about constraint programming, and modellng them is good exercise. And fun.

I have also solved - or at least modeled - some of the open problems: 1573, 1574, 1576, and 1577, but will not publish the models until they are closed. I "accidentally" published problem #1574 the other day before I realized it was still open, but so be it.

Some other models/data files

Here are two simple new problems taken from Choco's (forthcoming site ) example distribution:

• candles.mzn: Birthday Candles
• how_old_am_i.mzn: How old am I

Also, a new data file for the Bridge and Torch model: bridge_and_torch_problem8.dzn, which is, as I understand it, the same as Choco's U2planning problem.

Birthdays 2010 puzzle

Last, here is a very simple puzzle of my own based on a coincidence of birth years of me and my brother and the current year:

This year (2010) my older brother Anders will be the same age as the year I was born in the last century, and I will be the same age as the year he was born in the last century. My brother is four years older than me. How old are we this year?

A (unnecessary complex) MiniZinc model of this problem is birthdays_2010.mzn. Of course, it can be solved much easier with the simple equation: {H+A=110,A-H=4} (link to Wolfram Alpha), or in MiniZinc:

constraint H+A = 110 /\ A-H = 4;

But this latter version is not very declarative, and I - in general - prefer the declarative way.

Update: Added link to Wolfram Alpha for the simple equation above.

Posted by hakank at 07:59 PM | Permalink

This problem is from Uwe Hoffmann Finding celebrities at a party (PDF):

Problem: Given a list of people at a party and for each person the list of people they know at the party, we want to find the celebrities at the party. A celebrity is a person that everybody at the party knows but that only knows other celebrities. At least one celebrity is present at the party.

(This paper contains an implementation of the problem in Scala.)

Note: The original of this problem is Richard Bird and Sharon Curtis: "Functional pearls: Finding celebrities: A lesson in functional programming" (J. Funct. Program., 16(1):13–20, 2006), but I (nor Hoffmann) have not been able to access this paper. Update: I have now got hold of this paper. Thank you SW!

The example in Hoffmann's paper is to find of who are the celebrity/celebrities in this party graph:

Adam  knows {Dan,Alice,Peter,Eva},
Dan   knows {Adam,Alice,Peter},
Eva   knows {Alice,Peter},
Alice knows {Peter},
Peter knows {Alice}

Solution: the celebrities are Peter and Alice.

MiniZinc model

The MiniZinc model of this problem is finding_celebrities.mzn.

Following are some discussion of the two constraints

• All must knows a celebrity
• Celebrities only knows a celebrity

But first a comment how the party graph is represented.

Party graph

Here I have chosen to represent the party as an array of sets:

  Adam  (1) knows {Dan,Eva,Alice,Peter}  {2,3,4,5}
  Dan   (2) knows {Adam,Alice,Peter}     {1,4,5}
  Eva   (3) knows {Alice,Peter}          {4,5}
  Alice (4) knows {Peter}                {5}
  Peter (5) knows {Alice}                {4}

This is coded in MiniZinc as:

party = [
          {2,3,4,5}, % 1, Adam
          {1,4,5},   % 2, Dan 
          {4,5},     % 3, Eva
          {5},       % 4, Alice
          {4}        % 5, Peter
         ];

This corresponds to the following incidence matrix, which is calculated in the model. For simplifying the calculations, we assume that a person know him/herself (this is also handled in the model).

% 1 2 3 4 5
  1,1,1,1,1, % 1
  1,1,0,1,1, % 2
  0,0,1,1,1, % 3
  0,0,0,1,1, % 4
  0,0,0,1,1  % 5

This conversion from incidence sets (party) to incidence matrix (graph) is done by the set2matrix predicate:

predicate set2matrix(array[int] of var set of int: s,
                     array[int,int] of var int: mat) =
     forall(i in index_set(s)) ( graph[i,i] = 1)
     /\
     forall(i,j in index_set(s) where i != j) (
      j in party[i] <-> graph[i,j] = 1
    )

All must know a celebrity

I started this model by consider the celebrities as a clique, and therefore using the constraint clique (which is still included in the model). However, is not enough to identify the clique since there may be other cliques but are not celebrities. In the above example there is another clique: {Dan,Adam}.

In fact, the clique constraint is not needed at all (and it actually makes the model slower). Instead we can just look for person(s) that everybody knows, i.e. where there are all 1's in the column of a celebrity in the party graph matrix (graph in the model). This is covered by the constraint:

forall(i in 1..n) (
   (i in celebrities -> sum([graph[j,i] |j in 1..n]) = n)
)  

This is a necessary condition but not sufficient for identifying celebrities.

Celebrities only know each other

We must also add the constraint that all people in the celebrity clique don't know anyone outside this clique. This is handled by the constraint the all celebrities must knows the same amount of persons, i.e. the size (cardinality) of the clique:

forall(i in 1..n) (
   i in celebrities -> sum([graph[i,j] | j in 1..n]) = num_celebrities
)

As noted above, a person is assumed to know him/herself.

Running the model

If we run the MiniZinc model finding_celebrities.mzn we found the following solution:

celebrities = 4..5;
num_celebrities = 2;

which means that the celebrities are {4,5}, i.e. {Alice, Peter}.

Another, slightly different party

We now change the party matrix slightly by assuming that Alice (4) also know Adam (1), i.e. the following incidence matrix:

 % 1 2 3 4 5
   1,1,1,1,1, % 1
   1,1,0,1,1, % 2
   0,0,1,1,1, % 3
   1,0,0,1,1, % 4
   0,0,0,1,1  % 5
]);

This makes Alice a non celebrity since she knows the non celebrity Adam, and this in turn also makes Peter a non celebrity since he knows the non celebrity Alice. In short, in this party there are no celebrities.

The model also contains a somewhat larger party graph with 10 persons.

Update about 8 hours later There is now a version which uses just set constraints, i.e. no conversion to an incidence matrix: finding_celebrities2.mzn. The constraint sections is now:

constraint
  num_celebrities >= 1

  /\ % all persons know the celebrities,
     % and the celebrities only know celebrities
  forall(i in 1..n) (
     (i in celebrities -> 
             forall(j in 1..n where j != i) (i in party[j]))
     /\
     (i in celebrities -> 
             card(party[i]) = num_celebrities-1)
  )

I have kept the same representation of the party (the array of sets of who knows who) as the earlier model which means that a person is now not assuming to know him/herself. The code reflects this change by using where j != i and num_celebrities-1.

Posted by hakank at 11:19 AM | Permalink