Changelog

Changes in Gecode Versions

• Gecode 4.2.1 (2013-11-05)
• Gecode 4.2.0 (2013-07-19)
• Gecode 4.1.0 (2013-07-01)
• Gecode 4.0.0 (2013-03-14)
• Gecode 3.7.3 (2012-03-23)
• Gecode 3.7.2 (2012-02-27)
• Gecode 3.7.1 (2011-10-10)
• Gecode 3.7.0 (2011-08-31)
• Gecode 3.6.0 (2011-07-15)
• Gecode 3.5.0 (2011-02-01)
• Gecode 3.4.2 (2010-10-09)
• Gecode 3.4.1 (2010-10-08)
• Gecode 3.4.0 (2010-07-26)
• Gecode 3.3.1 (2010-04-09)
• Gecode 3.3.0 (2010-03-15)
• Gecode 3.2.2 (2009-11-30)
• Gecode 3.2.1 (2009-11-04)
• Gecode 3.2.0 (2009-10-05)
• Gecode 3.1.0 (2009-05-20)
• Gecode 3.0.2 (2009-03-26)
• Gecode 3.0.1 (2009-03-24)
• Gecode 3.0.0 (2009-03-13)
• Gecode 2.2.0 (2008-08-25)
• Gecode 2.1.1 (2008-03-06)
• Gecode 2.1.0 (2008-02-29)
• Gecode 2.0.1 (2008-02-07)
• Gecode 2.0.0 (2007-11-14)
• Gecode 1.3.1 (2006-10-25)
• Gecode 1.3.0 (2006-09-19)
• Gecode 1.2.2 (2006-07-25)
• Gecode 1.2.1 (2006-07-19)
• Gecode 1.2.0 (2006-06-20)
• Gecode 1.1.0 (2006-04-10)
• Gecode 1.0.1 (2006-03-01)
• Gecode 1.0.0 (2005-12-06)

Gecode Version Numbers

Gecode version numbers x.y.z change according to the following rules (of thumb):

• when z changes, the programming interfaces for Programming models, and Programming search engines remain stable and only minor additions or improvements are included.
• when y changes, the above mentioned interfaces might have changed and medium to major additions or improvements are included.
• the change of x is reserved for radical changes to Gecode.

Changes in Version 4.2.1 (2013-11-05)

This release fixes several major bugs and adds some minor improvements.

• Kernel
  • Additions
    • Activity information can now be initialized with a branch merit function. (minor, thanks to Kish Shen)
• Search engines
  • Additions
    • Added support for a repeat cutoff generator. (minor, thanks to Roberto Castañeda Lozano)
  • Bug fixes
    • Fix for restart-based search when the master does not have a branching. (major, thanks to Roberto Castañeda Lozano)
    • Restart-based search did not work when the cutoff limit did not strictly increase. (major, thanks to Roberto Castañeda Lozano)
• Finite domain integers
  • Additions
    • Activity information can now be initialized with a branch merit function. (minor, thanks to Kish Shen)
  • Bug fixes
    • Fixed incorrect propagation in sortedness with permutation variables. (major, thanks to Bauke Conijn)
    • Fixed cumulative constraint for 0-usage tasks. (major, thanks to Duane Leslie)
    • Fixed special case check for cumulative that would wrongly classify some instances as disjunctive. (major, thanks to Duane Leslie)
    • The nroot constraint now propagates correctly for negative numbers when the exponent is odd. (major, thanks to Kish Shen)
  • Performance improvements
    • Fix performance of domain consistent element for the case that the result variable is assigned. (minor, thanks to Anne Meyer)
• Finite integer sets
  • Additions
    • Activity information can now be initialized with a branch merit function. (minor, thanks to Kish Shen)
• Floats
  • Additions
    • Activity information can now be initialized with a branch merit function. (minor, thanks to Kish Shen)
• Minimal modeling support
  • Additions
    • The sum of IntArgs can now be computed similarly to the sum of IntVarArgs. (minor, thanks to Philippe Kezirian)
• Gecode/FlatZinc
  • Bug fixes
    • Fixed bug in auxiliary variable branching. (minor)
• General
  • Other changes
    • Compiles with MSVC 2013. (minor)
  • Bug fixes
    • Fix CMake to also build FlatZinc and Driver correctly. (minor)

Changes in Version 4.2.0 (2013-07-19)

This release adds no-goods from restarts, removes memory statistics (but Gecode can be configured for more accurate statistics), and fixes a number of bugs.

• Kernel
  • Additions
    • Added configure switch –enable-peakheap that adds support for memory statistics to the kernel. This comes with a runtime overhead, but provides more accurate information than the previous search engine based statistics. (minor)
  • Other changes
    • Low-level support for AFC is now public. (minor, thanks to Kish Shen)
    • The master() member function used during restart-based search now takes an additional no-goods argument. The default master() function posts no-goods (only effective when enabled in Search::Options). See MPG for details. (minor)
• Search engines
  • Additions
    • Search options have an additional field nogoods_limit that defines too which depth a search tree is inspected for no-goods. (minor)
    • Added support for no-goods from restarts, see Modeling and Programming with Gecode for details.
      Note that also entails that the statistics will report different a different peak depth than in previous releases of Gecode when using no-goods. (major)
  • Removals
    • Removed memory statistics from the search engines. The reason is that the figures were too inaccurate (memory for shared data structure, caches, etc were not counted) and computing the figures was complicated. This feature is replaced by a configure switch that enables peak memory tracking based on operating system information. (major)
• Script commandline driver
  • Additions
    • When using restart-based search, the use of no-goods from restarts can be switched on/off with the -nogoods command line option and the depth limit for extraction of no-goods with the -nogoods-limit command line option. (minor)
• Range and value iterators
  • Bug fixes
    • Fixed segfault in NaryUnion iterator. (minor, thanks to Farshid Hassani Bijarbooneh, Joseph Scott)
• Gecode/FlatZinc
  • Additions
    • Added support for value_precede_int and value_precede_set constraints. (minor)
  • Bug fixes
    • Fixed a memory leak in FlatZincSpace and a few more in the FlatZinc parser. (major, thanks to Chris Mears)
    • Fixed a bug in implicit search heuristic that could lead to a segmentation fault when minimizing an array element. (minor, thanks to Chris Mears)
• General
  • Bug fixes
    • Fixes link error for CMake with MSVC. (minor, thanks to Victor Zverovich)

Changes in Version 4.1.0 (2013-07-01)

This release adds a really useful feature and the required infrastructure to Gist (it now can show information on the alternatives in a search tree), has some new features, and fixes quite a number of bugs (some of which are quite serious, in particular for: LDSB, restart-based search, and FlatZinc).

• Kernel
  • Additions
    • Branchers now support a print() member function. (major)
    • Both AFC and Activity can be changed by a set() function. (minor)
  • Performance improvements
    • Implement the AFC search heuristic using FastMutex, which greatly improves parallel search performance on Mac OS X when using AFC. (minor)
• Search engines
  • Bug fixes
    • Fixed a bug in restart-based search, which would crash if the problem is failed at the root or only had a single solution during best-solution search. (major, thanks to Chris Mears, Roberto Castañeda Lozano)
• Finite domain integers
  • Additions
    • Integer and Boolean branchings now take an optional argument for a user-defined print function. See MPG for details. (major)
    • Added if-then-else constraint (called ite) for integer variables. (minor)
  • Other changes
    • Added classes IntMinimizeSpace and IntMaximizeSpace for cost-based optimization with an integer cost variable. While the classes MinimizeSpace and MaximizeSpace are still available, there use is deprecated and a later release might remove them. (minor)
  • Bug fixes
    • Fixed INT_VALUES_MAX() branching (INT_VALUES_MIN() was used instead). (minor, thanks to Victor Zverovich)
    • Fixed crash due to combination of LDSB and Activity. (major, thanks to Stefano Gualandi)
    • The internal representation of integer variable domains could leak memory to the space. (major)
    • Fixed binpacking crash when the b and s arrays are empty. (minor, thanks to David Rijsman)
• Finite integer sets
  • Additions
    • Set branchings now take an optional argument for a user-defined print function. See MPG for details. (major)
  • Bug fixes
    • Fixed SET_VAR_ACTIVITY_SIZE_MIN/MAX, which used to compute size/activity instead of activity/size. (minor)
    • Fixed crash due to combination of LDSB and Activity. (major, thanks to Stefano Gualandi)
• Floats
  • Additions
    • Float branchings now take an optional argument for a user-defined print function. See MPG for details. (major)
    • Added classes FloatMinimizeSpace and FloatMaximizeSpace for cost-based optimization with a float cost variable. (minor, thanks to Pascal Francq)
  • Bug fixes
    • Fixed FLOAT_VAR_ACTIVITY_SIZE_MIN/MAX, which used to compute size/activity instead of activity/size. (minor)
    • Random value selection for float branchings was not declared with the right types. (minor)
    • Fixed missing propagation in reified rel-constraints. (minor, thanks to Duong Khanh Chuong)
• Minimal modeling support
  • Bug fixes
    • Boolean expressions could lead to a segfault when initialized with default constructor. (minor, thanks to Roberto Castañeda Lozano)
• Script commandline driver
  • Additions
    • Added classes FloatMinimizeScript and FloatMaximizeScript for cost-based optimization with a float cost variable. (minor, thanks to Pascal Francq)
  • Other changes
    • Added classes IntMinimizeScript and IntMaximizeScript for cost-based optimization with an integer cost variable. While the classes MinimizeScript and MaximizeSpcript are still available, there use is deprecated and a later release might remove them. (minor)
  • Bug fixes
    • Fixed a race condition when using parallel search. (minor, thanks to Vincent Barichard)
• Support algorithms and datastructures
  • Additions
    • Added FastMutex class that is implemented using spin locks on some platforms. (minor)
• Example scripts
  • Additions
    • Added LDSB-based symmetry breaking to graph coloring example. (minor, thanks to Stefano Gualandi)
• Gist
  • Additions
    • Gist now can show information on the alternatives in a search tree, using the new menu options "Label branches" and "Label path". (major)
• Gecode/FlatZinc
  • Additions
    • The FlatZinc interpreter now supports float variables as objective functions. (major)
    • Added {int,bool,set,float}_default_search annotations. These can be used on solve items to declare the default search strategy for the respective variable types. (minor)
    • Added int2float constraint which was missing in the FlatZinc interpreter. (minor, thanks to Tias Guns)
  • Bug fixes
    • Fixed printing of float variables to be compatible with MiniZinc output. (minor, thanks to Peter Nightingale)
    • Fixed a segmentation fault when using FlatZinc with float variables that have initializers. (minor, thanks to Peter Nightingale)
    • Fixed the random search strategies to all use the same random number generator instead of different generators all initialised with the same seed (and therefore all producing the same sequences). (minor)
• General
  • Other changes
    • CMake build system tweaked for out-of-source-dir building. (minor, thanks to Cliff Yapp)

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) Details Hide details
      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)

Changes in Version 3.7.3 (2012-03-23)

This release fixes some small bugs in the FlatZinc interpreter and library.

• Gecode/FlatZinc
  • Additions
    • Added mzn-gecode scripts for conveniently solving MiniZinc models using the Gecode FlatZinc interpreter. (minor)
  • Other changes
    • Removed the print command line option. Instead, for optimization problems, using -a will print all solutions, while not using -a will only print the last one. This is consistent with the G12 FlatZinc command line interface. (minor)
  • Bug fixes
    • Fixed "largest" variable selection strategy for set variables. (minor, thanks to Marco Correia)
    • Fixed the parser for set literals. (minor, thanks to Thibaut Feydy)
    • Integer variables with empty domains result in unsatisfiable models instead of an error message. (minor)
    • Support 0-length array declarations. (minor)

Changes in Version 3.7.2 (2012-02-27)

This release fixes several small bugs.

• Kernel
  • Additions
    • Added Archive operators for floats and doubles. (minor)
• Finite domain integers
  • Other changes
    • Throw exception of type OutOfLimits instead of Exception when numerical arguments to sequence constraint are out of range. (minor)
  • Bug fixes
    • Added missing pruning to cumulative edge finding propagator. (minor, thanks to Joseph Scott)
    • Fixed sorted constraint to accept zero-length arrays. (minor, thanks to Kish Shen)
    • Added some missing propagation when posting a channel constraint between an array of Boolean variables and an integer variable. (minor, thanks to Kish Shen)
  • Performance improvements
    • Posting a reified dom constraint on IntVars with an assigned control variable does not create propagators any more, but updates the domain immediately. (minor)
• Finite integer sets
  • Bug fixes
    • The element constraint with SOT_UNION and IntSetArgs reported subsumption too early, resulting in incorrect propagation. (major, thanks to Denys Duchier)
• Minimal modeling support
  • Bug fixes
    • The BoolExpr default constructor did not properly initialize its members, causing crashes. (minor)
