My Constraint Programming Blog

Version 3.2.1 of Gecode is released.

From the Change log:

Changes in Version 3.2.1 (2009-11-04) This release fixes one serious bug in the element constraint for matrices; adds branchings using accumulated failure counts (also known as weighted degree); provides some optimizations (mostly for element constraints and for regular expressions with millions of nodes); adds two cute models (word-square and crossword); and a little this and that as always.

• Kernel
  • Additions
    • Propagators and variables now maintain an accumulated failure count (AFC). (major). Details: The AFC of a propagator counts how often has the propagator failed during the entire search, and the AFC of a variable is its degree plus the sum of the AFCs of all propagators depending on the variable. While it looks straightforward, this required a major extension of the Gecode toplevel namespace. kernel to deal with global information accessed concurrently from several threads during search. The AFC is also known as "weighted degree".
• Finite domain integers
  • Additions
    • Added INT_VAL_RANGES_MIN (and INT_VAL_RANGES_MAX) as value selection for branching: it tries the values from the smallest (largest) range first, if the variable's domain has several ranges, otherwise it splits the domain. (minor)
    • Added AFC-based branching strategies for integer and Boolean variables: INT_VAR_AFC_MIN, INT_VAR_AFC_MAX, INT_VAR_SIZE_AFC_MIN, INT_VAR_SIZE_AFC_MAX. For details, see "Modeling with Gecode". (major)
  • Other changes
    • The semantics of division and modulo has changed to match the C standard. This means that the operations round towards zero, and that the result of the modulo has the same sign as its first argument. (minor)
  • Bug fixes
    • Fixed segfault in matrix element constraint. (major)
    • Added missing dispose function for linear disequality of Boolean variables (the only problem was that with a proper dispose function more memory can be reused when the propagator becomes subsumed, so really a tiny quirk). (minor)
  • Performance improvements
    • Element constraints for integer arrays now accept shared integer arrays (IntSharedArray). By this, the very same array can be shared among several element constraints. Models require no change, as IntArgs are automatically coerced to IntSharedArrays. See "Modelling with Gecode" for more explanation. (minor)
    • Optimized element for matrices (in special cases, the propagator is up to six times as efficient as before). (minor)
• Finite integer sets
  • Additions
    • Added AFC-based branching strategies for set variables: SET_VAR_AFC_MIN, SET_VAR_AFC_MAX, SET_VAR_SIZE_AFC_MIN, SET_VAR_SIZE_AFC_MAX. For details, see "Modeling with Gecode". (major)
  • Other changes
    • Split rel-op.cpp and rel-op-const.cpp into several compilation units, to avoid excessive memory and time usage of the gcc compiler. (minor)
• Minimal modeling support
  • Performance improvements
    • Conversion of a regular expression to a DFA would crash on regular expressions with several million nodes (due to running out of call stack space). (minor, thanks to Håkan Kjellerstrand)
• Example scripts
  • Additions
    • Added word square puzzle. (minor , contributed by Håkan Kjellerstrand)
    • Added crossword puzzle (thanks to Peter Van Beek for providing access to some crossword grids). (minor, thanks to Peter Van Beek)
  • Other changes
    • Sudoku and GraphColor now uses smallest size over accumulated failure count (AFC) as the default heuristic. (minor)
  • Bug fixes
    • The Nonogram example no longer crashes on empty lines. (minor, thanks to Jan Wolter)
• Gecode/FlatZinc
  • Bug fixes
    • Fixed statistics output (number of solutions was sometimes wrong). (minor)
• General
  • Other changes
    • Now posting of propagators and branchers take an object of class Home (rather than just a space) that can carry additional information relevant for posting (for example, groups and accumulated failure information). Models do not need to be changed in any way! (major) :Details: While models require no change, propagator rewriting does (it will work but some information might be lost). Instead of writing something like GECODE_REWRITE(*this,SomeProp::post(home,...)); where *this is the propagator to be rewritten, you should now write GECODE_REWRITE(*this,SomeProp::post(home(*this),...)); By this, the new propagator will inherit information from *this (in particular the accumulated failure count).

Some notes about the new models

I can now proudly announce that my model word_square.cpp has been included (as the model word-square.cpp), or rather a much improved version of it. Christian Schulte and Mikael Lagerkvist has done a great job of making it very effective with two different approaches. For example, it presents all 17 word squares of order 7 (i.e. a 7x7 square) given the included word list in about a minute on my machine. Some of the fixed bugs above was found when we tested this model.

The other new model, crossword.cpp, solves crossword puzzles given a problem template and a word list. Included are 72 problems taken from different sources, basically a standard benchmark repository. This is also an impressive demonstration of an effective solution of a standard (and fun) problem using a general system.