My Constraint Programming Blog

Gecode version 4.0.0 has been released. Congrats to the developers!

From the Changelog:

Changes in Version 4.0.0 (2013-03-14)

This release adds a multitude of new features, fixes many bugs, and offers a number of performance improvements. There are too many major improvements to even summarize them here all, so here are just some highlights: LDSB as automatic symmetry breaking during search; restart-based search; complete redesign and reimplementation of branching enhancing the expressiveness massively (AFC with decay, activity, user-defined variable and value selection, tie-break control, better randomization, ...); half-reification; addition of floating point constraints.

It is recommended to read the new Chapter in MPG on branching as the changes are substantial and require you to change your programs, see also the full list of changes below.

As the interfaces has changed, please consult How to Change to Gecode 4.0.0.

• Kernel
  • Additions
    • The random seeds for variable and value branching options can now be initialized from a hardware random number generator (see MPG for details). (minor)
    • All ArgArrays now accept STL vectors and input iterators for construction. (minor)
    • The kernel now can record the activity of variables. The activity of a variable is defined as how often the domain of a variable has been pruned during search. For details, see "Modeling and Programming with Gecode". (major)
  • Other changes
    • The default constrain() function for best-solution search now does by default nothing (it used to throw an exception). (minor)
    • The entire infrastructure for variable-value branchers has been reimplemented from scratch. The new design makes a much better compromise between code size, efficiency, and expressiveness: the efficiency is about the same (for examples with no propagation and just branching one can note a slowdown of 2-4%) while code size shrinks drastically (the overall code size for integer variables shrinks by 20%) and the architecture is much more expressive (in particular, it supports tie-break limits, see MPG). (major)
    • Throw exception when the user-defined copy constructor of a class that inherits from Space does not call the Space copy constructor. (minor)
  • Performance improvements
    • Fixed a bug in the main memory allocation routine: now heap block sizes are decreased dynamically as they should be. Also changed the memory configuration parameters as explained in: Zandra Norman, Memory Management for Gecode. KTH Royal Institute of Technology, Sweden, Bachelor thesis, TRITA-ICT-EX-2012:143, 2012. (major, thanks to Zandra Norman)
• Search engines
  • Additions
    • Added support for restart-based search, see MPG for details. (major)
  • Other changes
    • Variable selection for branching used the quotient of size divided by degree, accumulated failure count, or activity. They now use the inverse. That is, for example, it is not any longer INT_VAR_SIZE_DEGREE_MIN() but INT_VAR_DEGREE_SIZE_MAX() (that is, largest degree divided by size). (major) That looks like an annoying change but is in fact essential: the strategies using accumulated failure count and activity now could have run into division by zero issues. And just changing the implementation is not good enough because the values of these measures can now be exposed during tie-breaking.
    • The restart best solution search engine has been removed (it is subsumed by the new restart-based meta search engine RBS). (major)
  • Performance improvements
    • The search engines now do not allocate memory on the search stack for the rightmost branch of each node. This means that the search tree depth is now computed differently. It now represents the actual peak depth required at any one time, taking into account that rightmost branches reuse the stack entry of their parents. (minor)
• Finite domain integers
  • Additions
    • Gecode now supports Lightweight Dynamic Symmetry Breaking (LDSB), see MPG for details. (major , contributed by Christopher Mears)
    • Added value selection strategies for branching INT_VAL_NEAR_MIN(), INT_VAL_NEAR_MAX(), INT_VAL_NEAR_INC(), and INT_VAL_NEAR_DEC(). They can take a previous assignment to the variables to branch on and try to choose values which are near (see MPG for details). (major, thanks to Manuel Loth)
    • Added domain constraint that constrains a variable (or an array) according to the domain of another variable. (minor)
    • Added variants of dom that copy the domain from one variable to another. (minor)
    • The nooverlap constraint now allows sharing of unassigned variables in its argument arrays. (minor)
    • Added half-reification for reified constraints (see Modeling and Programming with Gecode for details). (major)
    • Added pow and nroot constraints. (major)
    • The binpacking constraint now also accepts items of size zero. (minor, thanks to Kathrin Dannmann, Roberto Castañeda Lozano)
    • Added activity-based branching strategies for integer and Boolean variables: INT_VAR_ACTIVITY_MIN, INT_VAR_ACTIVITY_MAX, INT_VAR_ACTIVITY_SIZE__MIN, INT_VAR_ACTIVITY_SIZE_MAX. For details, see "Modeling and Programming with Gecode". (major)
  • Other changes
    • The coefficients for linear constraints are now divided by their greatest common divisor. That means that some equations can be handled now that previously threw an OutOfLimits exception, and some equations can be handled with the more efficient integer precision propagators that previously required double precision. (minor)
    • Generalized definition of no-overlap propagators for better reuse. (minor, thanks to Roberto Castañeda Lozano)
    • The interface for branching on integer and Boolean variables has changed considerably (supporting user-defined variable and value selection, tie-break limit functions, handlers to created branchers, and more). In order to change, you have to add () to all variants of INT_VAR, INT_VAL, and INT_ASSIGN. For example, INT_VAR_SIZE_MIN becomes the function call INT_VAR_SIZE_MIN() and INT_VAL_MIN_MIN becomes the function call INT_VAL_MIN_MIN(). Some of these functions expect additional arguments and can take also optional arguments (this replaces the VarBranchOptions and ValBranchOptions). Please read the new "Branching" chapter in MPG. (major)
    • Respect IntConLevel argument for reified linear constraints with a single integer variable. (minor)
  • Bug fixes
    • Fixed precede constraint with less than two values. (minor, thanks to Roberto Castañeda Lozano)
    • Fixed a bug where bounds consistent distinct reported subsumption instead of failure in certain cases. (major, thanks to Lin Yong)
    • Fixed potential rounding issues in sqr and sqrt constraints. (minor)
    • Fixed copying of tuple sets in extensional constraints and IntSets in sequence constraints (could lead to crashes when using parallel search). (major, thanks to Manuel Baclet)
    • Added missing propagation for nary min/max constraint. (minor, thanks to Jean-Noël Monette)
    • Make extensional constraints work with empty tuple sets. (minor, thanks to Peter Nightingale)
    • Fix count (global cardinality constraint) for multiple occurrences of the same value in the cover array. (minor, thanks to Peter Nightingale)
  • Performance improvements
    • Arithmetic, linear, and cumulative constraints now resort to internal operations using "long long int" rather than "double". This improves performance but also extends the range over integer coefficients that can be handled by linear constraints. (major)