• Script commandline driver
  • Bug fixes
    • Fixed rounding for printing the runtime (for example, 1:60:56.157 could be printed...). (minor, thanks to Serge Le Huitouze)
    • Fixed time output for times with zero minutes but nonzero hours. (minor, thanks to Jan Kelbel)
• Gecode/FlatZinc
  • Bug fixes
    • Export RTTI symbols for the FlatZinc AST so that it can be used by client code. (minor)
    • Do not crash when encountering undefined identifier as constraint argument. (minor, thanks to Nicholas Tung)
• General
  • Additions
    • Gecode now compiles on NetBSD. (minor, thanks to Adam Russell)
    • Added a macro GECODE_VERSION_NUMBER that is defined as x*1000000+y*100+z for Gecode version x.y.z. (minor, thanks to Denys Duchier)

Changes in Version 3.7.1 (2011-10-10)

This release fixes several bugs, upgrades to MiniZinc version 1.4, and features some minor improvements.

• Search engines
  • Bug fixes
    • Fixed a bug that crashed the single-thread branch-and-bound search engine when initialized with a failed space. (minor)
• Finite domain integers
  • Additions
    • Added efficient propagators for n-ary Boolean xor and equivalence (as they are now primitive in MiniZinc). (minor)
    • Domain consistency for simple counting constraints can be switched off. (minor, thanks to Kish Shen)
  • Other changes
    • The semantics of n-ary Boolean implication has been changed (to the more convential reading): rel(home, BOT_IMP, x, y) where x is an array of Boolean variable now assumes implication to be right associative. See MPG for explanation. (minor)
  • Bug fixes
    • Fixed bugs in the computation of the required precision (int or double) for linear propagation, and in division operations of scale views. These could cause an incorrect treatment of overflow in linear constraints. (major)
  • Performance improvements
    • Domain consistent distinct runs 10-20% faster. (minor)
• Finite integer sets
  • Bug fixes
    • Do not use SharedArray<IntSet> in the set element constraints, because it does not properly udpate the IntSet during copying. This could cause memory corruption. (major)
• Support algorithms and datastructures
  • Bug fixes
    • Compile again if threads are disabled. (minor)
• Gist
  • Bug fixes
    • Fixed a crash that occurred when double-clicking an unexplored node while move inspectors were active. (minor)
• Gecode/FlatZinc
  • Other changes
    • The FlatZinc interpreter is now compatible with the G12 MiniZinc distribution 1.4. This adds support for var and par identifiers that begin with underscores, the array_bool_xor primitive, as well as the command line option -r for specifying a random seed. (minor)
  • Bug fixes
    • Fixed linear inequations over integer variables that are channeled from Boolean variables. (major, thanks to Håkan Kjellerstrand)

Changes in Version 3.7.0 (2011-08-31)

This release adds and improves quite a number of constraints (total lexicographic order for set variables, membership constraints for integer variables, counting constraints for integer variables using integer sets, range, roots, set element constraints for integer variables, number of values for integer variables). All of these constraints (and some more) are now also available in FlatZinc. Additionally, some fixes and improvements.

This release is an important milestone as Gecode now provides native implementations for all important constraints available in MiniZinc/FlatZinc.

The documentation of constraints in "Modeling and Programming with Gecode" now refers to the Global Constraint Catalog (for those constraints that are listed in the catalog).

• Kernel
  • Additions
    • View arrays can now also use region-allocated memory. (minor)
  • Bug fixes
    • Array slices can now be created from empty arrays. (minor, thanks to Max Ostrowski)
• Finite domain integers
  • Additions
    • Added normal and reified membership constraints for integer and Boolean variables. (major)
    • The count constraints now also support comparison to integer sets in addition to integers and integer variables (which then implements among from the GCCAT). (major)
    • Added nvalues constraint. (major)
  • Bug fixes
    • Added some additional propagation for the count constraints (now, for example, count(home, x, y, IRT_GQ, 1) also constrains y to only take values supported by x). (minor)
    • The estimation of bounds on linear terms did not handle overflow correctly. (major)
• Finite integer sets
  • Additions
    • Added set relations SRT_LQ, SRT_LE, SRT_GQ, SRT_GR for total (lexicographic) order. (major)
    • Added set element constraints with singleton integer variables as arguments. (minor)
  • Bug fixes
    • Fixed a memory leak in the set weights constraint, and use IntSharedArray instead of IntArgs as parameters for weights. (minor, thanks to Johannes Inführ)
• Minimal modeling support
  • Additions
    • Added a convenience function values that restricts the set of values taken by an array of integer variables to a fixed set, using the nvalues constraint. The channel constraints between IntVarArgs and a SetVar now also use nvalues to increase propagation. (minor)
    • Added range and roots, which decompose into set element constraints. (minor)
• Range and value iterators
  • Other changes
    • Cached iterators such as n-ary union and intersection, minus, and cache (of course) are not any longer template classes but take template constructors and member functions. N-ary union and intersection iterators can now also be initialized incrementaly with iterators of different types. (minor)
• Example scripts
  • Additions
    • Added Dominating Queens puzzle. (minor)
• Gist
  • Bug fixes
    • Call solution inspectors also when exploring manually. (minor)
    • Flush output to Gist console, so that output that is not ended by a newline is not lost. (minor)
• Gecode/FlatZinc
  • Additions
    • Added native support for among, nvalues, int_set_channel, member_bool, member_int, sum_pred, and the range and roots constraints. (major)
  • Other changes
    • The set_in and set_in_reif constraints now work for constant sets even when Gecode is compiled without support for set variables. (minor)
  • Bug fixes
    • Added missing primitives set_le, set_lt, set_ge, and set_gt. (major)
• General
  • Bug fixes
    • Install generated variable implementation headers instead of the shipped versions (fixes a problem when building Gecode in a separate directory). (minor, thanks to Gustavo Gutierrez)

Changes in Version 3.6.0 (2011-07-15)

This release adds new constraints (value precedence constraints for integer and set variables, no-overlap constraints for rectangles, constraints for Hamiltonian paths), improves and cleans up a number of existing constraints (scheduling, channeling, relation, bin-packing, lexicographic relations), and adds new functionality (support for externalization of choices for distributed search, support for incremental propagation).

Some models might have to be changed as the graph and scheduling modules have been incorporated into the integer module (removing the respective include directives is sufficient).

On top, there are many small fixes, in particular for FlatZinc.

• Kernel
  • Additions
    • Moved RangeList class, which is a list of ranges implemented as a FreeList, from the set module into the kernel. Also added corresponding Iter::Ranges::RangeList iterator. (minor)
  • Other changes
    • Choices can now be written into an externalized form (called an Archive), and reconstructed from it. This is necessary for serializing paths in a distributed search engine. (major)
• Search engines
  • Bug fixes
    • Fixed memory leak when passing a failed space to a search engine with cloning option set to false. (minor)
• Finite domain integers
  • Additions
    • The cumulative constraints now support an IntVar as the capacity argument. (minor)
    • Added value precedence constraint. (major , contributed by Christopher Mears)
    • Added no-overlap constraint that enforces that rectangles do not overlap (also known as diffn). See "Modeling and Programming with Gecode" for details. (major)
    • Added constraints for Hamiltonian paths (called path). See "Modeling and Programming with Gecode" for details. (major)
    • Generalized lexicographic constraint to arrays of different sizes. (minor, thanks to Kish Shen)
    • Added a CachedView that can cache the domain between propagator invocations and provides an efficient test whether a view has changed since the previous invocation as well as an iterator over the removed domain values. This makes it easier to implement incremental propagation algorithms that need exact delta information. (major)
  • Other changes
    • The cumulatives constraint now does not post the s+p=e constraints, harmonizing its semantics with the cumulative and unary constraints. (minor)
    • Changed semantics of rel(home, x, IRT_NQ), enforces that not all variables in x are equal. See "Modeling and Programming with Gecode" for details. (major)
  • Bug fixes
    • Fixed element and sequence propagators, which were only correct by accident (incorrect use of GECODE_ME_CHECK instead of GECODE_ES_CHECK). (minor)
  • Performance improvements
    • Optimized channeling propagator between an array of Boolean variables and an integer variables. (minor)
    • The disequality constraint between variable arrays has an efficient propagator now. (minor)
    • The ordering constraints rel(home, x, IRT_LE) (also for IRT_LQ, IRT_GR, IRT_GQ) now have an optimal implementation (single incremental propagator). (major)
    • Increased performance of bin-packing propagator by 40 to 300 percent by using staging. (major)
    • The channel constraints between two integer arrays are now more memory efficient when offsets are used. (minor)
• Finite integer sets
  • Additions
    • Added value precedence constraint. (major , contributed by Christopher Mears)
    • Added a CachedView that can cache the domain between propagator invocations and provides an efficient test whether a view has changed since the previous invocation as well as an iterator over the removed domain values. This makes it easier to implement incremental propagation algorithms that need exact delta information. (major)
    • Added channel aliases for set union of an array of integer variables, and renamed channel to channelSorted. (minor, thanks to Marco Correia)
  • Bug fixes
    • Fixed sequence, partition, and union propagators, which were only correct by accident (incorrect use of GECODE_ME_CHECK instead of GECODE_ES_CHECK). (minor)
    • The constructors for set variable arrays and argument arrays threw incorrect VariableEmptyDomain exceptions. (minor)
  • Performance improvements
    • Use new cached views for a more efficient implementation of the channel constraint between IntVarArgs and SetVarArgs. (minor)
  • Documentation fixes
    • Fixed documentation for set channeling constraint. (minor, thanks to Marco Correia)
• Scheduling constraints
  • Other changes
    • The scheduling module has been removed and its constraints have been added to the integer module. (major)
  • Bug fixes
    • Fixed scheduling code for mandatory flexible tasks, which was only correct by accident (incorrect use of GECODE_ME_CHECK instead of GECODE_ES_CHECK). (minor)
• Graph constraints
  • Additions
    • Added circuit constraints with offsets. (minor)
  • Other changes
    • The graph module has been removed and its constraints have been added to the integer module. (major)
• Script commandline driver
  • Bug fixes
    • Fixed a small memory leak in the driver (stop objects were not deleted). (minor, thanks to Jan Kelbel)
• Example scripts
  • Additions
    • Added Schur's Lemma puzzle. (minor)
• Gist
  • Other changes
    • Zoom-to-fit can now be selected during search. (minor)
    • Compiles under MSVC 2005 SP1 again. (minor, thanks to Alin Gherman)
  • Bug fixes
    • Changed keyboard shortcuts in Gist so that they work on all platforms: "Inspect" is now Ctrl+number of inspector, for "Inspect before fixpoint" press Alt in addition (on Mac OS, use the Command key instead of Ctrl). (minor)
• Gecode/FlatZinc
  • Additions
    • Added native support for the precedence constraint. (major)
    • Added native support for the no-overlap constraint (called diffn in MiniZinc/FlatZinc). (major)
    • Support indomain_middle and indomain_interval search annotation by replacing them with indomain_median and indomain_split, respectively. (minor, thanks to Håkan Kjellerstrand)
    • Added native support for link_set_to_booleans, global_cardinality_low_up_closed, and decreasing_bool. (minor)
  • Other changes
    • Adapted the MiniZinc declarations and the command line options for Gecode/FlatZinc to MiniZinc 1.3. The fz binary now works with the minizinc driver script. (minor)
  • Bug fixes
    • Re-enabled the global cardinality constraint in the FlatZinc interpreter. (minor, thanks to Håkan Kjellerstrand)
    • Fixed the MiniZinc definition for the circuit constraints to work with arbitrarily indexed arrays. (minor, thanks to Håkan Kjellerstrand)
• General
  • Additions
    • Added configure option –enable-small-codesize that results in slightly less efficient but more compact code being generated for non-debug builds. (minor, thanks to Ruben Zilibowitz)
  • Bug fixes
    • Fixed Makefile, now installation works when FlatZinc library is disabled. (minor, thanks to Martin Mann)

Changes in Version 3.5.0 (2011-02-01)

This release fixes serious bugs in parallel search, FlatZinc, fixes some DLL issues on Windows, adds support for FreeBSD, and adds STL-style iterators for arrays.

• Kernel
  • Additions
    • Added STL compatible iteration support for arrays (variable arrays, argument arrays, view arrays, and shared arrays). (major , contributed by Gregory Crosswhite)
• Search engines
  • Bug fixes
    • Fixed a serious bug in parallel search (took over a year to isolate the bug). (major, thanks to Denys Duchier, Chris Mears)
• Minimal modeling support
  • Bug fixes
    • Do not inline construction of linear, Boolean, and set expressions to avoid cross-DLL allocation/deallocation issues on Windows. (minor, thanks to Alexander Kleff)
• Gecode/FlatZinc
  • Other changes
    • Fixed the definitions of global_cardinality to work with MiniZinc 1.2 and newer, and added corresponding definitions of global_cardinality_closed and global_cardinality_low_up_closed. (major)
  • Bug fixes
    • Fixed incorrect posting of linear constraints with variable arrays of size one. (major, thanks to Roberto Castañeda Lozano)
