# # Main authors: # Christian Schulte # # Copyright: # Christian Schulte, 2005 # # Last modified: # $Date: 2006-10-25 13:51:24 +0200 (Wed, 25 Oct 2006) $ by $Author: schulte $ # $Revision: 3787 $ # # This file is part of Gecode, the generic constraint # development environment: # http://www.gecode.org # # See the file "LICENSE" for information on usage and # redistribution of this file, and for a # DISCLAIMER OF ALL WARRANTIES. # # # This file contains entries for changelogs # # There are two kinds of entries: one marking releases and the others # being actual entries. # # All the lines for describing entries must start at the beginning. # # A release is described as follows: # [RELEASE] # Version: # Date: # [DESCRIPTION] # ... All the text up to the next [ENTRY] is included # as description # # An entry is described as follows: # [ENTRY] # Module: kernel|search|int|set|example|minimodel|iter|support|test|other # What: bug|documentation|performance|new|removed|change # Rank: minor|major # Bug: # Thanks: # [DESCRIPTION] # ... All the text up to the next [ENTRY] or [RELEASE] is included # as description # [RELEASE] Version: 1.3.1 Date: 2006-10-25 [DESCRIPTION] This is a minor release which fixes a major bug (the first real serious bug). Please update as soon as possible. [ENTRY] Module: kernel What: bug Rank: major Thanks: Rafael Meneses [DESCRIPTION] 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. [ENTRY] Module: int What: bug Rank: minor [DESCRIPTION] Bounds-consistent distinct catches border case when an assigned variable during bounds propagation leads to value removal for value propagation. [ENTRY] Module: int What: performance Rank: minor [DESCRIPTION] Bounds-consistent distinct eliminates assigned variables more aggresively (can save up to 10% runtime in some cases). [ENTRY] Module: int What: bug Rank: minor Thanks: Alejandro Arbelaez [DESCRIPTION] IntVar::init now also raises exceptions for illegal domain specifications. [RELEASE] Version: 1.3.0 Date: 2006-09-19 [DESCRIPTION] 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. [ENTRY] Module: set What: new Rank: major [DESCRIPTION] 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.). [ENTRY] Module: other What: new Rank: minor Thanks: Jorge Marques Pelizzoni [DESCRIPTION] Also pass options for linking standard libraries for MSVC. [ENTRY] Module: other What: bug Rank: minor [DESCRIPTION] The pkg-config files now contain the correct path if you configured to the default prefix (i.e. /usr/local). [ENTRY] Module: minimodel What: new Rank: minor [DESCRIPTION] Added aliases lex, atleast, atmost, and exactly for the count constraint. [ENTRY] Module: int What: change Rank: minor [DESCRIPTION] Renamed lex constraint to rel (as it also supports equality and disequality). [ENTRY] Module: int What: performance Rank: minor [DESCRIPTION] Make count constraints with integer number of equal ocurrences more incremental using dynamic subscriptions (gives a 20-30% speedup). [ENTRY] Module: example What: new Rank: minor [DESCRIPTION] Added an example for solving Black Hole patience games. [ENTRY] Module: kernel What: new Rank: major [DESCRIPTION] Subscription to variables now features an additional and optional Boolean argument whether the propagator is to be processed. This allows to dynamically create subscriptions during propagation. [ENTRY] Module: other What: new Rank: minor [DESCRIPTION] 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. [ENTRY] Module: kernel What: new Rank: minor [DESCRIPTION] 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. [ENTRY] Module: minimodel What: bug Rank: minor Thanks: Rafael Meneses [DESCRIPTION] Under certain conditions (posting in a failed space), the post function returned uninitialized variables. [ENTRY] Module: kernel What: performance Rank: major [DESCRIPTION] 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%. [ENTRY] Module: kernel What: performance Rank: major [DESCRIPTION] Allocate subscriptions in separate memory area. Can speedup execution in some (but few) cases by up to 15-20%. [ENTRY] Module: int What: documentation Rank: minor Bug: 43 [DESCRIPTION] Fixed documentation problem due to doxygen... [ENTRY] Module: search What: new Rank: major [DESCRIPTION] 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. [ENTRY] Module: kernel What: bug Rank: minor [DESCRIPTION] 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. [RELEASE] Version: 1.2.2 Date: 2006-07-25 [DESCRIPTION] This release switches recomputation back on and removes some experimental code that had sneaked into the system... [ENTRY] Module: kernel What: performance Rank: major [DESCRIPTION] Some experimental code had sneaked into the release, slowing down the system by more than 10%... [ENTRY] Module: search What: bug Rank: major [DESCRIPTION] With the changes to search in Gecode 1.2.1 recomputation was actually almost switched off... [ENTRY] Module: int What: performance Rank: minor [DESCRIPTION] Improve performance of domain-consistent distinct (by providing special ternary version). Can reduce runtime by 10-20% for some examples. [ENTRY] Module: int What: performance Rank: minor [DESCRIPTION] Cut memory requirements for element (for integer arrays) by half. [ENTRY] Module: example What: new Rank: minor [DESCRIPTION] Added stress test for element constraint (originally due to Neng-Fa Zhou). [ENTRY] Module: example What: new Rank: minor [DESCRIPTION] Added stress test for min constraint. [ENTRY] Module: example What: new Rank: minor [DESCRIPTION] Added possibility to stop the search for solutions in examples based on the time taken, the number of fails, or both. [ENTRY] Module: example What: new Rank: minor [DESCRIPTION] Added an example for solving Peacable co-existing armies of %Queens. [RELEASE] Version: 1.2.1 Date: 2006-07-19 [DESCRIPTION] 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. [ENTRY] Module: kernel What: new Rank: minor [DESCRIPTION] 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++). [ENTRY] Module: int What: bug Rank: minor [DESCRIPTION] Fixed fixpoint detection bug in n-ary min and max propagators. [ENTRY] Module: int What: bug Rank: minor [DESCRIPTION] Min and max propagators now correctly handle cases such as min(x,y)=x. [ENTRY] Module: int What: removed Rank: minor [DESCRIPTION] Removed bounds-consistent propagation for count constraint (not worth the trouble, just use domain-consistent). [ENTRY] Module: kernel What: change Rank: minor Thanks: Martin Mann [DESCRIPTION] The ViewValBranching class now passes the home space to all member functions used in selecting the view and the value. [ENTRY] Module: set What: bug Rank: minor [DESCRIPTION] Fixed fixpoint detection for n-ary partition propagator. [ENTRY] Module: set What: new Rank: major [DESCRIPTION] Added finite set projection propagators. They allow to propagate all finite set constraints expressible as finite set projectors, including negated and reified constraints. [ENTRY] Module: support What: new Rank: minor [DESCRIPTION] Added simple class encapsulating a linear congruential pseudo-random number generator. [ENTRY] Module: kernel What: change Rank: major [DESCRIPTION] 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. [ENTRY] Module: int What: bug Rank: minor [DESCRIPTION] Assignment branchings (that is, branchings with a single alternative) could possibly take the wrong values for assignment during recomputation. [ENTRY] Module: kernel What: change Rank: major [DESCRIPTION] 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. [ENTRY] Module: search What: bug Rank: major [DESCRIPTION] 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... [ENTRY] Module: kernel What: bug Rank: minor [DESCRIPTION] As Boolean variables can be derived from integer variables, the assumption that a not yet assigned Boolean variable can not be modified is wrong. [ENTRY] Module: other What: documentation Rank: minor [DESCRIPTION] Generate one page per version released in changelog. [ENTRY] Module: kernel What: change Rank: minor Bug: 41 [DESCRIPTION] Change exceptions thrown by Gecode to be compliant with C++ exceptions. [ENTRY] Module: other What: bug Rank: minor Bug: 42 [DESCRIPTION] Renamed macros so as to avoid nameclashes (all macros start with GECODE_). [ENTRY] Module: search What: bug Rank: minor [DESCRIPTION] Search engines now correctly count the number of propagation steps including propagation that occurs when adaptive recomputation creates additional clones. [ENTRY] Module: search What: change Rank: major [DESCRIPTION] 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. [ENTRY] Module: int What: performance Rank: major [DESCRIPTION] Make Boolean linear constraints with constant right hand sides more incremental using dynamic subscriptions (gives a 20-30% speedup). [ENTRY] Module: minimodel What: performance Rank: minor [DESCRIPTION] Take advantage of specialized Boolean propagators in Boolean expressions and relations. [ENTRY] Module: int What: performance Rank: minor [DESCRIPTION] Made n-ary Boolean conjunction and disjunction more incremental by using dynamic subscriptions. [ENTRY] Module: int What: performance Rank: minor [DESCRIPTION] Provide special versions of Boolean propagators optimizing cases where n-ary disjunctions are true. [ENTRY] Module: int What: performance Rank: minor [DESCRIPTION] Change implementation of Boolean propagators from conjunction to disjunction so that disjunction can be used as special case for Boolean sum with inequalities. [RELEASE] Version: 1.2.0 Date: 2006-06-20 [DESCRIPTION] 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 to pass 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. [ENTRY] Module: set What: bug Rank: minor Thanks: Luis Otero [DESCRIPTION] Fixed memory leak in finite set distinct propagator. [ENTRY] Module: int What: bug Rank: minor [DESCRIPTION] Fixed memory leak in global cardinality constraint. [ENTRY] Module: int What: bug Rank: minor Thanks: Martin Mann [DESCRIPTION] Fixed bug in equality tests that could lead to reified (dis)equality propagators not achieving domain consistency. [ENTRY] Module: test What: new Rank: minor [DESCRIPTION] 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. [ENTRY] Module: kernel What: performance Rank: minor [DESCRIPTION] More aggresive inlining for cancelling subscriptions. [ENTRY] Module: search What: bug Rank: minor Bug: 39 [DESCRIPTION] Fixed linkage of BAB destructor under Cygwin. [ENTRY] Module: kernel What: change Rank: minor [DESCRIPTION] The branch member function for branchings now also takes a home space as argument. [ENTRY] Module: kernel What: change Rank: major [DESCRIPTION] Cancelling 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). [ENTRY] Module: kernel What: change Rank: major [DESCRIPTION] 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! [ENTRY] Module: kernel What: new Rank: minor [DESCRIPTION] Spaces can be queried for number of propagators and branchings. [ENTRY] Module: search What: new Rank: minor [DESCRIPTION] Search engines can now be checked whether they have been stopped. [ENTRY] Module: int What: documentation Rank: minor Thanks: Martin Mann [DESCRIPTION] Fixed bug in description of PC_INT_DOM. [ENTRY] Module: other What: change Rank: major Thanks: Martin Mann [DESCRIPTION] Moved library source code into gecode subdirectory. Facilitates cleaner installation. Programs compiling against Gecode now need to include e.g. "gecode/int.hh". [ENTRY] Module: example What: change Rank: minor [DESCRIPTION] Sudoku example generalized to arbitrarily sized Sudokus. [RELEASE] Version: 1.1.0 Date: 2006-04-10 [DESCRIPTION] This minor release adds some new constraints (see below), adds support for stopping search engines based on definable criterias, 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. [ENTRY] Module: other What: bug Bug: 37 Rank: minor Thanks: Kari Pahula [DESCRIPTION] Added a configure switch --enable-doc-dot. If enabled, this checks for presence of the dot tool (used for generating graphs in the documentation) [ENTRY] Module: example What: new Rank: minor [DESCRIPTION] Added all-interval series using distinct. [ENTRY] Module: minimodel What: new Rank: minor [DESCRIPTION] Added functions returning variables for arithmetic (min, max, abs, mult, plus, minus). [ENTRY] Module: int What: change Rank: minor [DESCRIPTION] Support for shared views has been removed in sortedness propagator and in the propagator for global cardinality with fixed cardinalities. [ENTRY] Module: int What: bug Rank: minor [DESCRIPTION] Fixed bug in fixpoint detection of sortedness and global cardinality propagator. [ENTRY] Module: set What: bug Rank: minor Bug: 36 Thanks: Javier Mena [DESCRIPTION] 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. [ENTRY] Module: int What: change Rank: minor [DESCRIPTION] Staged propagation for domain-consistent absolute value propagator [ENTRY] Module: int What: change Rank: minor [DESCRIPTION] EqBnd and EqDom now take two template parameters for their views types. This allows using different views, e.g. to express x0=-x1 using a MinusView. [ENTRY] Module: search What: new Rank: major Thanks: Rafael Meneses [DESCRIPTION] Added functionality to interrupt search engines (introduced a Search::Stop class). [ENTRY] Module: search What: change Rank: major [DESCRIPTION] Removed search engines optimizing for copying only (after all, one should always use some recomputation). [ENTRY] Module: int What: bug Rank: minor [DESCRIPTION] Fixed bug in fixpoint detection of n-ary maximum/minimum propagator. [ENTRY] Module: kernel What: change Rank: minor [DESCRIPTION] The status member function now also allows the first argument to be optional. [ENTRY] Module: set What: bug Rank: minor [DESCRIPTION] Fixed bugs in fixpoint detection of several set propagators (match, convexity, sequence, n-ary (disjoint) union). [ENTRY] Module: int What: bug Rank: minor [DESCRIPTION] Fixed bug in fixpoint detection of bounds-consistent element for variables propagator. [ENTRY] Module: int What: bug Rank: minor [DESCRIPTION] Fixed bug in fixpoint detection of bounds-consistent squaring propagator (mult with the same variable twice). [ENTRY] Module: int What: bug Rank: minor [DESCRIPTION] Fixed bug in fixpoint detection of bounds-consistent abs propagator. [ENTRY] Module: int What: performance Rank: minor [DESCRIPTION] Rewrite n-ary linear, min/max, and Boolean propagators to binary/ternary variants during cloning if possible (saves memory). [ENTRY] Module: int What: bug Rank: minor Thanks: Stefano Gualandi [DESCRIPTION] Fixed wrong assertion in gcc-bnd propagator. [ENTRY] Module: int What: bug Rank: major Thanks: Jean-Christophe Godart [DESCRIPTION] Fixed indexing bug in SupportSet (part of the domain consistent linear equation propagator). [ENTRY] Module: int What: new Rank: major [DESCRIPTION] Added new constraint channel for variable/value channeling between two variable arrays. [ENTRY] Module: int What: change Rank: minor [DESCRIPTION] All distinct propagators raise an exception if a variable occurs multiply in its arguments. [ENTRY] Module: set What: change Rank: major [DESCRIPTION] Renamed the set propagators minElement to min, maxElement to max, and channelVarVal to channel. [ENTRY] Module: int What: performace Rank: major [DESCRIPTION] Improved initialization of domain-consistent distinct propagator, in common cases for distinct this can save up to 10% runtime. [ENTRY] Module: set What: bug Rank: minor Thanks: Patrick Pekczynski [DESCRIPTION] Fixed off-by-one bug in SetVarImp::lubMinN and SetVarImp::lubMaxN. [ENTRY] Module: minimodel What: bug Rank: minor Thanks: Olof Sivertsson [DESCRIPTION] (In-)Equations were still not correct with respect to the sign. [ENTRY] Module: minimodel What: bug Rank: minor Bug: 33 Thanks: Olof Sivertsson [DESCRIPTION] Slice-operation now returns elements in right order. [ENTRY] Module: minimodel What: bug Rank: minor Bug: 32 Thanks: Olof Sivertsson [DESCRIPTION] Possible array-out-of bounds access fixed for MiniModel::Matrix. [ENTRY] Module: example What: performance Rank: minor [DESCRIPTION] Added redundant constraint to social golfers example. [RELEASE] Version: 1.0.1 Date: 2006-03-01 [DESCRIPTION] Maintenance release including some additions of domain-consistent propagators and a fix for a serious bug in reified linear inequalities. [ENTRY] Module: search What: change Rank: minor [DESCRIPTION] Changed default copying recomputation distance to 8. [ENTRY] Module: minimodel What: bug Rank: minor Thanks: Olof Sivertsson [DESCRIPTION] (In-)Equations with an int on the left hand side (like 9==x) were translated with a wrong sign (as -9==x). [ENTRY] Module: other What: bug Rank: minor Bug: 31 [DESCRIPTION] The preprocessor macro NDEBUG for disabling assertions is no longer put into config.icc. Without this fix, user programs could not use assert if Gecode was compiled with NDEBUG. [ENTRY] Module: minimodel What: new Rank: minor [DESCRIPTION] The post functions for linear expressions and relations also take an integer consistency level as optional argument. [ENTRY] Module: int What: new Rank: major [DESCRIPTION] Added domain-consistent linear equalities. [ENTRY] Module: int What: bug Rank: minor Bug: 30 [DESCRIPTION] Fixed fixpoint detection for ternary min and max. [ENTRY] Module: int What: bug Rank: minor [DESCRIPTION] Fixed subsumption detection for regular with multiple variable occurences. [ENTRY] Module: int What: change Rank: minor [DESCRIPTION] Cost computation for sortedness has been changed from static to dynamic (taking into account the variable reduction the propagator can perform). [ENTRY] Module: int What: change Rank: major [DESCRIPTION] 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. [ENTRY] Module: int What: new Rank: major [DESCRIPTION] Added domain-consistent version of the absolute value propagator. [ENTRY] Module: other What: performance Rank: major [DESCRIPTION] Switch assertions off in optimized builds with Microsoft's C++ compiler. [ENTRY] Module: int What: bug Rank: major Bug: 29 Thanks: Dominik Brill [DESCRIPTION] Fixed a very serious bug in the reified linear inequality propagator. [ENTRY] Module: other What: bug Rank: minor Thanks: Filip Konvicka [DESCRIPTION] Removed some compiler warnings for the Microsoft compiler with -W3. [ENTRY] Module: int What: bug Rank: major Bug: 27 [DESCRIPTION] 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. [ENTRY] Module: other What: change Rank: minor Bug: 24 [DESCRIPTION] The soname for libraries on Linux is now set properly, as well as the version information on Darwin (Mac OS). [ENTRY] Module: other What: change Rank: minor Bug: 25 [DESCRIPTION] The build system has been updated to support building both static and shared libraries at the same time on Unix-like systems. [ENTRY] Module: example What: change Rank: minor [DESCRIPTION] Examples now use per default the recomputation settings as defined in the search module. [RELEASE] Version: 1.0.0 Date: 2005-12-06 [DESCRIPTION] Initial release.