• Finite integer sets
  • Additions
    • Gecode now supports Lightweight Dynamic Symmetry Breaking (LDSB), see MPG for details. (major , contributed by Christopher Mears)
    • Added domain constraint that constrains a variable (or an array) according to the domain of another variable. (minor)
    • Added domain constraints for arrays of set variables. (minor)
    • Added half-reification for reified constraints (see Modeling and Programming with Gecode for details). (major)
    • Added activity-based branching strategies for set variables: SET_VAR_ACTIVITY_MIN, SET_VAR_ACTIVITY_MAX, SET_VAR_ACTIVITY_SIZE_MIN, SET_VAR_ACTIVITY_SIZE_MAX. For details, see "Modeling and Programming with Gecode". (major)
    • Added channeling constraint between arrays of set variables. (major , contributed by Denys Duchier)
  • Other changes
    • The interface for branching on integer and Boolean variables has changed considerably (supporting user-defined variable and value selection, tie-break limit functions, handlers to created branchers, and more). In order to change, you have to add () to all variants of SET_VAR, SET_VAL, and SET_ASSIGN. For example, SET_VAR_SIZE_MIN becomes the function call SET_VAR_SIZE_MIN() and SET_VAL_MIN_INC becomes the function call SET_VAL_MIN_INC(). Some of these functions expect additional arguments and can take also optional arguments (this replaces the VarBranchOptions and ValBranchOptions). Please read the new "Branching" chapter in MPG. (major)
  • Bug fixes
    • Fixed precede constraint with less than two values. (minor, thanks to Roberto Castañeda Lozano)
• Floats
  • Additions
    • Added support for float variables. (major , contributed by Vincent Barichard)
• Minimal modeling support
  • Additions
    • Added pow and nroot expressions for integer variables. (minor)
  • Other changes
    • Made implementations of MiniModel expressions private, so that the MiniModel headers do not have to include propagator headers like gecode/int/linear.hh any longer. (minor)
• Script commandline driver
  • Additions
    • Added commandline options to control restart-based search, see MPG for details. (major)
    • Decay values can now be passed on the command line using the switch -decay. (minor)
    • Added options -file-sol and -file-stat for writing solutions and statistics to arbitrary files and streams. (minor, thanks to Andrea Pretto)
    • The command line -print-last configures whether only the last solution found is printed. (minor, thanks to Josef Eisl)
  • Other changes
    • Boolean options (BoolOption) can now be given a false or true argument and hence are in-line with all other option types. (minor)
• Range and value iterators
  • Documentation fixes
    • Clarified for several iterators that when using the assignment operator both iterators must be allocated from the very same region. (minor)
• Support algorithms and datastructures
  • Bug fixes
    • Fixed a concurrency problem that caused an exception to be thrown at the end of a multi-threaded search on some platforms. (minor)
    • Fixed a bug in the allocation of very large bitsets. (minor, thanks to Max Ostrowski)
• Example scripts
  • Additions
    • New example: Colored matrix without monochromatic rectangles. (minor)
• Gist
  • Additions
    • Added option to invoke move cursors during the automatic search. (minor)
  • Other changes
    • Updated to compile with Qt version 5.0 (still works with Qt >= 4.3 as well). (minor)
• Gecode/FlatZinc
  • Additions
    • Added support for more search annotations (defined in gecode.mzn), and for the restart and decay command line options. (minor)
    • Added native support for lex_less_bool and lex_lesseq_bool. (minor)
    • Gecode/FlatZinc now supports float constraints and variables. (major)
    • The FlatZinc interpreter now supports comparing of nodes in Gist. (major, thanks to Gabriel Hjort Blindell)
    • Added native support for the inverse_set constraint. (minor)
  • Other changes
    • Renamed the FlatZinc executable to fzn-gecode, to better distinguish it when installed alongside other FlatZinc implementations. (minor)
    • The FlatZinc interpreter no longer performs a complete search on variables annotated as var_is_introduced, but tries to extend a solution on the model variables to a solution that includes the introduced variables. Each solution on the model variables is therefore only reported once. (major)
  • Bug fixes
    • The mzn-gecode shell script now passes arguments correctly to the FlatZinc interpreter. (minor)
    • Removed spurious debug output for among constraint. (minor, thanks to Simon Ekvy)
    • Exported registry and helper functions so that users can add constraint handlers to the FlatZinc interpreter. (minor, thanks to Jean-Noël Monette)
• General
  • Additions
    • Added CMake build script for Gecode (CMakeLists.txt). (minor, thanks to Victor Zverovich)
    • Variable selection using AFC now supports decay. Read more in MPG. (major)
  • Other changes
    • Compiles with MSVC 2012. (minor)

Also see:

• Documentation
• Download
• Community