• General
  • Additions
    • Gecode now compiles on FreeBSD. (minor, thanks to Peter Penchev)
    • Embed resource information into Gecode DLLs and EXEs on Windows. (major)
  • Other changes
    • Embed manifest into Gecode DLLs on Windows. (minor)

Changes in Version 3.4.2 (2010-10-09)

This release removes LDS from Gecode as it is patented in the US.

• Search engines
  • Removals
    • Removed limited discrepancy search (LDS) as it is patented in the US. (minor)
• Gecode/FlatZinc
  • Additions
    • Added support for binpacking constraint. (minor)

Changes in Version 3.4.1 (2010-10-08)

This release adds a new global constraint for binpacking (with extended example) and filter functions for branchers. The reference documentation has been cleaned up. In particular, information on how to obtain, install, and link Gecode has been expanded and moved to "Modeling and Programming with Gecode" (Section 2.6). Additionally, the release fixes some bugs and contains some performance improvements.

• Kernel
  • Other changes
    • Branching now honors filter functions, where variables are considered for branching only if the filter functions returns true (see "Modeling and Programming with Gecode" for details). (major, thanks to Felix Brandt)
    • Variable implementation views are now parametric with respect to variables but not variable implementations (see "Modeling and Programming with Gecode" for details). (minor)
    • Renamed the template class for variables defined by a variable implementation from Var to VarImpVar and re-added a class Var as base class for any variable type. (minor)
• Finite domain integers
  • Additions
    • Added a binpacking constraint and propagator. (major)
  • Bug fixes
    • Do not inline functions with variable arguments. (minor, thanks to Gustavo A. Gómez Farhat)
    • The reified dom constraint failed instead of setting the BoolVar to 0 when the minimum argument given was greater than the maximum. (minor, thanks to Kish Shen)
  • Performance improvements
    • Fixed sortedness constraint by replacing an algorithm that is linear in the width of the union of all domains with an algorithm that is quadratic in the number of variables. The previous algorithm crashed for domains with large values due to excessive memory use. (minor, thanks to Kish Shen)
    • Using ICL_DOM for binary linear equations with unit coefficients (such as x = y+3) is now implemented using the much more efficient binary equality propagator instead of the linear equation propagator (which has worst case exponential runtime). (minor)
• Scheduling constraints
  • Bug fixes
    • Fixed initialization for unary and cumulative edge-finding (just worked accidentally). (major, thanks to Roberto Castañeda Lozano)
• Minimal modeling support
  • Other changes
    • Added element expression for BoolVarArgs. (minor)
  • Bug fixes
    • Fixed memory allocation for non-linear expressions and made the LinExpr constructor explicit for non-linear expressions (previously the automatic cast from integers to LinExpr was sometimes ambiguous). (minor)
• Script commandline driver
  • Additions
    • Added a class InstanceOptions that takes one additional string argument. (minor)
• Range and value iterators
  • Performance improvements
    • Reimplemented n-ary union, minus, and cache iterators for much better efficiency. (minor)
• Example scripts
  • Additions
    • Added a binpacking model using the binpacking constraint and CDBF (complete decreasing best fit) search. (major)
• Gist
  • Other changes
    • Only center node on double-click if it was undetermined (otherwise inspecting several nodes becomes slightly annoying). (minor)
  • Performance improvements
    • Saved some memory for each node in Gist (one pointer per node, two integers per inner node, and some additional memory on 64 bit platforms due to optimizing alignment), and speeded up deallocation of the tree (e.g. when resetting or closing Gist). (minor)
• Gecode/FlatZinc
  • Additions
    • Added support for global_cardinality_low_up. (minor)
  • Performance improvements
    • The FlatZinc parser now uses hash maps instead of STL maps, which significantly increases parsing performance for larger files. Furthermore, a single symbol table is used, also increasing performance and allowing to report duplicate symbol errors, which were previously ignored. (minor)
• General
  • Documentation fixes
    • Removed obsolete Glossary in reference documentation. (minor)

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 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)

Changes in Version 3.3.1 (2010-04-09)

This release adds many new features to Gist, fixes two major bugs in extensional constraints, and has some more cleanups to comply with the first release of the "Modeling and Programming with Gecode" document. And, as always some small fixes and cleanups.

• Kernel
  • Other changes
    • The (unused and unusable) CopiedHandle have been removed. (minor)
  • Bug fixes
    • Fixed bug in VarArray::resize function that occurred when shrinking variable arrays. (minor)
• Finite domain integers
  • Bug fixes
    • Fixed extensional constraint with finite automata for very unlikely (but apparantely possible) border case. (major)
    • The extensional constraints with tuple sets could cause crashes when used with parallel search. (major)
• Finite integer sets
  • Removals
    • Removed Set::IntSetPropagator and Set::IntSetRePropagator because they are subsumed by the MixBinaryPropagator patterns. (minor)
  • Bug fixes
    • Fixed channeling between set and integer variables which did not propagate enough. (minor)
• Scheduling constraints
  • Other changes
    • Tasks in unary scheduling constraints may now have processing times of 0. (minor)
  • Bug fixes
    • The unary scheduling propagator with optional tasks missed some propagation sometimes. (minor)
• Script commandline driver
  • Additions
    • You can now register Gist inspectors in the driver options. (minor)
• Example scripts
  • Additions
    • Added Gist inspectors for the Knights and Queens examples. (minor)
• Gist
  • Additions
    • In addition to inspectors, you can now also register comparators, which can be used to compare two nodes in the tree. In combination with the option to compare before computing a fixpoint of the second node, this lets you see what exactly was modified by a branching. (major)
    • Gist can now stop exploration after all alternatives of a certain branching are exhausted. This feature can be turned on by posting a special branching using the Gist::stopBranch post function. Gist will then stop whenever that special branching becomes active. (major)
    • Added inspection of nodes before fixpoint computation. (minor)
    • Nodes can now be bookmarked. (minor)
    • Added inspectors that react whenever a node is selected. (minor)
  • Bug fixes
    • Missing export declarations prevented embedding Gist as a widget. There is now example code for embedding Gist in the directory gecode/gist/standalone-example. (minor)
    • Fixed a bug where sometimes clicking on a node would select a different node. (minor)
  • Performance improvements
    • Scrolling and zooming have been reimplemented. The new implementation is more efficient and works around problems that occurred with large trees on some platforms. Zooming is now more intuitive, keeping the current center centered. You can now also zoom by pressing shift while using the mouse wheel. (major)
• Gecode/FlatZinc
  • Other changes
    • Comply with MiniZinc 1.1. String literals are not allowed any longer except in annotations, the solver outputs UNKNOWN and UNSATISFIABLE instead of just ==========, and the global constraints all_equal, decreasing_int, and decreasing_bool are supported. (minor)
  • Performance improvements
    • Variables that do not have output annotations are now garbage collected during copying. (minor)
    • When using sums of Boolean variables using bool2int in MiniZinc, the FlatZinc interpreter now posts the more efficient propagators that work directly on the Boolean variables. (minor)
• General
  • Documentation fixes
    • Removed many small documentation quirks. (minor)

Changes in Version 3.3.0 (2010-03-15)

This release provides some fixes, some performance improvements for domain propagators, and quite some clean ups how propagators and advisors report their status to the kernel. Many of these clean ups are essential to make it easier to program propagators and branchers with Gecode.

• Kernel
  • Additions
    • Advisors now can force its propagator to be rescheduled, including recomputation of its cost used for scheduling (normally, a propagator is only rescheduled if its modification event delta changes). An advisor can signal forceful rescheduling by returning ES_NOFIX_FORCE or returning the return value of ES_NOFIX_FORCE_DISPOSE. Read the forthcoming "Modeling and Programming with Gecode" for details. (minor)
  • Other changes
    • The failure macros for posting GECODE_ES_FAIL and GECODE_ME_FAIL now only accept a single argument and assume that "home" actually refers to the home space. Read the forthcoming "Modeling and Programming with Gecode" for details. (minor)
    • The functions ES_FIX_PARTIAL, ES_NOFIX_PARTIAL, ES_FIX_DISPOSE, and ES_NOFIX_DISPOSE are now member of Space. Read the forthcoming "Modeling and Programming with Gecode" for details. (minor)
    • The function ES_SUBSUMED now is a member of Space and accepts a propagator as its single argument. The variant with a size as the second argument is available as ES_SUBSUMED_DISPOSED but use is highly discouraged. Read the forthcoming "Modeling and Programming with Gecode" for details. (minor)
    • The functions ES_SUBSUMED_FIX and ES_SUBSUMED_NOFIX for advisors have been renamed to ES_FIX_DISPOSE and ES_NOFIX_DISPOSE. Read the forthcoming "Modeling and Programming with Gecode" for details. (minor)
  • Bug fixes
    • ViewValBrancher with random value selection did not produce a random sequence of values. (minor)
• Finite domain integers
  • Additions
    • Integer sets (IntSet) now have a in member function for testing whether an integer is included. (minor)
  • Other changes
    • Patterns for reified propagators have been moved to the Gecode::Int namespace. (minor)
  • Performance improvements
    • Considerably improved performance and memory consumption of the DFA-based extensional constraint (regular). (major)
• Finite integer sets
  • Other changes
    • Patterns for set propagators have been moved to the Gecode::Set namespace. (minor)
• Minimal modeling support
  • Additions
    • Linear expressions can freely mix integer and Boolean variables and support construction from variable arrays via a sum function. (minor)
  • Removals
    • Removed special cases for posting linear and Boolean expressions consisting of a single variable only (was highly ambigious). (minor)
• Support algorithms and datastructures
  • Performance improvements
    • Changed to single, really efficient bitset implementation used allover the system. (major)
• Gist
  • Bug fixes
    • Avoid inter-thread call to QWidget::update, which apparently causes a slight memory leak (and warning messages on stderr) on Mac OS. (minor)
• Gecode/FlatZinc
  • Other changes
    • The FlatZinc interpreter can now be extended by plugins that implement custom search strategies. The plugins are implemented as dynamically loaded libraries using the Qt plugin mechanism. An example can be found in the directory gecode/flatzinc/exampleplugin. (minor)
    • The index of the variable used for optimization is now available in the FlatZincSpace class. (minor)
    • Added command line option -print, which controls whether all solutions are printed or only the last one that is found, and -search, to choose between branch-and-bound and restart optimization. (minor)
    • The FlatZinc library can now parse a FlatZinc model into any subclass of FlatZincSpace, so that custom extensions can be built. Annotations on the solve item can now be accessed from the returned FlatZincSpace, so that additional search strategies can be implemented. (minor)
  • Bug fixes
    • The FlatZinc interpreter ignored the -c-d and -a-d command line switches when used with Gist. (minor)
• General
  • Bug fixes
    • Configure now prepend options to the CXXFLAGS and CFLAGS variables instead of appending them. That way, defining the variables when invoking configure overrides the choices configure makes (e.g. overriding the default -O3 with -O2). (minor)

Changes in Version 3.2.2 (2009-11-30)

This release adds the sequence constraint (contributed by David Rijsman, Quintiq) and has as always some small additions and fixes.

• Kernel
  • Bug fixes
    • Added missing assignment operator for space-based allocators for STL data structures. (minor, thanks to Gustavo Gutierrez)
• Search engines
  • Bug fixes
    • The memory reported could be sometimes too low (the previous fix for 3.2.0 did not fix it for branch and bound search). (minor)
• Finite domain integers
  • Additions
    • Added sequence constraint. (major , contributed by David Rijsman)
  • Bug fixes
    • The global cardinality (count) constraint now accepts unsorted arrays of values. It previously propagated incorrectly if the array was not sorted. (minor, thanks to Alberto Delgado)
    • Fixed bug in the ICL_VAL propagator for global cardinality. (minor)
    • Subscription to constant views did not honor the flag to avoid processing. (minor)
• Finite integer sets
  • Bug fixes
    • Subscription to constant views did not honor the flag to avoid processing (did not occur in practice). (minor)
• Script commandline driver
  • Additions
    • Report if search engine has been stopped. (minor)
• Range and value iterators
  • Other changes
    • Renamed test for subset or disjointness of range iterators to "compare". (minor)
• Example scripts
  • Additions
    • Added car sequencing example (problem 1 in CSPLib). Uses the new sequence-constraint. (minor)
• Gecode/FlatZinc
  • Bug fixes
    • Support search annotations with constants in the variable arrays. (minor, thanks to Håkan Kjellerstrand)
    • The set_in and set_in_reif constraints were buggy when used with Boolean variables (which are usually not generated by mzn2fzn so that the issue probably does not occur in practice). (minor)
    • The global_cardinality constraint was not completely compatible with the MiniZinc semantics. It would constrain values not mentioned in the array to have zero occurrences, while in MiniZinc they are unrestricted. (minor)
    • Element constraints in reified positions produced an error in the mzn2fzn translation. (major, thanks to Håkan Kjellerstrand)

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 Hide 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 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 "Modeling 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 Hide 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).

