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