Softpedia >Windows >Programming >Other Programming Files >Gecode >  Changelog

Gecode Changelog

What's new in Gecode 4.4.0

Mar 24, 2015
  • SEARCH ENGINES:
  • Additions:
  • Added functions to Stop class that can create common stop objects. (minor)
  • Exposed class definitions for common cutoff generators. (minor)
  • Bug fixes:
  • Fix memory leak in the DFS and BAB search engines that could make restart-based search run out of memory very quickly.
  • Performance improvements:
  • Delay efforts for restarting until it is really needed after a solution has been found. (minor)
  • MINIMAL MODELING SUPPORT:
  • Additions:
  • The classes FloatMinimizeSpace and FloatMaximizeSpace can be created with an improvement step for optimization.
  • SCRIPT COMMANDLINE DRIVER:
  • Additions:
  • An option -step now can pass an improvement step to scripts of type FloatMinimizeScript and FloatMaximizeScript.
  • Added option -seed for passing a seed to random number generators.
  • Other changes:
  • All scripts now must call the constructor of their base class with an option argument. Note that you will have to change your models by a call to the constructor of the script class with an option argument! (major)
  • EXAMPLE SCRIPTS:
  • Additions:
  • Added quasigroup completion benchmarks. (minor)
  • GECODE/FLATZINC:
  • Additions:
  • An option -step now can pass an improvement step for optimization of float problems. (minor)
  • Bug fixes:
  • Added support for missing builtins array_float_element (by decomposition), float_lin_lt and float_lin_lt_reif. (minor)
  • LNS could fail when the search was restarted before finding the first solution. (minor)

New in Gecode 4.3.3 (Jan 21, 2015)

  • SEARCH ENGINES:
  • Other changes:
  • Change the slave function for meta search engines to return whether the search in the slave is going to be complete. This is necessary for example in LNS, where completing the search in the slave does not mean that the overall search is finished. (minor)
  • Bug fixes:
  • Now no-goods are extracted properly in case a solution is found.
  • FINITE DOMAIN INTEGERS:
  • Additions:
  • Added argmin and argmax constraints. (minor)
  • FINITE INTEGER SETS:
  • Bug fixes:
  • The channeling propagator between a SetVar and an array of BoolVars propagated incorrectly when posted on a fixed SetVar.
  • GECODE/FLATZINC:
  • Additions:
  • Added support for arg_min and arg_max constraints. (minor)
  • Make a simple form of LNS accessible from FlatZinc. To use it, include gecode.mzn and add the relax_and_reconstruct search annotation defined in that file. (major)
  • Support dom_w_deg search annotation. (minor)
  • Add support for gecode_schedule_cumulative_optional constraint. (minor)
  • Other changes:
  • Add support for the MiniZinc 2 min/max builtins. The Gecode MiniZinc library is now compatible with both MiniZinc 1.6 and 2.0. (minor)
  • Search on objective function variable after all other variables (but still before introduced variables). (minor)
  • Bug fixes:
  • Fix special case detection for cumulatives constraint, could sometimes incorrectly turn a cumulatives into a disjunctive constraint.
  • Fix behaviour of -a command line option for satisfaction problems.
  • Fix default search annotation for float objectives.
  • Install parser.tab.hh header.

New in Gecode 4.3.2 (Nov 8, 2014)

  • FlatZinc bug in 4.3.1: Unfortunately the Gecode FlatZinc interpreter in versions 4.3.0 and 4.3.1 had major bugs. Please upgrade to Gecode 4.3.2 (see below) if you are planning to use FlatZinc!

New in Gecode 4.3.1 (Nov 3, 2014)

  • FlatZinc bug in 4.3.1: Unfortunately the Gecode FlatZinc interpreter in versions 4.3.0 and 4.3.1 has major bugs. Please revert to Gecode 4.2.1 (see below) or the svn trunk version if you are planning to use FlatZinc. We are currently testing bug fixes and will release an update soon.

