Changelog

Changes in Gecode Versions

• 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 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, bugzilla entry, 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 CSPLib). (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
• 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
    • 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, bugzilla entry)
    • 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, bugzilla entry)
    • Orientation of Sudokus now match the orientation in the specification-file. (minor, bugzilla entry)
• 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, bugzilla entry)
• 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, bugzilla entry)
  • 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, bugzilla entry)
  • 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, bugzilla entry)
• 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, bugzilla entry, 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, bugzilla entry, thanks to Olof Sivertsson)
    • Possible array-out-of bounds access fixed for MiniModel::Matrix. (minor, bugzilla entry, 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, bugzilla entry, 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, bugzilla entry)
    • Fixed subsumption detection for regular with multiple variable occurences. (minor)
    • Fixed a very serious bug in the reified linear inequality propagator. (major, bugzilla entry, 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, bugzilla entry)
• 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, bugzilla entry)
    • The build system has been updated to support building both static and shared libraries at the same time on Unix-like systems. (minor, bugzilla entry)
  • 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, bugzilla entry)
    • 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.