Changes in Version 3.2.0 (2009-10-05)

This release has some important bug fixes (in particular for global cardinality aka count), the documentation has been improved (worked around some issues with generation by doxygen), integrates the FlatZinc interpreter into the Gecode source tree, provides propagators for disjunctive scheduling (experimental), and lots of small changes and fixes. For more consistent names, branchings are branchers now and branching descriptions are choices (this you might have to adapt to).

• Kernel
  • Other changes
    • A branching is now a brancher and a branching description is now a choice. (major) Details Hide details
      Classes and member functions have been renamed accordingly. The change is necessary due to proper explanation in the forthcoming "Programming with Gecode".
• Search engines
  • Other changes
    • Optimized thread creation by thread pools, now the creation and deletion of arbitrarily many parallel search engines also works for platforms using pthreads (Linux and MacOS). (minor)
    • Path for search provides top and empty methods. (minor, thanks to Vincent Barichard)
  • Bug fixes
    • The memory reported could be sometimes too low (that could only happen when an advisor allocates memory which they do only now). (minor)
    • Compiles again if no threads available. (minor)
• Finite domain integers
  • Additions
    • Added regret_min and regret_max for IntVar and BoolVar (they were only available for IntView). (minor, thanks to Kish Shen)
    • Added branch and assign for single integer and Boolean variable. (minor)
    • Added element constraints for Matrix arrays. (minor, thanks to Håkan Kjellerstrand)
  • Other changes
    • The element constraint now computes more accurate variable bounds when being posted (to avoid arithmetic overflow in naive models). (minor)
    • The element constraint now throws an exception if used with an empty array. (minor)
    • Moved cumulatives to the new scheduling library. (minor)
    • Moved circuit to the new graph library. (minor)
  • Bug fixes
    • Slightly improved strength of the division propagator. (minor, thanks to Jan Kelbel)
    • Fixed serious bug in the bounds propagator for global cardinality. (major)
  • Performance improvements
    • Extensional propagators using DFAs or REGs (aka regular) use a more compact state representation but create their state more eagerly. That can improve performance considerably (twice as fast) at a slight increase in memory. (minor, thanks to George Katsirelos, Nina Narodytska)
    • Optimized n-ary disjunction and conjunction and the clause constraint. (minor)
    • Linear constraints over Boolean variables with unit coefficients (aka Boolean cardinality constraints) have been reimplemented. Less memory (minus 30%) and more speed. For example, BIBD runs 10% faster now. (minor)
• Finite integer sets
  • Additions
    • Added branch and assign for single set variable. (minor)
    • Added element constraints for Matrix arrays. (minor, thanks to Håkan Kjellerstrand)
  • Other changes
    • The element constraint with an integer index variable now throws an exception if used with an empty array. (minor)
• Scheduling constraints
  • Additions
    • Added propagators for disjunctive scheduling (unary resource scheduling). This is still experimental as the propagators are not yet optimized and branching and modelling support is not yet available. (major)
    • Added a new module for scheduling. To use scheduling constraints, you have to include <gecode/scheduling.hh> and link against the scheduling library. (minor)
• Graph constraints
  • Additions
    • Cost-based variants for circuit added. (minor)
    • Added a new module for graph constraints. To use graph constraints, you have to include <gecode/graph.hh> and link against the graph library. (minor)
• Minimal modeling support
  • Additions
    • Added element constraints for Matrix interface to arrays. (minor, thanks to Håkan Kjellerstrand)
• Script commandline driver
  • Additions
    • Added new standard option for options called symmetry. (minor)
  • Other changes
    • The driver takes copies of all string values passed top it. (minor, thanks to Luca Di Gaspero)
• Support algorithms and datastructures
  • Other changes
    • No longer depend on availability of timersub. (minor, thanks to Alexandre Fayolle)
• Example scripts
  • Additions
    • Added branching following Warnsdorff's heuristic for Knights. (minor)
  • Other changes
    • Examples now use the symmetry-option for symmetry-breaking. (minor) Details Hide details
      The affected examples are:

      • BlackHole
      • EFPA
      • Pentominoes
      • SteelMill
  • Bug fixes
    • Fixed wrong symmetry breaking for TSP. (minor, thanks to Geoffrey Chu)
    • Fixed zero cost edges in TSP examples. (minor)
• Gist
  • Other changes
    • The Gist console now has a toolbar that provides buttons to clear the text as well as to configure the console window to stay on top of Gist. Furthermore, after adding output, the console now automatically scrolls to the bottom. (minor)
  • Bug fixes
    • Gist now places clones also on the leftmost branch during search. (minor)
• Gecode/FlatZinc
  • Additions
    • The Gecode interpreter for the FlatZinc language is now part of the main Gecode source tree. (major)
• General
  • Other changes
    • Compiles with MSVC 2005 again. (minor, thanks to David Rijsman)
  • Bug fixes
    • The configure script checked for Qt 4.2, although Gist requires at least Qt 4.3. (minor)
  • Documentation fixes
    • Cleaned up the generated reference documentation, and introduced a number of workarounds for issues in doxygen. In particular, the documentation for linear constraints over Boolean variables and for the thread abstractions is now generated properly. (major)
    • Mention that also grep is needed for building Gecode. (minor, thanks to Vivian De Smedt)

Changes in Version 3.1.0 (2009-05-20)

This release introduces parallel search, features improved memory management (can double efficiency on MacOS X), and provides a reusable command line driver upon popular request. And, of course, some this and that.

• Kernel
  • Performance improvements
    • Cache memory blocks from deleted spaces. This hardly increases peak memory consumption. It improves performance on Windows and Linux only by up to 5%, but on MacOS by 50% in some cases (this improvement is absolutely essential for parallel execution). (major)
• Search engines
  • Additions
    • Added parallel search engines for DFS, BAB, and Restart (but not LDS). Please make sure to read the section "Parallel search" in "Modeling with Gecode". (major) Details Hide details
      Parallel search is still experimental: creating and destroying a large number (more than 1000) of search engines (and hence a large number of threads) might raise exceptions on operating systems using pthreads as thread implementation. This will be fixed in a future release by using thread pools.
  • Other changes
    • The stop function of stop objects now also takes a second argument of type Search::Options. This is in particular useful for decisions that involve the number of threads used for search. (minor)
• Finite domain integers
  • Additions
    • Added a wait propagator: executes a function when a variable (or variables) become(s) assigned. (minor)
  • Other changes
    • The INT_VAL_MED value selection now consistently selects the greatest element in the domain not greater than the median. (minor)
• Finite integer sets
  • Additions
    • Added a wait propagator: executes a function when a variable (or variables) become(s) assigned. (minor)
  • Other changes
    • The set constraint sequentialUnion has been renamed to sequence. (minor)
• Script commandline driver
  • Additions
    • Added a new module "driver" as a commandline driver for scripts. This is due to popular request: most people have been using the support functionality for examples anyway. This function is now wrapped into a proper module (and Example is now called Script to be more general). See "Modeling with Gecode" for documentation. (major)
  • Other changes
    • If Gist is not available, -mode gist is the same as -mode solution. Invocation with -help also prints information about how Gecode has been configured. (minor)
• Support algorithms and datastructures
  • Additions
    • Added a tiny portable thread package specifically tailored to the needs for parallel search. Unfortunately, other portable thread packages have just too many issues. (minor)
    • Support::quicksort and Support::insertion support using the less than operator for the sort order by leaving out the comparator object. (minor)
• Example scripts
  • Additions
    • Added new example for equidistant frequency permutation arrays (EFPA). (minor)
  • Other changes
    • The parameters of the Hamming Codes example are now configurable through command line options (instead of hard-coded). (minor)
• Gist
  • Other changes
    • Small user interface changes: disable search from hidden nodes, add depth information to status bar, and add statistics for subtrees (available from the node context menu and the Node menu). (minor)
    • Easily add multiple inspectors to Gist. Inspectors are not exclusive any longer, you can select any combination of them to respond to clicks or solutions simultaneously. (minor)
  • Bug fixes
    • Fixed a dead lock that could occur when closing the Gist main window while search is still running. (minor)
    • The inspectors are finalized before Gist exits. This fixes a bug where (at least on Mac OS) some memory was not freed in the correct order. (minor)
    • Gist now correctly centers the current node after search has finished. (minor)

Changes in Version 3.0.2 (2009-03-26)

This is a bug fix release fixing two more embarrassing bugs. However, this time we redesigned our tests carefully such that they cover all changes and optimizations done for the transition from 2.2.0 to 3.0.*. Please update asap.

• Finite domain integers
  • Bug fixes
    • Fixed bug in optimization of extensional constraints with DFAs (hard to reproduce, almost impossible). (major)
  • Performance improvements
    • Reoptimized element with integer values and created bizarre testcases. (minor)
• Minimal modeling support
  • Bug fixes
    • Fixed bug in posting of Boolean expressions including reified linear expressions. Again, that escaped our testsuite (also fixed). (major, thanks to Gustavo Guiterrez)
• Example scripts
  • Bug fixes
    • The radiotherapy example was missing in the Makefile. (minor, thanks to Håkan Kjellerstrand)
• Gist
  • Other changes
    • A separator is printed between solutions in the TextInspector. (minor)

Changes in Version 3.0.1 (2009-03-24)

This is a bug fix release fixing two embarrassing bugs that were not caught by our test infrastructure. Please update asap.

• Finite domain integers
  • Bug fixes
    • Fixed bug in element with integer values. (major, thanks to Vincent Barichard)
    • IntSetArgs no longer inherit from PrimArgArray, which was wrong as IntSet is no primitive type and hence does not support vararg initializers. (minor)
    • Fixed bug in reified Boolean linear constraints (an optimization is currently disabled and will be active in the next release: the optimization was incorrect and was never tested). (major, thanks to Alberto Delgado)
• Example scripts
  • Additions
    • Added new example for Radiotherapy. (minor)
  • Bug fixes
    • The examples now pass the c-d and a-d command line options correctly to Gist. (minor)
    • The Steel Mill Slab Design example had two bugs in the search heuristic and a missing redundant constraint. (minor, thanks to Chris Mears)

Changes in Version 3.0.0 (2009-03-13)

This release is a major consolidation release: interfaces have been cleaned up (consistent parameter passing, consistent naming, simpler Gist interface, namespaces for operator overloading); some functionality has been extended (propagators can be non-monotonic; branchings support tie-breaking and random variable and value selection); some functionality that did not meet our quality goals has been removed (complete set variables, reflection); usage has been simplified (auto-linking on Windows, more commonly used filename extensions); important aspects have been optimized (memory management, memory usage and efficiency on 64bit machines). These cleanups were in particular necessary to make Gecode easier to document (this release is the first to be accompanied by tutorial documentation explaining how to model with Gecode).

Apart from that, many small fixes and additions. Please see below for the details.

As the interfaces have changed considerably, please consult How to Change to Gecode 3.0.0.

• Kernel
  • Additions
    • Integrated space and region-based allocators that work with STL classes. (minor , contributed by Filip Konvicka)
    • Added support for synchronized execution during branching (executes a function). (minor, thanks to Denys Duchier)
  • Removals
    • View and value assignments have been removed as they now can be expressed by view and value branchings. (major)
  • Other changes
    • The specification of propagation cost has changed. It now must be computed by the static member functions of the class Gecode::PropCost. (major)
    • The clone operation on spaces is now const. (minor)
    • Introduced CopiedHandle as a new base class for SharedHandle. (minor) Details Hide details
      A copied handle provides access to an object that is used by entities in a space, and that is copied when then space is copied. This abstraction can be used e.g. to pass information between different entities in a space, such as between propagators and branchings.
    • Made macros semicolon-safe. (minor, thanks to Denys Duchier)
    • The index structure for variable dependencies is now implemented using integers instead of pointers, saving memory on 64 bit machines. (minor) Details Hide details
      For example, the index structure of integer variables is now 40% smaller, for Boolean variables (which have the smallest possible index structure) we still save 16%.
    • Gecode now supports weakly monotonic propagators. (major) Details Hide details
      A weakly monotonic propagator must only be able to decide for assignments whether they are solutions or not (which is a very natural property as it means the propagator must be a correct implementation of a constraint). Otherwise, the propagator does not have to be monotonic, it can even be indeterministic.
      Weakly monotonic but not monotonic propagators must notify a space about their existence: if a weakly monotonic propagator is created, it must execute "home.notice(*this,AP_WEAKLY)"; if it is disposed, it must execute "home.ignore(*this,AP_WEAKLY)".
    • The functions force and unforce of an actor to force disposal have been removed. (minor) Details Hide details
      Now, the new interface based on notice and ignore using actor properties must be used instead. So, instead of "force(home)", write "home.notice(*this,AP_DISPOSE)" and, instead of "unforce(home)", write "home.ignore(*this,AP_DISPOSE)".
    • The home space is now also passed to the cost function of a propagator. (minor)
    • All functions for checking sharing for arrays (same, shared, unique) require a space argument (for memory management). (minor)
    • The description() member function of a space is not any longer const: it can be called at most once. (minor)
    • The constrain method used for best solution search must be virtual and takes an argument of type const Space& rather than Space* as argument. (major)
    • View and value branchings have been completely reimplemented to support tie-breaking and state (for randomized selection). (major)
  • Bug fixes
    • Updating of a council of advisors crashed if a propagator has no advisors (as we had no example of this kind of propagators). (major, thanks to Vincent Barichard)