New in Gecode 4.3.0 (Sep 19, 2014)

  • KERNEL:
  • Other changes:
  • Allow 0.0 as decay value.
  • Bug fixes:
  • The function brancher did not return a handle.
  • FINITE DOMAIN INTEGERS:
  • Additions:
  • Added multi-dimensional bin-packing constraint.
  • Bug fixes:
  • Re-enabled parts of not-first-not-last propagation for unary with optional tasks.
  • In extremely rare cases, the bounds-consistent distinct (and hence all other distinct propagators as they use the bounds-consistent one internally) propagator could suffer from numerical overflow.
  • No-good literals for greater-or-equal did not prune as much as they should.
  • FINITE INTEGER SETS:
  • Bug fixes
  • Removed compiler warning.
  • FLOATS:
  • Bug fixes:
  • Removed compiler warning.
  • MINIMAL MODELING SUPPORT:
  • Bug fixes:
  • Fixed posting of set relations involving constants. (major)
  • EXAMPLE SCRIPTS:
  • Additions:
  • Added example for multi-dimensional bin-packing constraint. Thanks to Brian and Willem-Jan for allowing us to use their data set.
  • SYSTEMATIC TESTS:
  • Bug fixes:
  • Removed uninitialized access.
  • gECODE/FLATZINC:
  • Other changes:
  • The --free command line option has been renamed to -f to comply with other FlatZinc solvers. (minor)
  • Bug fixes
  • Added unshare constraints to all constraints that need them. Without unsharing, variables occurring multiply in the same FlatZinc arrays could lead to the FlatZinc interpreter aborting with an error. (minor)
  • Fixed FlatZinc interpreter to compile with clang in C++11 mode. (minor, thanks to Victor Zverovich)
  • Catch exceptions and print proper error message. (minor)
  • Performance improvements
  • The diffn constraint now posts additional implied cumulative constraints to strengthen propagation. (minor)
  • Treat equality constraints in FlatZinc as aliases instead of posting propagators, and post simple domain constraints before more complex propagators to help post the most efficient versions. (minor)
  • GENERAL:
  • Bug fixes:
  • Various fixes for CMake:
  • Set the output directory for runtime target files (executables and DLLs) to bin/ subdirectory of the project's binary directory to avoid collisions when Gecode is used as a subproject.Improve suppression of warnings.
  • Add GECODE_USE_QT variable which specifies whether to use Qt. Qt is used if GECODE_USE_QT is TRUE or unset.
  • Prevent linker warnings on MSVC.
  • Use per-target instead of global include directories. This simplifies use of Gecode as a subproject because add_target_libraries( ) now sets the necessary include directories for in addition to link dependencies.
  • Fix to fully link internal dependencies needed for creating DLLs: https://github.com/ampl/gecode/pull/2 .
  • Added patch for PowerPC (downstream patch from Debian).
  • Added missing boost header files.

New in Gecode 4.2.1 (Nov 6, 2013)

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

New in Gecode 4.2.0 (Nov 6, 2013)

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

New in Gecode 4.1.0 (Nov 6, 2013)

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

