My Constraint Programming Blog

In Learning constraint programming - part II: Modeling with the Element constraint I complained about the lack of support for Element for matrices in Gecode. It was also my main complaint of Gecode in SweConsNet 2009 talk.

I'm happy to say that Gecode version 3.2 now contains support for this. Thanks to the Gecode team, and especially Christian! See the API for details.

The models mentioned in the former blog post has now been updated to use the new version of Element. They have the same name as the original model, just with a "2" added. The old code is kept (but commented) in the new models for comparison.

• who_killed_agatha2.cpp (old: who_killed_agatha.cpp)
• crossword2.cpp (old: crossword.cpp)
• word_square2.cpp (old: word_square.cpp)

Example: Word square

As an example, here is the old variant for handling element in a matrix of words:

void element_offset(Space& space, 
                    IntArgs words,
                    IntVar e, 
                    IntVar word_len, 
                    IntVar c,
                    IntVar res,
                    IntConLevel icl = ICL_BND) {

  element(space, words, 
                plus(space, 
                     mult(space, 
                          e, 
                          word_len, icl), 
                     c, icl), 
                res, icl);

  
} // element_offset

      // ... and was used as such: 
       element_offset(*this, words, E[i], word_len_v, C[j], tmp, opt.ic());

The new version of Element makes this much easier:

        // ...
        element(*this, words_m, C[j], E[i], tmp, opt.icl());

Performance

For the Word square model the improvement in performance is significant. Now it is very easy to generate a word square of larger orders: The new model gives a solution of order 5 in less than 1 second, whereas the old model took much longer, over a couple of minutes. Order 6 with the new model takes about 2 seconds (I haven't waited for the old model to give a solution).

Here is an example of an order 7 word square; took about a minute with the new model.

laissez
almonry
impling
solideo
snidest
ernesse
zygotes

It is probably possible to tweak this further.

Warning

Last, please note the following warning from Modeling with Gecode about using this feature:

Tip 6.2 (Element for matrix can compromise propagation). Whenever it is possible one should use an array rather than a matrix for posting element constraints, as an element constraint for a matrix will provide rather weak propagation for the row and column variables.

...