My Constraint Programming Blog

Version 3.4 of Gecode has been released. It can be downloaded here.

This version has quite a few changes. My favorites are

• the extended "syntactic sugar" for rel and expr
• "Modeling and Programming with Gecode" which has been extended with many sections and chapters, for example quite a few case studies.

Very soon after this blog post, I will also publish two posts related to this new Gecode version:

• Changes of my existing Gecode models
• About 100 new Gecode models, which use the new syntax and features

Here are the Changes:

Changes in Version 3.4.0 (2010-07-26)

This release includes: considerably improved support for posting expressions and relations (also including set and full arithmetic expressions); other improvements for modeling (array initialization and element addition to arrays); state-of-the-art unary and cumulative scheduling propagators (including optional and flexible tasks); major cleanups of the variable and view infrastructure (now also documented in MPG); cleanups of the examples; several other fixes and performance improvements.

This release is the first to be accompanied by a complete version of "Modeling and Programming in Gecode" which has been extended by many new case studies and parts on programming search engines and variables.

• Kernel
  • Additions
    • Added LocalObject and LocalHandle classes that can be used for space-allocated objects that are shared within a space, for example among several propagators or propagators and branchers. (minor)
  • Other changes
    • The support for dynamically resizing variable arrays has been removed (it was buggy and inefficient). Instead, all argument arrays now support adding elements using operator<<. In addition, all arrays now support concatenation using operator+ and slicing, and variable arrays, view arrays, and variable argument arrays include a test whether all variables are assigned. (major)
  • Bug fixes
    • Posting a propagator in a failed space could make the space non-failed again. (minor)
• Finite domain integers
  • Additions
    • You can now construct IntArgs from an STL vector, an IntSharedArray, or using simple comprehensions. (minor)
  • Other changes
    • The argument arrays now have constructors that create new variables. (minor)
    • IntArgs with simple sequences of values can now be created using the IntArgs::create static member function. (minor)
  • Performance improvements
    • Optimized element propagator, expect a speed up of around 35-50% in most cases. (minor)
• Finite integer sets
  • Other changes
    • The argument arrays now have constructors that create new variables. (minor)
  • Bug fixes
    • Fixed the include and exclude tell operations of set variables so that they work with empty ranges. (minor)
• Scheduling constraints
  • Additions
    • Added scheduling constraints for tasks with flexible duration (for both unary and cumulative resources), and made all scheduling propagators deal correctly with zero length tasks. (major)
    • Added propagators for cumulative scheduling. (major)
• Minimal modeling support
  • Additions
    • The minimodel library now provides convenient post functions for set constraints. (major)
  • Other changes
    • The Matrix class now supports const operations and has an output operator. (minor)
    • Linear expressions can now contain non-linear parts, such as multiplications or divisions, or set expressions such as cardinality. (major)
    • The minimodel post functions have been split into two functions, rel and expr. While rel posts a constraint, expr returns a new variable constrained to the given expression. This change makes it possible to get rid of the reification operator (~) as well as the tt and ff functions, which were previously needed to distinguish between relations and expressions. Boolean equivalence and implication can now be expressed using operators (==,<<,>>). (major)
    • Array slices can now be empty. (minor)
  • Bug fixes
    • Fixed a bug in minimodel, which could crash when using zero coefficients. (minor, thanks to Håkan Kjellerstrand)
  • Performance improvements
    • Posting linear expressions performs more aggressive optimizations for assigned variables. (minor)
    • Arithmetic modeling functions now try to avoid creating new variables and posting propagators for common cases. (minor)
• Script commandline driver
  • Other changes
    • The driver now catches SIGINT (i.e., pressing Ctrl-C) and stops the search properly, printing statistics up to the point where it stopped. (minor)
    • Running a script in time mode stops all iterations and samples immediately if a single run reaches a limit (eases benchmarks with timeouts). (minor)
• Example scripts
  • Additions
    • New custom branching for the BACP example using a custom value selection. (minor)
  • Removals
    • Removed stress tests, the real examples are much more stressful, actually! (minor)
  • Other changes
    • The Nonogram example now uses AFC as the default branching and includes some more instances. (minor)
    • Take advantage of the better modeling support for the Balanced incomplete block design (BIBD), Golomb ruler, Kakuro, Black Hole, and Warehouse examples (nothing but dusting off examples that have been around for ages). (minor)
• Gist
  • Other changes
    • If an inspector throws an exception, an error message is printed indicating which inspector caused the problem. Previously, Gist would crash with a Qt error that was difficult to trace. (minor)
  • Bug fixes
    • Fixed bug in Gist where signals were sent across threads, which makes Qt crash in certain situations on some platforms. (minor)
    • Fixed bug in interactive search where every move in the tree required recomputation. (minor, thanks to David Zaremby)
• Gecode/FlatZinc
  • Bug fixes
    • Boolean relations were incorrect on assigned arguments. (minor)
    • Fixed garbage collection of variables that are not printed. The bug lead to variables being mixed up in the output. (minor)
• General
  • Removals
    • Variables do not have init functions any longer as they are not needed, see MPG for discussion. (minor)
  • Other changes
    • Completely cleaned up variables and views, drastically saving code. (major)
    • The configure script now checks for qmake-qt4 and moc-qt4, which are used on some Linux systems to distinguish between Qt3 and Qt4. (minor)
    • The build system now supports Visual C++ 2010. (minor)