• Search engines
  • Additions
    • The search engines now collect statistics for the number of nodes visited and the maximum depth of the search tree. The information for number of clone and commit operations has been removed as it was too confusing. (minor)
    • Search engines have been completely reimplemented. (major)
• Finite domain integers
  • Additions
    • Added support for synchronized execution that executes a function or a static member function when a Boolean variable becomes assigned (called when). (minor)
    • Integer sets can now be initialized from integer argument arrays. (minor)
    • Domain constraints (dom) also accept integers now. (minor)
    • Added a Boolean clause constraint that supports conjunction and disjunction of both positive and negative variables. (minor)
  • Removals
    • Support for PropKind has been removed for all but extensional constraints. (minor)
  • Other changes
    • A TupleSet must be finalized before an extensional constraint can be posted using it. (minor)
    • Make the variable deltas generated for minus_r more meaningful if possible. (minor, thanks to David Rijsman)
    • TupleSet now accepts duplicate tuples. (minor)
    • Renamed size() to ranges() for IntSet (returning the number of ranges). Added a size() and width() function that return the size and width of the set respectively. (minor)
    • Tie-breaking and random selection for branch is now supported. (major)
    • The variable selection INT_VAR_DEGREE_MIN and INT_VAR_DEGREE_MAX do not have tiebreaking with smallest domain size built in. (minor) Details Hide details
      The old behavior can be reclaimed by explicit tiebreaking, for example replace INT_VAR_DEGREE_MAX by tiebreak(INT_VAR_DEGREE_MAX,INT_VAR_SIZE_MIN).
  • Bug fixes
    • Fixed bug in domain consistent min and max propagators. (minor)
    • Fixed off-by-one bug in extensional for DFAs. (major, thanks to Roland Yap Hock Chuan)
    • The binary min and max propagators did not do all pruning they should do. (minor, thanks to Jonathan Cederberg) Details Hide details
      Given the constraint x = max(y,z) with the store {x->{1,2,3}, y->{1,2}, z->{3}}, propagation did not yield any new information (now it gives the correct result {x->{3}, y->{1,2}, z->{3}}).
  • Performance improvements
    • Integrated an efficient implementation of reified linear constraints over Boolean variables. (major , contributed by Tias Guns)
    • Now n-ary Boolean disjunction and conjunction are constant time (rather than linear time, as before), even when a variable for the result is used. (minor)
    • The incremental extensional propagator for tuplesets uses less memory (around 25%) and reports its size correctly. (minor)
    • The element propagator for integer arrays now chooses datastructures according to and the elements of the array. (minor) Details Hide details
      This can save more than 80% memory on a 64 bit machine, and up to 75% on a 32 bit machine. In common cases, one can expect a reduction by at least 50%.
    • The regular propagator now chooses datastructures according to the size of the DFA. This can save up to 80% memory on a 64 bit machine, and still up to 50% on a 32 bit machine. (minor)
    • Simpler and more efficient memory management for element propagators (integer arrays). (minor)
• Finite integer sets
  • Additions
    • More set branching strategies have been added (for instance random variable and value selection), as well as set assignment. (minor)
    • Added reified propagators constraining an integer variable to be the minimum or maximum element of a set variable. (minor, thanks to Denys Duchier)
  • Removals
    • Removed automatically generated set projectors, they will come back eventually. This makes no change to the available functionality for set variables. (minor)
  • Other changes
    • Element and convexity constraints on set variables have a more uniform interface, and the match constrained has been renamed to channel. (minor)
    • Reorganized the internal data structures of set variables so that each variable takes up 8 bytes less memory on 64 bit machines. (minor)
    • The values for variable and value selection for branching have been made consistent and extended. (major) Details Hide details
      The following values have been renamed:

      • SET_VAR_MIN_CARD -> SET_VAR_SIZE_MIN
      • SET_VAR_MAX_CARD -> SET_VAR_SIZE_MAX
      • SET_VAR_MIN_UNKNOWN_ELEM -> SET_VAR_MIN_MIN
      • SET_VAR_MAX_UNKNOWN_ELEM -> SET_VAR_MAX_MAX
      • SET_VAL_MIN -> SET_VAL_MIN_INC
      • SET_VAL_MAX -> SET_VAL_MAX_INC

      Tie-breaking and random selection is now supported.
  • Bug fixes
    • Fixed bug in creation of set variables. (minor, thanks to Stefano Gualandi)
    • Fixed constructors for set variables. They now throw proper exceptions when trying to create empty variable domains. (minor, thanks to Denys Duchier)
• Finite integer sets with complete representation
  • Removals
    • Complete sets have been removed (just not good enough). (major)
• Minimal modeling support
  • Additions
    • Added MinimizeSpace and MaximizeSpace classes for cost-based optimization (requires implementing a cost function returning an integer cost variable). Optimization can now be implemented by inheriting from these classes rather than from Space and by implementing a cost function. (minor)
  • Other changes
    • LinExpr, LinRel, BoolExpr are now part of the Gecode namespace rather than Gecode::MiniModel (to support operator resolution). (minor)
    • The Matrix class is now in the Gecode namespace (and not in Gecode::MiniModel). (minor)
  • Performance improvements
    • Posting constraints according to Boolean expressions now uses a negation normalform and by this avoids any propagator for negation and uses fewer propagators due to the new clause constraint. (minor)
• Range and value iterators
  • Bug fixes
    • Fixed init method of SingletonAppend range iterator. (minor, thanks to Stefano Gualandi)
  • Documentation fixes
    • Mention that arrays for Iter::Values::Arrays must be sorted. (minor, thanks to Anden Blah, Morten Boysen)
• Support algorithms and datastructures
  • Removals
    • PQueue has been removed (too specialized to be reused anyway). (minor)
    • GECODE_AUTOARRAY has been removed. Use a Region for memory management instead. (minor)
    • GECODE_AUTOSTACK and SentinelStack has been removed. Use StaticStack instead. (minor)
  • Bug fixes
    • Sorting (quicksort and insertion) require strict orders and now work with arrays of more than 2^32 elements. (minor, thanks to Michal Dobrogost)
• Example scripts
  • Additions
    • New example: the steel mill slab design problem (Problem 38 in <a href="http://csplib.org">CSPLib</a>). (minor) Details Hide details
      The model used is from Gargani and Refalo, "An efficient model and strategy for the steel mill slab design problem.", CP 2007. The symmetry-breaking search is from Van Hentenryck and Michel, "The Steel Mill Slab Design Problem Revisited", CPAIOR 2008.
  • Bug fixes
    • A bug in the independent set example has been fixed (most edges were ignored). (minor, thanks to Stefano Gualandi)
    • Fixed a bug in the extensional propagation-version of the domino example. (minor)
  • Performance improvements
    • Improved branching for Nonogram examples. (minor, thanks to Håkan Kjellerstrand)
• Systematic tests
  • Additions
    • Tests for testing claims of bounds(Z) and bounds(D) consistency. These tests would have found the bug in the binary min and max propagators. (minor) Details Hide details
      An integer test can enable these new tests by setting the contest member to CTL_BOUNDS_Z or CTL_BOUNDS_D. For domain-consistency propagators the contest member is set automatically to CTL_DOMAIN. If no consistency-testing should be done, contest should be set to CTL_NONE.
• Gist
  • Additions
    • Added inspectors that react on every solution instead of a double click. (minor)
  • Other changes
    • Gist now takes an optional argument specifying options for the search, including the inspectors to be used. The Qt interface has been cleaned up, so that Gist is easier to extend. (minor)
• General
  • Additions
    • For the Microsoft compiler, auto-link information is added during compilation. (minor) Details Hide details
      That is, by including Gecode headers during compilation the right libraries will be found automatically during linking. To simplify development and deployment, the libraries (and DLLs) encode version, platform, and build type (release or debug) in their filename.
  • Removals
    • All support for reflection has been removed: not clean enough, not powerful enough, too difficult, and too much trouble. (major)
  • Other changes
    • All operators are now in their correct namespace. (major, thanks to Max)
    • Changed naming scheme for files. (major) Details Hide details
      All files with extension .cc have been renamed to .cpp, and .icc has become .hpp. This avoids conflicts as .icc is typically used for other file types. All include directives are now specified using \<...> notation instead of "...", so that Gecode headers do not clutter the include namespace of a client program.
    • Now everything is passed as reference (Space, Propagator, ModEventDelta, Advisor, Branching, and BranchingDesc). (major) Details Hide details
      The reason for this massive change is to be more C++ compliant and make the interfaces more consistent (at some places things were passed as references and at other places as pointers, for no obvious and explainable reason). Routines that create objects rather than pass them (such as copy, clone, or description) still return a pointer to an object (so that it can actually be deleted!).
      You will have to rewrite your models and other programs using Gecode. For models this is easy enough:

      • Replace "(Space* home" by "(Space\& home".
      • Replace "home-\>" by "home.".
      • Replace "(this" by "(*this".

      That should do the trick for 99% of the models.
      For the other changes, just lookout for the changes in types and that "this" becomes "*this" now.
    • The memory management has been completely reworked. (major) Details Hide details
      It is now more robust, more portable (does not use alloca any longer), more efficient, fits C++ better and is much easier too understand. There are now three memory areas: a single heap, spaces, and regions. Heap and spaces are as before. A region (an object of class Region) is a simple and very efficient memory manager for temporary memory managed in a stack fashion. These three memory managers provide uniform operations for allocation (alloc), deallocation (free), and reallocation (realloc). These operations use constructors, destructors, and assignment operators as required by C++ and are implemented with efficient specializations for basic data types.
  • Bug fixes
    • Output operators (<<) now respect formatting width and work with output streams using arbitrary character types. (minor, thanks to Chris Mears)

Changes in Version 2.2.0 (2008-08-25)

This release adds many domain consistent propagators for arithmetic constraints and fixes a number of bugs. Some of these bugs fixed are potentially serious, in particular as they occur very seldom. Please change to 2.2.0 as soon as possible (in particular if you are using the 64bit Microsoft Visual C++ compiler). And, of course, the usual small fixes and changes.

• Kernel
  • Removals
    • Removed ViewTuple. Just not useful enough... (minor)
  • Other changes
    • Cleaned up Reflection::Var type, overloading did not conform to the C++ standard. (minor)
  • Bug fixes
    • Fixed a bug in the memory alignment on Windows 64bit (very hard to reproduce). (major)
    • Fixed bug that could potentially have affected certain staged propagators. (minor)
    • Generated variable stubs were wrong (could only be observed for new variable types). (major, thanks to Filip Konvicka)
  • Documentation fixes
    • Fixed explanation of ES_FIX and ES_NOFIX for advisors (description was mixed up). (minor, thanks to David Rijsman)
• Finite domain integers
  • Additions
    • The attempt to access the value of an unassigned integer or Boolean variable (IntVar or BoolVar) throws an exception now. (minor, thanks to Raphael Reischuk)
    • Added bounds consistent division/modulo propagator. (minor)
    • The channel constraint now comes in a version that allows to specify offsets to the array indices. (minor)
    • Added domain consistent multiplication propagator. (minor)
    • Added domain consistent minimum (min) and maximum (max) propagators. (minor)
    • Added domain consistent square root propagator (sqrt). (minor)
    • Added domain consistent squaring propagator (sqr). (minor)
    • Added reified propagators for relations over Boolean variables. (minor)
  • Other changes
    • All functional linear and arithmetic constraints now put sharp bounds on the output variable (eases interfacing to modelling languages). (minor)
  • Bug fixes
    • Fixed a bug in the domain consistent distinct propagator that would cause a stack overflow under rare circumstances. (major)
    • Fixed bug for domain-consistent distinct that never occurred in practice. (minor)
    • Cumulatives did not do all the pruning it should do. (minor, thanks to David Rijsman)
    • Fixed bug in element with IntArgs and sharing between the two IntVars. (minor)
    • Fixed bug in sqrt. (minor, thanks to Jaroslav Mlejnek)
    • Fixed bug in ValSplitMin::branchingSpec. (minor, thanks to David Rijsman)
  • Documentation fixes
    • Added documentation for domain consistent absolute value (abs) propagator. (minor)
