Generated on Mon Aug 25 11:35:46 2008 for Gecode by doxygen 1.5.6

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