New in Gecode 4.0.0 (Nov 6, 2013)

  • Kernel:
  • Additions:
  • The random seeds for variable and value branching options can now be initialized from a hardware random number generator (see MPG for details). (minor)
  • All ArgArrays now accept STL vectors and input iterators for construction. (minor)
  • The kernel now can record the activity of variables. The activity of a variable is defined as how often the domain of a variable has been pruned during search. For details, see "Modeling and Programming with Gecode". (major)
  • Other changes:
  • The default constrain() function for best-solution search now does by default nothing (it used to throw an exception). (minor)
  • The entire infrastructure for variable-value branchers has been reimplemented from scratch. The new design makes a much better compromise between code size, efficiency, and expressiveness: the efficiency is about the same (for examples with no propagation and just branching one can note a slowdown of 2-4%) while code size shrinks drastically (the overall code size for integer variables shrinks by 20%) and the architecture is much more expressive (in particular, it supports tie-break limits, see MPG). (major)
  • Throw exception when the user-defined copy constructor of a class that inherits from Space does not call the Space copy constructor. (minor)
  • Performance improvements:
  • Fixed a bug in the main memory allocation routine: now heap block sizes are decreased dynamically as they should be. Also changed the memory configuration parameters as explained in: Zandra Norman, Memory Management for Gecode. KTH Royal Institute of Technology, Sweden, Bachelor thesis, TRITA-ICT-EX-2012:143, 2012. (major, thanks to Zandra Norman)
  • Search engines:
  • Additions:
  • Added support for restart-based search, see MPG for details. (major)
  • Other changes:
  • Variable selection for branching used the quotient of size divided by degree, accumulated failure count, or activity. They now use the inverse. That is, for example, it is not any longer INT_VAR_SIZE_DEGREE_MIN() but INT_VAR_DEGREE_SIZE_MAX() (that is, largest degree divided by size). (major) Details
  • The restart best solution search engine has been removed (it is subsumed by the new restart-based meta search engine RBS). (major)
  • Performance improvements:
  • The search engines now do not allocate memory on the search stack for the rightmost branch of each node. This means that the search tree depth is now computed differently. It now represents the actual peak depth required at any one time, taking into account that rightmost branches reuse the stack entry of their parents. (minor)
  • Finite domain integers:
  • Additions:
  • Gecode now supports Lightweight Dynamic Symmetry Breaking (LDSB), see MPG for details. (major , contributed by Christopher Mears)
  • Added value selection strategies for branching INT_VAL_NEAR_MIN(), INT_VAL_NEAR_MAX(), INT_VAL_NEAR_INC(), and INT_VAL_NEAR_DEC(). They can take a previous assignment to the variables to branch on and try to choose values which are near (see MPG for details). (major, thanks to Manuel Loth)
  • Added domain constraint that constrains a variable (or an array) according to the domain of another variable. (minor)
  • Added variants of dom that copy the domain from one variable to another. (minor)
  • The nooverlap constraint now allows sharing of unassigned variables in its argument arrays. (minor)
  • Added half-reification for reified constraints (see Modeling and Programming with Gecode for details). (major)
  • Added pow and nroot constraints. (major)
  • The binpacking constraint now also accepts items of size zero. (minor, thanks to Kathrin Dannmann, Roberto Castañeda Lozano)
  • Added activity-based branching strategies for integer and Boolean variables: INT_VAR_ACTIVITY_MIN, INT_VAR_ACTIVITY_MAX, INT_VAR_ACTIVITY_SIZE__MIN, INT_VAR_ACTIVITY_SIZE_MAX. For details, see "Modeling and Programming with Gecode". (major)
  • Other changes:
  • The coefficients for linear constraints are now divided by their greatest common divisor. That means that some equations can be handled now that previously threw an OutOfLimits exception, and some equations can be handled with the more efficient integer precision propagators that previously required double precision. (minor)
  • Generalized definition of no-overlap propagators for better reuse. (minor, thanks to Roberto Castañeda Lozano)
  • The interface for branching on integer and Boolean variables has changed considerably (supporting user-defined variable and value selection, tie-break limit functions, handlers to created branchers, and more). In order to change, you have to add () to all variants of INT_VAR, INT_VAL, and INT_ASSIGN. For example, INT_VAR_SIZE_MIN becomes the function call INT_VAR_SIZE_MIN() and INT_VAL_MIN_MIN becomes the function call INT_VAL_MIN_MIN(). Some of these functions expect additional arguments and can take also optional arguments (this replaces the VarBranchOptions and ValBranchOptions). Please read the new "Branching" chapter in MPG. (major)
  • Respect IntConLevel argument for reified linear constraints with a single integer variable. (minor)
  • Bug fixes:
  • Fixed precede constraint with less than two values.
  • Fixed a bug where bounds consistent distinct reported subsumption instead of failure in certain cases.
  • Fixed potential rounding issues in sqr and sqrt constraints. (minor)
  • Fixed copying of tuple sets in extensional constraints and IntSets in sequence constraints (could lead to crashes when using parallel search).
  • Added missing propagation for nary min/max constraint.
  • Make extensional constraints work with empty tuple sets.
  • Fix count (global cardinality constraint) for multiple occurrences of the same value in the cover array.
  • Performance improvements:
  • Arithmetic, linear, and cumulative constraints now resort to internal operations using "long long int" rather than "double". This improves performance but also extends the range over integer coefficients that can be handled by linear constraints. (major)
  • Finite integer sets:
  • Additions:
  • Gecode now supports Lightweight Dynamic Symmetry Breaking (LDSB), see MPG for details.
  • Added domain constraint that constrains a variable (or an array) according to the domain of another variable. (minor)
  • Added domain constraints for arrays of set variables. (minor)
  • Added half-reification for reified constraints (see Modeling and Programming with Gecode for details). (major)
  • Added activity-based branching strategies for set variables: SET_VAR_ACTIVITY_MIN, SET_VAR_ACTIVITY_MAX, SET_VAR_ACTIVITY_SIZE_MIN, SET_VAR_ACTIVITY_SIZE_MAX. For details, see "Modeling and Programming with Gecode". (major)
  • Added channeling constraint between arrays of set variables.
  • Other changes:
  • The interface for branching on integer and Boolean variables has changed considerably (supporting user-defined variable and value selection, tie-break limit functions, handlers to created branchers, and more). In order to change, you have to add () to all variants of SET_VAR, SET_VAL, and SET_ASSIGN. For example, SET_VAR_SIZE_MIN becomes the function call SET_VAR_SIZE_MIN() and SET_VAL_MIN_INC becomes the function call SET_VAL_MIN_INC(). Some of these functions expect additional arguments and can take also optional arguments (this replaces the VarBranchOptions and ValBranchOptions). Please read the new "Branching" chapter in MPG. (major)
  • Bug fixes:
  • Fixed precede constraint with less than two values.
  • Floats:
  • Additions:
  • Added support for float variables.
  • Minimal modeling support:
  • Additions:
  • Added pow and nroot expressions for integer variables. (minor)
  • Other changes:
  • Made implementations of MiniModel expressions private, so that the MiniModel headers do not have to include propagator headers like gecode/int/linear.hh any longer. (minor)
  • Script commandline driver:
  • Additions:
  • Added commandline options to control restart-based search, see MPG for details. (major)
  • Decay values can now be passed on the command line using the switch -decay. (minor)
  • Added options -file-sol and -file-stat for writing solutions and statistics to arbitrary files and streams.
  • The command line -print-last configures whether only the last solution found is printed.
  • Other changes:
  • Boolean options (BoolOption) can now be given a false or true argument and hence are in-line with all other option types. (minor)
  • Range and value iterators:
  • Documentation fixes:
  • Clarified for several iterators that when using the assignment operator both iterators must be allocated from the very same region. (minor)
  • Support algorithms and datastructures:
  • Bug fixes:
  • Fixed a concurrency problem that caused an exception to be thrown at the end of a multi-threaded search on some platforms. (minor)
  • Fixed a bug in the allocation of very large bitsets.
  • Example scripts:
  • Additions:
  • New example: Colored matrix without monochromatic rectangles. (minor)
  • Gist:
  • Additions:
  • Added option to invoke move cursors during the automatic search. (minor)
  • Other changes:
  • Updated to compile with Qt version 5.0 (still works with Qt >= 4.3 as well). (minor)
  • Gecode/FlatZinc:
  • Additions:
  • Added support for more search annotations (defined in gecode.mzn), and for the restart and decay command line options. (minor)
  • Added native support for lex_less_bool and lex_lesseq_bool. (minor)
  • Gecode/FlatZinc now supports float constraints and variables. (major)
  • The FlatZinc interpreter now supports comparing of nodes in Gist. (major, thanks to Gabriel Hjort Blindell)
  • Added native support for the inverse_set constraint. (minor)
  • Other changes:
  • Renamed the FlatZinc executable to fzn-gecode, to better distinguish it when installed alongside other FlatZinc implementations. (minor)
  • The FlatZinc interpreter no longer performs a complete search on variables annotated as var_is_introduced, but tries to extend a solution on the model variables to a solution that includes the introduced variables. Each solution on the model variables is therefore only reported once. (major)
  • Bug fixes:
  • The mzn-gecode shell script now passes arguments correctly to the FlatZinc interpreter. (minor)
  • Removed spurious debug output for among constraint.
  • Exported registry and helper functions so that users can add constraint handlers to the FlatZinc interpreter.
  • General:
  • Additions:
  • Added CMake build script for Gecode (CMakeLists.txt).
  • Variable selection using AFC now supports decay. Read more in MPG. (major)
  • Other changes:
  • Compiles with MSVC 2012. (minor)

New in Gecode 3.7.3 (Nov 6, 2013)

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

New in Gecode 3.7.2 (Feb 29, 2012)

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

New in Gecode 3.7.1 (Oct 11, 2011)

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

New in Gecode 3.7.0 (Sep 1, 2011)

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

New in Gecode 3.6.0 (Jul 15, 2011)

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