• Finite integer sets
  • Other changes
    • The set selection constraints are now called element. (minor)
  • Bug fixes
    • The ternary intersection propagator was incorrect if any of the sets had a maximum cardinality of Set::Limits::card. (major)
• Example scripts
  • Removals
    • Example-based support for SAC (singleton arc consistency) has been removed. Might be reintroduced later in a more general fashion. (minor)
• General
  • Additions
    • Added configure options for adding a prefix and a suffix to the names of the compiled libraries. (minor)
    • The Makefile has a new target, check, which performs a minimal integrity check using some tests from the test suite. (minor)
  • Other changes
    • The configure script now always uses the Microsoft compiler on Windows. Use the CC and CXX environment variables to override this if you want to use gcc. (minor)

Changes in Version 2.1.1 (2008-03-06)

This is a bugfix release.

• Kernel
  • Bug fixes
    • The generated med_updated function was incorrect, resulting in potential crashes of programs that use SetVars. (major)
    • Made the constructor of Reflection::Var explicit, otherwise overloading for output stream operators does not work as expected. (minor)
• Finite domain integers
  • Bug fixes
    • Non-shared copying of dfa was broken (matters only for parallel execution). (minor)
• Finite integer sets with complete representation
  • Documentation fixes
    • The CpltSet variables are now in the correct documentation group. (minor)
• Gist
  • Bug fixes
    • Fixed redraw artefacts on Windows. (minor)
• General
  • Bug fixes
    • Fixed boost serialization. (minor)

Changes in Version 2.1.0 (2008-02-29)

This release makes two essential contributions: a partly reimplemented kernel that is faster, is simpler, and uses less memory and lots of small and not so small fixes. This release is the first release where really everything that we can test (rather than everything that we initially believed to matter) has been systematically tested. So, better switch now to 2.1.0!

Apart from that, the value range for variables has been increased (basically, 32 bits minus three values, so that is 32 bits), the reflection API is now fully functional and no longer considered experimental, and we have the usual small additions.

• Kernel
  • Additions
    • A generic variable class has been added that can be used for interfacing. It can store arbitrary Gecode variables (e.g. IntVar and SetVar), and cast them back using a run-time type check. The update, reflection, and output operations are implemented through the reflection registry. (minor)
  • Other changes
    • Cleaned up reflection. Unreflection is now part of the kernel instead of the serialization library. Branchings now provide a human-readable description of a BranchingDesc. The name function of a Propagator has been renamed to ati (actor type identifier). All reflection is now const where possible. Unreflection of variables now checks dynamically that the variable types match. Unreflection of propagators checks the number of arguments. A tutorial-style section on reflection has been added to the documentation. (minor)
    • Only stable and non-failed spaces can be cloned, otherwise Space::clone raises an exception. This makes cloning and propagation fully orthogonal. To emulate the old behavior, just execute Space::status before Space::clone. (major)
    • The number of propagators and branchings can be accurately retrieved from both failed and non-stable spaces. (minor)
    • Views and variables do not any longer reveal whether they have been modified: this feature committed the kernel to a particular implementation which might not be available in the future. (minor)
    • The kernel has undergone some cleanups and improvements (much of it got actually reimplemented):
      • Automatically generated stubs for variable implementations are directly inlined into the kernel. This improves performance, but more importantly, lifts some limits on the number of variables. Now, the only limit is that the sum of the ceiling of the logarithms of the number of modification events of all variables does not exceed 32 (as an estimate, the kernel now can handle around 10 to 16 variable types). Moreover, if the need for more variable types arises this is straightforward to do.
      • The addition of new variable types for users has been simplified.
      • The main propagation loop has been entirely rewritten (much much simpler). Now, the kernel does not optimize any longer for the case that a variable is modified more than once during propagator execution. While this changes the asymptotic complexity, it reduces the propagator execution overhead by up to 30%. And a propagator is still free to make sure that a variable is modified only once (many propagators do that already).
      • Variable implementations became smaller by one word. Now variable implementations are optimal in the sense that no additional memory is needed for cloning or book-keeping, the memory required for propagation is sufficient.
      • Spaces have lost some weight as memory for datastructures only used during cloning or propagation are shared (saves some 25% of memory per space). (major)
    • Propagator modification events have been renamed to modification event deltas (because that is what they are). (major)
    • To not confuse variable implementations with variables, variable implementations are now always called VarImp, and not Variable. (minor)
  • Bug fixes
    • Fixed bug in unreflection of empty VarArrays. (minor)
• Search engines
  • Other changes
    • All search engines now take an option value for configuration instead of individual arguments for recomputation, stop objects, etc. (major)
• Finite domain integers
  • Additions
    • Added interface to extensional constraints defined by TupleSets with BoolVars. (minor)
    • Added sqrt propagator. (minor)
    • Added sqr post function. (minor)
    • Added missing branching for INT_VAR_SIZE_DEGREE_MIN and INT_VAR_SIZE_DEGREE_MAX for Boolean variables. (minor)
  • Removals
    • Removed extensional constraints with offset arguments. (minor)
    • The offset arguments for element constraints have been removed, as you can simply add dummy elements to the array to achieve the same effect. (minor)
  • Other changes
    • Throw an exception if variables occur multiply for array-based channel constraints. (minor)
    • The limits for set variables have been moved from Limits::Set to Set::Limits.
      The range of integer variables have been extended by one bit. For example, on a standard machine (regardless of 32 or 64 bits), the largest possible integer value for an integer variable is 2^31-2, the smallest -2^31+2. With other words, only the integer values 2^31-1, -2^31, and -2^31+1 are missing from the two-complement representation (and we will never use these values for the sake of mental sanity. We promise.). (major)
  • Bug fixes
    • Fixed multiplication propagator for x*y=x. (minor)
    • The overloaded versions of dom for variable arrays could not be resolved automatically. (minor)
    • Distinct with integer offsets checks accurately for overflow now. (minor)
  • Performance improvements
    • IntSet have been reimplemented for efficiency. (minor)
    • Boolean variables consume 20% less memory. (minor)
• Finite integer sets
  • Removals
    • The offset arguments for selection constraints have been removed, as you can simply add dummy elements to the array to achieve the same effect. (minor)
  • Other changes
    • The limits for set variables have been moved from Limits::Set to Set::Limits.
      The range of set variables has been adapted to the range of integer variables. For example, on a standard machine (regardless of 32 or 64 bits), a set can hold values from -2^30+2 to 2^30-2, its maximum cardinality therefore is 2^31-3. (major)
  • Bug fixes
    • Fixed bugs in several set constraints: rel(Space*,SetVar,IntRelType irt,IntVar) for irt=IRT_NQ, rel(Space*,SetVar,SetOpType sot,const IntSet&,SetRelType srt,SetVar) for sot=SOT_MINUS, srt=SRT_SUP, selectDisjoint, selectUnion with constant IntSet arguments, dom with SRT_NQ. (major)
• Minimal modeling support
  • Additions
    • Support reified linear expressions with Boolean variables. (minor)
    • All minimodel functionality now understands both IntConLevel and PropKind arguments. (minor)
    • Added sqrt function. (minor)
  • Removals
    • Removed scheduling abstractions. (minor)
  • Bug fixes
    • Reimplemented linear expressions from scratch, they were just hopelessly screwed. (major)
    • Added work-around for compiler bug in MSVC. (minor)
    • Fixed bug in posting linear expressions. (major, thanks to Stanimir Dragiev)
• Example scripts
  • Additions
    • Simple Singleton Arc Consistency pre-processing has been added as an optional step for examples. (minor)
• Gist
  • Additions
    • The Gecode Interactive Search Tool (Gist), a Qt-based graphical search engine, is now part of the main Gecode distribution. It is currently included as an experimental beta preview and may not be completely stable yet. (major)
• General
  • Additions
    • The serialization library now contains a registry of all the Gecode post functions. This makes interfacing to Gecode much easier. The registry is automatically generated from the post functions defined in gecode/int.hh and gecode/set.hh. (major)
    • (De-)Serialization to and from JavaScript added. (major)
  • Other changes
    • Both the cost and propagate function of a propagator take the current modification event delta as input. Likewise, retrieving the modification event for a particular View must use the static function View::me with the passed modification event delta. Again, this feature committed the kernel to a particular implementation which might not be available in the future. (major)
  • Documentation fixes
    • Function prototypes are now highlighted in the detailed function documentation. (minor, thanks to Martin Mann)

Changes in Version 2.0.1 (2008-02-07)

This is a bug-fix only release. Very unfortunately, it fixes three serious bugs in search (LDS, Restart, and assignment branchings). We highly encourage you to switch to Gecode 2.0.1 as soon as possible.

• Kernel
  • Other changes
    • The VarMapIter can now return both a specification and the actual VarBase* of the currently iterated variable. (minor)
  • Bug fixes
    • Static initialization order was undefined, making reflection work unreliably. In particular, linking Gecode statically did not work. (major)
    • Exceptions did not have rtti information when compiled with gcc and visibility, which meant that they could not be caught. (minor)
    • Fixed a bug in the hash function for pointers, which could return negative array indices. (minor)
  • Performance improvements
    • Be less aggressive in increasing size of heap chunks. (minor)
• Search engines
  • Bug fixes
    • Assignment branchings wrongly reported that they feature two alternatives rather than one. (major)
    • LDS had numerous quirks. It has been fixed and greatly improved: it detects when the entire search tree has been probed, independent of the maximal discrepancy. (major, thanks to Stefano Gualandi)
    • Restart was broken in case the problem failed immediately with propagation only, both when being initialized or when requesting a next solution. (major, thanks to Stefano Gualandi)
• Finite domain integers
  • Additions
    • Re-added reified linear constraints for Boolean variables. (minor, thanks to Mohamad Rabbath)
  • Bug fixes
    • Fixed memory leak in IntSet. (minor)
    • Domain-consistent abs could crash in certain (extremely rare) border cases. (minor)
    • Initializing an IntVar with an empty IntSet did not throw the appropriate exception but crashed. (minor)
  • Documentation fixes
    • Fixed bug in documentation of table-based extensional constraint. (minor)
• Finite integer sets
  • Bug fixes
    • Fixed memory leak in set projection propagators. (minor)
• Range and value iterators
  • Bug fixes
    • Changed Ranges::Diff to make older versions of gcc happy. (minor, thanks to David Barton)
• Example scripts
  • Bug fixes
    • Fixed a bug and quirk in Kakuro puzzles. (minor, thanks to Helmut Simonis)
• Systematic tests
  • Additions
    • Added comprehensive tests for all search engines. (major)
  • Bug fixes
    • Fixed memory leak in reflection tests. (minor)
• General
  • Bug fixes
    • Fixed linking order so that static linking works again. (minor, thanks to David Barton)
    • Revived boost serialization. The serialization functions will be compiled if Gecode is configured with –with-boost. (minor)

Changes in Version 2.0.0 (2007-11-14)

As witnessed by the version number change, this is a major release with too many changes, fixes, and additions to mention them all: please consult the changelog.

The highlights are:

• New propagators: channeling between Integer variable and array of Boolean variables, circuit, table constraint (extensional), incremental regular constraint (extensional), incremental Boolean linear constraints
• Boolean variables have a dedicated implementation: twice as fast, half the memory
• Advisors for incremental propagation (see: Lagerkvist, Schulte, Advisors for Incremental Propagation, CP 2007)
• Many crucial performance and scalability improvements: memory management, memory footprint of propagators
• Many cleanups and more documentation, many new examples
• New set variables with complete domain representation (CpltSetVar) [experimental]
• A reflection API to query spaces about their propagators [experimental]

The features marked as experimental are all functional, but might be revised in the next releases.

As Gecode 2.0.0 is a major release, you might have to adapt your programs: How to Change to Gecode 2.0.0.

• Kernel
  • Additions
    • A reflection API has been added, which allows querying spaces about the variables and propagators they contain. (major)
    • Added advisors as an abstraction for incremental propagation: advisors are executed for their propagator whenever their view changes. Advisors, when not being used, add one word of overhead to each variable and slow down the system in the worst case by less than 1%. In average, no slowdown can be observed. (major)
    • A new propagation condition PC_GEN_NONE (and hence, PC_INT_NONE, ...) has been introduced. Propagator patterns with this propagation condition now do not create any subscriptions. (minor)
    • Support for reference-counted shared objects added: they handle both reference counting as well as non-shared copying. This fixes some bugs with the handling of shared arrays, integer sets, and finite automata. (major)
    • Added classes for shared objects and handles. Handles to shared objects allow to either share copies among spaces when being copied or to create a new shared copy, if requested. (major)
    • Added macro GECODE_REWRITE for rewriting propagators. It is strongly advised to always use this macro! (major)
    • Add a generic class for assignments during search (similar to generic branchings for views and values). (minor)
  • Other changes
    • Shared arrays are now available in the kernel (where they properly belong). This entails that they are available in the Gecode namespace and not in Gecode::Support. (minor)
    • VarArrays can now be resized dynamically. (minor)
    • The way how propagators report subsumption and partial fixpoints has changed. Now, a propagator must first call dispose (which then cancels subscriptions and possibly frees external resources) and only then can return that the propagator is subsumed. For that purpose a new function Gecode::ES_SUBSUMED has been defined. Likewise, ES_FIX_PARTIAL and ES_NOFIX_PARTIAL are functions rather than member functions of Gecode::Propagator. The benefit is that this saves memory and is more efficient. (major)
    • Made all macros type safe. (minor)
    • The propagator abstractions Inhom* have been renamed to Mix*. (minor)
    • Propagators and branchings that require disposal when a space is deleted must now be explicitly registered via a force function and explicitly deregistered by an unforce function. (minor)
  • Bug fixes
    • Branching ids were not properly initialized. This was a serious problem if you posted branchings in spaces other than the root space. (major)
    • Subscription to constant views now should use the propagate member function from a variable implementation: it guarantees execution of a propagator at least once (int and set views have been adopted accordingly). (minor)
  • Performance improvements
    • Improved automatic memory management on Windows platforms. (minor)
    • The memory management policies have been completely reworked. Now memory requests are much more regular. Hence, memory is much more likely to be returned to the operating system. Furthermore, the flush member functions for actors have been removed (they were unneeded) and actors and spaces now have allocated member functions for returning how much memory is allocated by a space.
      Moreover, the memory reported by some propagators has been ignored. Note that this flaw did not affect the benchmark figures on the Gecode webpage. (major)
    • Explicit disposal of actors has been reimplemented (the old design was nothing but darn stupid). The memory overhead of propagators is reduced by 40% for most propagators and 20% for all. That is, a binary propagator takes 30% less memory and a ternary propagator takes 25% less memory. Programs with many binary or ternary propagators can run up to 20% faster. (major)
• Finite domain integers
  • Additions
    • Added table-based extensional constraint. (major)
    • Added new variable selection based on largest or smallest quotient of size and degree. (minor)
    • Added a new version of count (and also atleast, atmost, exactly) that counts the number of variables equal to integers in an array. (minor, thanks to Martin Mann)
    • Added channel constraints that channel an integer variable to either a single or an array of Boolean variables. (major)
    • Relaxed sharing restrictions for channel, in particular channel(this, x, x) is allowed. (minor)
    • Added propagators for the circuit constraint. (major)
    • Added propagators for linear constraints over Boolean variables, in particular specialized and efficient versions for non-unit coefficients. (major)
    • The element constraint now also supports integer values as result. (minor)
  • Other changes
    • The extensional constraint specified by a DFA or a regular expression (formerly known as regular) is now named "extensional" rather than "regular". (minor)
    • The interface for the global cardinality constraint has been simplified. The constraint is now called count. (minor)
    • Regular expressions (REG) have been moved from the integer module to the minimodel module. (minor)
    • Iterator-based domain operations have been renamed, reimplemented, and extended. Now operations for both range and value iterators are supported and the operations can be told to perform more efficient destructive updates. (major)
    • Sortedness constraints have been renamed to sorted constraints. (minor)
    • The Boolean tell operations one_none and zero_none now also return a ModEvent and hence must be checked for failure. This is needed for simpler advisors. (minor)
    • Integer and Boolean variables are now guaranteed to be inspectable (that is, all const member functions work on them), even though a space is failed. However, the variables might have been modified during a tell operation that has failed. (minor)
    • Boolean variables (and hence Boolean views) do not any longer share the implementation with integer variables. That has the following consequences:
      • Boolean variables are not any longer integer variables. The same holds true for arrays of variables.
      • All constraints that make sense for both Boolean and integer variables have post functions that support both integer and Boolean variables.
      • Memory for Boolean variables is reduced by 50% and performance increases in problems with many Boolean variables by up to 50%. (major)
    • The linear constraints are now more careful (that is, they will use more efficient versions more often if it is safe) to determine whether overflow occurs and which precision (integer or double) should be chosen. (minor)
    • The element constraints now accept an additional offset argument. (minor)
    • All Boolean constraints got a new and regular interface. Rather than providing different post functions for the different constraints, the single post function rel is used: the Boolean operation then is described by a value of type BoolOpType. In addition, all Boolean propagators have been reimplemented for better performance and less memory use. (major)
    • The use of the consistency options were a little confusing, now the rule is: the level of consistency increases from ICL_VAL to ICL_BND to ICL_DOM. (minor)
    • All branching classes for value and view selection are now parametric. (minor)
    • Boolean variables cannot longer be initialized from an integer variable. If needed, a channel propagator must be posted (added). (minor)
    • The equality constraints have been replaced by a variant of rel. (minor)
    • The operations t_one, t_one_none, t_zero, t_zero_none for Boolean views have been renamed to one, one_none, zero, zero_none. (minor)
  • Bug fixes
    • Fixed a border-case bug for n-ary Boolean conjunction and disjunction. (minor)
    • Fixed bug in copying of n-ary or-propagator for a special boundary case. (minor)
    • Branching on maximum regret would always crash on non-range domains. (major)
    • Fixed memory leak in reified dom constraint. (minor)
  • Performance improvements
    • Boolean linear equations and inequalities with constant right-hand sides use constant time propagators whenever appropriate (linear time with less overhead and memory for propagators with few variables). (major)
    • The regular constraint has been reimplemented, the new version runs more than twice as fast. (major)
    • Domain consistent distinct and channel allocate memory from the space heap now. Much simpler. (minor)
    • The multiplication uses integer precision if possible for better performance. (minor)
• Finite integer sets
  • Additions
    • Added channeling propagator between a SetVar and a BoolVarArray that propagates the characteristic function of the set to the Boolean variables. (minor)
    • Finite set projectors can now be specified using formulas, in addition to set expressions. (minor)
    • Added selection and reified relation constraints with constant sets. (minor)
  • Removals
    • Removed buggy distinct propagator for finite sets. (minor)
  • Other changes
    • Slightly stronger inferences for the finite set sequence and selection constraints. (minor)
    • The finite set selection propagators accept an additional argument that specifies where the indexing should start. It should make some models more natural to express, and helps in porting code from other systems, such as Prolog or Mozart. In addition, the selectUnion propagator is now hand-written again, resulting in better performance. (minor)
  • Bug fixes
    • Fixed the n-ary partition propagator to handle overflow of the sum of cardinalities correctly. (minor)
    • Set projectors could subscribe with bogus propagation conditions. (minor)
    • Fixed memory leak in distinct constraint for sets. (minor)
  • Performance improvements
    • Changed the datastructure for set variables to use singly-linked lists. (minor)
    • Performance of the tell operations on finite set variables was improved. Especially the intersect operation benefits from this. (minor)
• Finite integer sets with complete representation
  • Additions
    • Finite integer set variables with complete domain representation, based on binary decision diagrams (BDDs), have been added as a new variable type. (major)
• Minimal modeling support
  • Other changes
    • Linear expressions and relations can also be created from Boolean variables, with the restriction that Boolean relations cannot be reified. (major)
  • Bug fixes
    • Fixed small quirk in posting an absolute propagator via a function. (minor)
  • Performance improvements
    • Boolean expressions erroneously decomposed into ternary Boolean constraints, while not incorrect rather inefficient for large Boolean expressions. (minor)
• Example scripts
  • Additions
    • New example: Kakuro puzzles. (minor, thanks to Helmut Simonis)
    • Added a model for the traveling salesman problem, mostly intended to exercise the new circuit constraint (as the model is not very competitive). (minor)
    • New example: the balanced academic curriculum problem (problem 030 from CSPlib). (minor)
    • New example: MineSweeper. (minor)
    • New example: Domino. (minor)
    • New example: Pentominoes. The example uses extensional constraints specified as regular expressions to place irregular-shaped pieces on a board. (major)
  • Other changes
    • Most examples have been cleaned up. (major)
    • Parsing of commandline arguments has been completely redone and is much more extensible and flexible. (minor)
  • Bug fixes
    • Examples reported wrong number of propagator invocations (the invocations for problem setup were missing). (minor)
    • The number of colors in graph-color was off by one. (minor)
    • Orientation of Sudokus now match the orientation in the specification-file. (minor)
• Systematic tests
  • Additions
    • Added simple testing for branchings. (minor)
• General
  • Additions
    • When compiling with gcc, the default visibility of symbols in the generated dynamic library is set to hidden. (minor)
    • Added dist and distdir targets for creating source distribution. (minor, thanks to Martin Mann)
    • On windows with MSVC, always build program database files to ease debugging of applications using Gecode (files are also included in packages). (minor, thanks to Filip Konvicka)
    • Variable arrays, view arrays, and argument arrays can directly be printed on standard output streams. (minor)
  • Other changes
    • The structure of includes has been drastically simplified. Support for iterators ("gecode/iter.hh") is automatically included with integers ("gecode/int.hh") and sets ("gecode/set.hh"). Likewise, all support functionality becomes available by including "gecode/support.hh" (one can assume that this is included in "gecode/kernel.hh"). (minor)
    • The values (and types) for selecting how to branch have been made uniform for all variables types: they start with INT_ (or SET_ or CPLTSET_), followed by either VAL or VAR and the respective strategy. (minor)
    • All of Gecode has been put under the MIT license (which the previous license was a simple rewording of). (minor)
  • Bug fixes
    • Removed huge number of casts that could (only potentially) compromise portability. (minor)

Changes in Version 1.3.1 (2006-10-25)

This is a minor release which fixes a major bug (the first real serious bug). Please update as soon as possible.

• Kernel
  • Bug fixes
    • Branch&Bound search with ViewValBranchings (all standard branchings) together with batch recomputation was severely broken. The problems ranged from wrong search trees (missing solutions) to segmentation faults. The fix changes the way assigned variables are removed from the array in a ViewValBranching. (major, thanks to Rafael Meneses)
• Finite domain integers
  • Bug fixes
    • Bounds-consistent distinct catches border case when an assigned variable during bounds propagation leads to value removal for value propagation. (minor)
    • IntVar::init now also raises exceptions for illegal domain specifications. (minor, thanks to Alejandro Arbelaez)
  • Performance improvements
    • Bounds-consistent distinct eliminates assigned variables more aggressively (can save up to 10% runtime in some cases). (minor)

Changes in Version 1.3.0 (2006-09-19)

This release adds a compiler for finite set projectors and provides new infrastructure making it easier to add new variable domains. In addition, it contains recent bug fixes and minor improvements.

• Kernel
  • Additions
    • Subscription to variables now features an additional and optional Boolean argument whether the propagator is to be processed. This allows dynamically creation of subscriptions during propagation. (major)
    • Variables can now be deallocated when the Space is deallocated (for example in case of failure). This is important in case a variable implementation needs to reference external resources. Deallocation can be switched on in the high-level description used for generating the variable implementation. (minor)
  • Bug fixes
    • Now commits can be interleaved with adding new constraints during batch recomputation. This also entails that commit does not raise an exception when applied to an already failed space (it is simply ignored). The bug could not be observed (unless you did some very fancy search engines yourself) and one could actually see it as an extension. (minor)
  • Performance improvements
    • Variable implementations are now generated from a high-level description (taking care of all aspects relating to modification events and propagation conditions). While simplifying the implementation of new variable domains considerably, this also can, in lucky cases, deliver a speed-up of 5%. (major)
    • Allocate subscriptions in separate memory area. Can speedup execution in some (but few) cases by up to 15-20%. (major)
• Search engines
  • Additions
    • Branch-and-bound search now interleaves recomputation with adding bounding constraints. This can prune the search tree much earlier: instead of recomputing many nodes from the same copy node and then adding a constraint that fails all these nodes, it might be possible to already fail the copy node directly. In principle, the difference can be exponential, however for examples we tried the effect is minor. (major)
• Finite domain integers
  • Other changes
    • Renamed lex constraint to rel (as it also supports equality and disequality). (minor)
  • Performance improvements
    • Make count constraints with integer number of equal occurrences more incremental using dynamic subscriptions (gives a 20-30% speedup). (minor)
  • Documentation fixes
    • Fixed documentation problem due to doxygen... (minor)
• Finite integer sets
  • Additions
    • Compiler for finite set projectors. Given a specification of a finite set constraint as a projector set, it generates C++ code for the corresponding propagator. Together with the dynamic propagator for finite set projectors, this implements the backend of the technique described in the paper "Generating Propagators for Finite Set Constraints" (Tack, Schulte, Smolka; CP 2006.). (major)
• Minimal modeling support
  • Additions
    • Added aliases lex, atleast, atmost, and exactly for the count constraint. (minor)
  • Bug fixes
    • Under certain conditions (posting in a failed space), the post function returned uninitialized variables. (minor, thanks to Rafael Meneses)
• Example scripts
  • Additions
    • Added an example for solving Black Hole patience games. (minor)
• General
  • Additions
    • Also pass options for linking standard libraries for MSVC. (minor, thanks to Jorge Marques Pelizzoni)
    • New configure switches: –enable-audit to include audit code, which may contain expensive checks of internal invariants or alternative, checked implementations of critical parts of Gecode. –enable-universal and –with-sdk, to support building universal binaries on Mac OS X. (minor)
  • Bug fixes
    • The pkg-config files now contain the correct path if you configured to the default prefix (i.e. /usr/local). (minor)

Changes in Version 1.2.2 (2006-07-25)

This release switches recomputation back on and removes some experimental code that had sneaked into the system...

• Kernel
  • Performance improvements
    • Some experimental code had sneaked into the release, slowing down the system by more than 10%... (major)
• Search engines
  • Bug fixes
    • With the changes to search in Gecode 1.2.1 recomputation was actually almost switched off... (major)
• Finite domain integers
  • Performance improvements
    • Improve performance of domain-consistent distinct (by providing special ternary version). Can reduce runtime by 10-20% for some examples. (minor)
    • Cut memory requirements for element (for integer arrays) by half. (minor)
• Example scripts
  • Additions
    • Added stress test for element constraint (originally due to Neng-Fa Zhou). (minor)
    • Added stress test for min constraint. (minor)
    • Added possibility to stop the search for solutions in examples based on the time taken, the number of fails, or both. (minor)
    • Added an example for solving Peacable co-existing armies of Queens. (minor)

Changes in Version 1.2.1 (2006-07-19)

In addition to the usual fixes and improvements, the biggest change is that all branchings now must support branching descriptions. This also entails straightforward changes (simplifications) to search-related space operations and to the implementation of search engines.

• Kernel
  • Additions
    • Added a macro GECODE_NEVER that assert that this command is never executed. This is preferred over assert(false) as it is used for optimization, if supported by a compiler (for example, Microsoft Visual C++). (minor)
  • Other changes
    • The ViewValBranching class now passes the home space to all member functions used in selecting the view and the value. (minor, thanks to Martin Mann)
    • The interface for branchings has changed considerably, reflecting the fact now that all branchings must support branching descriptions. This is also reflected in the Space::status operation which has its arguments reversed and corrected const qualifiers on its arguments. But the good news is that it is considerably simpler than before. (major)
    • The status operation does not any longer accept an argument for the number of alternatives. The number of alternatives is now available from a branching description (where it is passed upon creation of the description). This reflects the fact that branching descriptions are mandatory now. (major)
    • Change exceptions thrown by Gecode to be compliant with C++ exceptions. (minor)
  • Bug fixes
    • As Boolean variables can be derived from integer variables, the assumption that a not yet assigned Boolean variable can not be modified is wrong. (minor)
• Search engines
  • Other changes
    • Branchings now must return branching descriptions and commit operations also insist on being provided with branching descriptions. This change reflects that batch recomputation is of vital importance for efficiency in Gecode. (major)
  • Bug fixes
    • Fixed a serious bug where during recomputation the search stack was always inspected behind the last element: the reason why recomputation never crashed has been that stacks always keep one element extra for optimization. So, serious bug but looks as if no one stumbled over this... (major)
    • Search engines now correctly count the number of propagation steps including propagation that occurs when adaptive recomputation creates additional clones. (minor)
• Finite domain integers
  • Removals
    • Removed bounds-consistent propagation for count constraint (not worth the trouble, just use domain-consistent). (minor)
  • Bug fixes
    • Fixed fixpoint detection bug in n-ary min and max propagators. (minor)
    • Min and max propagators now correctly handle cases such as min(x,y)=x. (minor)
    • Assignment branchings (that is, branchings with a single alternative) could possibly take the wrong values for assignment during recomputation. (minor)
  • Performance improvements
    • Make Boolean linear constraints with constant right hand sides more incremental using dynamic subscriptions (gives a 20-30% speedup). (major)
    • Made n-ary Boolean conjunction and disjunction more incremental by using dynamic subscriptions. (minor)
    • Provide special versions of Boolean propagators optimizing cases where n-ary disjunctions are true. (minor)
    • Change implementation of Boolean propagators from conjunction to disjunction so that disjunction can be used as special case for Boolean sum with inequalities. (minor)
• Finite integer sets
  • Additions
    • Added finite set projection propagators. They allow to propagate all finite set constraints expressible as finite set projectors, including negated and reified constraints. (major)
  • Bug fixes
    • Fixed fixpoint detection for n-ary partition propagator. (minor)
• Minimal modeling support
  • Performance improvements
    • Take advantage of specialized Boolean propagators in Boolean expressions and relations. (minor)
• Support algorithms and datastructures
  • Additions
    • Added simple class encapsulating a linear congruential pseudo-random number generator. (minor)
• General
  • Bug fixes
    • Renamed macros so as to avoid nameclashes (all macros start with GECODE_). (minor)
  • Documentation fixes
    • Generate one page per version released in changelog. (minor)

Changes in Version 1.2.0 (2006-06-20)

This release makes quite some drastic changes to how propagators and branchings are deleted: instead of using destructors they use a dispose method that allows passing a home space during deletion (we will use this infrastructure measure to speed up cloning considerably a little later). Moreover the directory structure has changed on popular request so that all include files are to be found in a gecode subdirectory. Apart from that, some small fixes and extensions due to requests.

• Kernel
  • Additions
    • Spaces can be queried for number of propagators and branchings. (minor)
  • Other changes
    • The branch member function for branchings now also takes a home space as argument. (minor)
    • Canceling subscriptions on views and variable implementations now require also a home space (this has become possible due to not using destructors but ordinary "dispose" member functions). (major)
    • Actors (propagators and branchings) do not any longer use destructors but a "dispose" member function that takes a home space as argument and must return the size of the actor. Important: this requires that dispose member functions from super-classes and class members are called explicitly! (major)
  • Performance improvements
    • More aggressive inlining for canceling subscriptions. (minor)
• Search engines
  • Additions
    • Search engines can now be checked whether they have been stopped. (minor)
  • Bug fixes
    • Fixed linkage of BAB destructor under Cygwin. (minor)
• Finite domain integers
  • Bug fixes
    • Fixed memory leak in global cardinality constraint. (minor)
    • Fixed bug in equality tests that could lead to reified (dis)equality propagators not achieving domain consistency. (minor, thanks to Martin Mann)
  • Documentation fixes
    • Fixed bug in description of PC_INT_DOM. (minor, thanks to Martin Mann)
• Finite integer sets
  • Bug fixes
    • Fixed memory leak in finite set distinct propagator. (minor, thanks to Luis Otero)
• Example scripts
  • Other changes
    • Sudoku example generalized to arbitrarily sized Sudokus. (minor)
• Systematic tests
  • Additions
    • Added –enable-leak-debug configure option. This option causes the test suite to call mtrace() under Linux, which can be used to test for memory leaks. (minor)
• General
  • Other changes
    • Moved library source code into gecode subdirectory. Facilitates cleaner installation. Programs compiling against Gecode now need to include e.g. "gecode/int.hh". (major, thanks to Martin Mann)

Changes in Version 1.1.0 (2006-04-10)

This minor release adds some new constraints (see below), adds support for stopping search engines based on definable criteria, and some other small fixes. Most notably, the test infrastructure has been extended to also check whether propagators correctly claim that they have computed a fixpoint (now all invariants a propagator must obey in Gecode are covered by the test infrastructure). This has lead to many small fixes.

• Kernel
  • Other changes
    • The status member function now also allows the first argument to be optional. (minor)
• Search engines
  • Additions
    • Added functionality to interrupt search engines (introduced a Search::Stop class). (major, thanks to Rafael Meneses)
  • Other changes
    • Removed search engines optimizing for copying only (after all, one should always use some recomputation). (major)
• Finite domain integers
  • Additions
    • Added new constraint channel for variable/value channeling between two variable arrays. (major)
  • Other changes
    • Support for shared views has been removed in sortedness propagator and in the propagator for global cardinality with fixed cardinalities. (minor)
    • Staged propagation for domain-consistent absolute value propagator (minor)
    • EqBnd and EqDom now take two template parameters for their view types. This supports using different views, e.g. to express x0=-x1 using a MinusView. (minor)
    • All distinct propagators raise an exception if a variable occurs multiply in its arguments. (minor)
  • Bug fixes
    • Fixed bug in fixpoint detection of sortedness and global cardinality propagator. (minor)
    • Fixed bug in fixpoint detection of n-ary maximum/minimum propagator. (minor)
    • Fixed bug in fixpoint detection of bounds-consistent element for variables propagator. (minor)
    • Fixed bug in fixpoint detection of bounds-consistent squaring propagator (mult with the same variable twice). (minor)
    • Fixed bug in fixpoint detection of bounds-consistent abs propagator. (minor)
    • Fixed wrong assertion in gcc-bnd propagator. (minor, thanks to Stefano Gualandi)
    • Fixed indexing bug in SupportSet (part of the domain consistent linear equation propagator). (major, thanks to Jean-Christophe Godart)
  • Performance improvements
    • Rewrite n-ary linear, min/max, and Boolean propagators to binary/ternary variants during cloning if possible (saves memory). (minor)
    • Improved initialization of domain-consistent distinct propagator, in common cases for distinct this can save up to 10% runtime. (major)
• Finite integer sets
  • Other changes
    • Renamed the set propagators minElement to min, maxElement to max, and channelVarVal to channel. (major)
  • Bug fixes
    • A non-debug version of Gecode could not be linked to a program compiled with assertions switched on, as BndSet::isConsistent was missing from the library. (minor, thanks to Javier Mena)
    • Fixed bugs in fixpoint detection of several set propagators (match, convexity, sequence, n-ary (disjoint) union). (minor)
    • Fixed off-by-one bug in SetVarImp::lubMinN and SetVarImp::lubMaxN. (minor, thanks to Patrick Pekczynski)
• Minimal modeling support
  • Additions
    • Added functions returning variables for arithmetic (min, max, abs, mult, plus, minus). (minor)
  • Bug fixes
    • (In-)Equations were still not correct with respect to the sign. (minor, thanks to Olof Sivertsson)
    • Slice-operation now returns elements in right order. (minor, thanks to Olof Sivertsson)
    • Possible array-out-of bounds access fixed for MiniModel::Matrix. (minor, thanks to Olof Sivertsson)
• Example scripts
  • Additions
    • Added all-interval series using distinct. (minor)
  • Performance improvements
    • Added redundant constraint to social golfers example. (minor)
• General
  • Bug fixes
    • Added a configure switch –enable-doc-dot. If enabled, this checks for presence of the dot tool (used for generating graphs in the documentation) (minor, thanks to Kari Pahula)

Changes in Version 1.0.1 (2006-03-01)

Maintenance release including some additions of domain-consistent propagators and a fix for a serious bug in reified linear inequalities.

• Search engines
  • Other changes
    • Changed default copying recomputation distance to 8. (minor)
• Finite domain integers
  • Additions
    • Added domain-consistent linear equalities. (major)
    • Added domain-consistent version of the absolute value propagator. (major)
  • Other changes
    • Cost computation for sortedness has been changed from static to dynamic (taking into account the variable reduction the propagator can perform). (minor)
    • Global cardinality changed to non-staged version. Further inference for cardinality variables added. Parts of the graph structure for the domain-consistent propagator have been revised so as to avoid unnecessary propagation in case of fixed cardinalities and to allow better staging for the propagator. Revision of propagation for fixed cardinalities has also been applied to bounds-consistent propagator. (major)
  • Bug fixes
    • Fixed fixpoint detection for ternary min and max. (minor)
    • Fixed subsumption detection for regular with multiple variable occurences. (minor)
    • Fixed a very serious bug in the reified linear inequality propagator. (major, thanks to Dominik Brill)
    • The strongly connected components represented by the permutation variables in the extended version of Sortedness has been fixed restoring bounds consistency on the permutation variables. (major)
• Minimal modeling support
  • Additions
    • The post functions for linear expressions and relations also take an integer consistency level as optional argument. (minor)
  • Bug fixes
    • (In-)Equations with an int on the left hand side (like 9==x) were translated with a wrong sign (as -9==x). (minor, thanks to Olof Sivertsson)
• Example scripts
  • Other changes
    • Examples now use per default the recomputation settings as defined in the search module. (minor)
• General
  • Other changes
    • The soname for libraries on Linux is now set properly, as well as the version information on Darwin (Mac OS). (minor)
    • The build system has been updated to support building both static and shared libraries at the same time on Unix-like systems. (minor)
  • Bug fixes
    • The preprocessor macro NDEBUG for disabling assertions is no longer put into config.hpp. Without this fix, user programs could not use assert if Gecode was compiled with NDEBUG. (minor)
    • Removed some compiler warnings for the Microsoft compiler with -W3. (minor, thanks to Filip Konvicka)
  • Performance improvements
    • Switch assertions off in optimized builds with Microsoft's C++ compiler. (major)

Changes in Version 1.0.0 (2005-12-06, initial release)

No changes, of course.