Gecode Changelog

New in version 4.4.0

March 24th, 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 version 4.3.3 (January 21st, 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. (major, thanks to Zichen Zhu)
  • 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. (minor, thanks to Farshid Hassani Bijarbooneh)
  • 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. (minor, thanks to Mats Carlsson)
  • Fix behaviour of -a command line option for satisfaction problems. (minor, thanks to Björn Böttcher)
  • Fix default search annotation for float objectives. (minor, thanks to Chris Mears)
  • Install parser.tab.hh header. (minor, thanks to Willem Van Onsem)

New in version 4.3.2 (January 19th, 2015)

  • SYSTEMATIC TESTS:
  • Additions:
  • Added long-overdues tests for the FlatZinc interpreter. (major)
  • GECODE/FLATZINC:
  • Bug fixes:
  • Fixed major bug that would cause the FlatZinc interpreter to crash on most models. (major, thanks to Jean-Noël Monette)
  • GENERAL:
  • Bug fixes:
  • Fix cmake build file to work better when building with Qt. (minor, thanks to Alex Elliott)

New in version 4.3.1 (November 3rd, 2014)

  • This release fixes some minor issues and a major bug for the FlatZinc interpreter. It considerably extends restart-based search so that it supports LNS (Large Neighborhood Search).

New in version 3.7.1 (October 11th, 2011)

  • Search engines:
  • Bug fixes:
  • 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. (minor, thanks to Kish Shen)
  • 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 data structures:
  • 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. (major, thanks to Håkan Kjellerstrand)

New in version 3.7.0 (September 1st, 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, thanks to Max Ostrowski)
  • 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, thanks to Johannes Inführ)
  • 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, thanks to Gustavo Gutierrez)

New in version 3.6.0 (July 15th, 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)

New in version 3.5.0 (February 2nd, 2011)

  • Kernel
  • Additions
  • Added STL compatible iteration support for arrays (variable arrays, argument arrays, view arrays, and shared arrays). (major , contributed by Gregory Crosswhite)
  • Search engines
  • Bug fixes
  • Fixed a serious bug in parallel search (took over a year to isolate the bug). (major, thanks to Denys Duchier, Chris Mears)
  • Minimal modeling support
  • Bug fixes
  • Do not inline construction of linear, Boolean, and set expressions to avoid cross-DLL allocation/deallocation issues on Windows. (minor, thanks to Alexander Kleff)
  • Gecode/FlatZinc
  • Other changes
  • Fixed the definitions of global_cardinality to work with MiniZinc 1.2 and newer, and added corresponding definitions of global_cardinality_closed and global_cardinality_low_up_closed. (major)
  • Bug fixes
  • Fixed incorrect posting of linear constraints with variable arrays of size one. (major, thanks to Roberto Castañeda Lozano)
  • General
  • Additions
  • Gecode now compiles on FreeBSD. (minor, thanks to Peter Penchev)
  • Embed resource information into Gecode DLLs and EXEs on Windows. (major)
  • Other changes
  • Embed manifest into Gecode DLLs on Windows. (minor)

New in version 3.4.2 (October 11th, 2010)

  • Search engines:
  • Removals: Removed limited discrepancy search (LDS) as it is patented in the US. (minor)
  • Gecode/FlatZinc:
  • Additions: Added support for bin packing constraint. (minor)

New in version 3.3.1 (April 10th, 2010)

  • Kernel:
  • Other changes:
  • The (unused and unusable) CopiedHandle have been removed. (minor):
  • Bug fixes:
  • Fixed bug in VarArray::resize function that occurred when shrinking variable arrays. (minor)
  • Finite domain integers:
  • Bug fixes:
  • Fixed extensional constraint with finite automata for very unlikely (but apparantely possible) border case. (major):
  • The extensional constraints with tuple sets could cause crashes when used with parallel search. (major)
  • Finite integer sets:
  • Removals:
  • Removed Set::IntSetPropagator and Set::IntSetRePropagator because they are subsumed by the MixBinaryPropagator patterns. (minor):
  • Bug fixes:
  • Fixed channeling between set and integer variables which did not propagate enough. (minor)
  • Scheduling constraints:
  • Other changes:
  • Tasks in unary scheduling constraints may now have processing times of 0. (minor):
  • Bug fixes:
  • The unary scheduling propagator with optional tasks missed some propagation sometimes. (minor)
  • Script commandline driver:
  • Additions:
  • You can now register Gist inspectors in the driver options. (minor)
  • Example scripts:
  • Additions:
  • Added Gist inspectors for the Knights and Queens examples. (minor)
  • Gist:
  • Additions:
  • In addition to inspectors, you can now also register comparators, which can be used to compare two nodes in the tree. In combination with the option to compare before computing a fixpoint of the second node, this lets you see what exactly was modified by a branching. (major):
  • Gist can now stop exploration after all alternatives of a certain branching are exhausted. This feature can be turned on by posting a special branching using the Gist::stopBranch post function. Gist will then stop whenever that special branching becomes active. (major):
  • Added inspection of nodes before fixpoint computation. (minor):
  • Nodes can now be bookmarked. (minor):
  • Added inspectors that react whenever a node is selected. (minor):
  • Bug fixes:
  • Missing export declarations prevented embedding Gist as a widget. There is now example code for embedding Gist in the directory gecode/gist/standalone-example. (minor):
  • Fixed a bug where sometimes clicking on a node would select a different node. (minor):
  • Performance improvements:
  • Scrolling and zooming have been reimplemented. The new implementation is more efficient and works around problems that occurred with large trees on some platforms. Zooming is now more intuitive, keeping the current center centered. You can now also zoom by pressing shift while using the mouse wheel. (major)
  • Gecode/FlatZinc:
  • Other changes:
  • Comply with MiniZinc 1.1. String literals are not allowed any longer except in annotations, the solver outputs UNKNOWN and UNSATISFIABLE instead of just ==========, and the global constraints all_equal, decreasing_int, and decreasing_bool are supported. (minor):
  • Performance improvements:
  • Variables that do not have output annotations are now garbage collected during copying. (minor):
  • When using sums of Boolean variables using bool2int in MiniZinc, the FlatZinc interpreter now posts the more efficient propagators that work directly on the Boolean variables. (minor)
  • General:
  • Documentation fixes:
  • Removed many small documentation quirks. (minor)

New in version 3.3.0 (March 18th, 2010)

  • Kernel:
  • Additions:
  • Advisors now can force its propagator to be rescheduled, including recomputation of its cost used for scheduling (normally, a propagator is only rescheduled if its modification event delta changes). An advisor can signal forceful rescheduling by returning ES_NOFIX_FORCE or returning the return value of ES_NOFIX_FORCE_DISPOSE. Read the forthcoming "Modeling and Programming with Gecode" for details. (minor)
  • Other changes:
  • The failure macros for posting GECODE_ES_FAIL and GECODE_ME_FAIL now only accept a single argument and assume that "home" actually refers to the home space. Read the forthcoming "Modeling and Programming with Gecode" for details. (minor)
  • The functions ES_FIX_PARTIAL, ES_NOFIX_PARTIAL, ES_FIX_DISPOSE, and ES_NOFIX_DISPOSE are now member of Space. Read the forthcoming "Modeling and Programming with Gecode" for details. (minor)
  • The function ES_SUBSUMED now is a member of Space and accepts a propagator as its single argument. The variant with a size as the second argument is available as ES_SUBSUMED_DISPOSED but use is highly discouraged. Read the forthcoming "Modeling and Programming with Gecode" for details. (minor)
  • The functions ES_SUBSUMED_FIX and ES_SUBSUMED_NOFIX for advisors have been renamed to ES_FIX_DISPOSE and ES_NOFIX_DISPOSE. Read the forthcoming "Modeling and Programming with Gecode" for details. (minor)
  • Bug fixes:
  • ViewValBrancher with random value selection did not produce a random sequence of values. (minor)
  • Finite domain integers:
  • Additions:
  • Integer sets (IntSet) now have a in member function for testing whether an integer is included. (minor)
  • Other changes:
  • Patterns for reified propagators have been moved to the Gecode::Int namespace. (minor)
  • Performance improvements:
  • Considerably improved performance and memory consumption of the DFA-based extensional constraint (regular). (major)
  • Finite integer sets:
  • Other changes:
  • Patterns for set propagators have been moved to the Gecode::Set namespace. (minor)
  • Minimal modeling support:
  • Additions:
  • Linear expressions can freely mix integer and Boolean variables and support construction from variable arrays via a sum function. (minor)
  • Removals:
  • Removed special cases for posting linear and Boolean expressions consisting of a single variable only (was highly ambigious). (minor)
  • Support algorithms and datastructures:
  • Performance improvements:
  • Changed to single, really efficient bitset implementation used allover the system. (major)
  • Gist:
  • Bug fixes:
  • Avoid inter-thread call to QWidget::update, which apparently causes a slight memory leak (and warning messages on stderr) on Mac OS. (minor)
  • Gecode/FlatZinc:
  • Other changes:
  • The FlatZinc interpreter can now be extended by plugins that implement custom search strategies. The plugins are implemented as dynamically loaded libraries using the Qt plugin mechanism. An example can be found in the directory gecode/flatzinc/exampleplugin. (minor)
  • The index of the variable used for optimization is now available in the FlatZincSpace class. (minor)
  • Added command line option -print, which controls whether all solutions are printed or only the last one that is found, and -search, to choose between branch-and-bound and restart optimization. (minor)
  • The FlatZinc library can now parse a FlatZinc model into any subclass of FlatZincSpace, so that custom extensions can be built. Annotations on the solve item can now be accessed from the returned FlatZincSpace, so that additional search strategies can be implemented. (minor)
  • Bug fixes:
  • The FlatZinc interpreter ignored the -c-d and -a-d command line switches when used with Gist. (minor)

New in version 3.2.2 (December 1st, 2009)

  • Kernel:
  • Bug fixes:
  • Added missing assignment operator for space-based allocators for STL data structures. (minor, thanks to Gustavo Gutierrez)
  • Search engines:
  • Bug fixes:
  • The memory reported could be sometimes too low (the previous fix for 3.2.0 did not fix it for branch and bound search). (minor)
  • Finite domain integers:
  • Additions:
  • Added sequence constraint. (major , contributed by David Rijsman)
  • Bug fixes:
  • The global cardinality (count) constraint now accepts unsorted arrays of values. It previously propagated incorrectly if the array was not sorted. (minor, thanks to Alberto Delgado)
  • Fixed bug in the ICL_VAL propagator for global cardinality. (minor)
  • Subscription to constant views did not honor the flag to avoid processing. (minor)
  • Finite integer sets:
  • Bug fixes:
  • Subscription to constant views did not honor the flag to avoid processing (did not occur in practice). (minor)
  • Script commandline driver:
  • Additions:
  • Report if search engine has been stopped. (minor)
  • Range and value iterators:
  • Other changes:
  • Renamed test for subset or disjointness of range iterators to "compare". (minor)
  • Example scripts:
  • Additions:
  • Added car sequencing example (problem 1 in CSPLib). Uses the new sequence-constraint. (minor)
  • Gecode/FlatZinc:
  • Bug fixes:
  • Support search annotations with constants in the variable arrays. (minor, thanks to Håkan Kjellerstrand)
  • The set_in and set_in_reif constraints were buggy when used with Boolean variables (which are usually not generated by mzn2fzn so that the issue probably does not occur in practice). (minor)
  • The global_cardinality constraint was not completely compatible with the MiniZinc semantics. It would constrain values not mentioned in the array to have zero occurrences, while in MiniZinc they are unrestricted. (minor)
  • Element constraints in reified positions produced an error in the mzn2fzn translation. (major, thanks to Håkan Kjellerstrand)

New in version 3.2.1 (November 6th, 2009)

  • Kernel:
  • Additions:
  • Propagators and variables now maintain an accumulated failure count (AFC). (major)
  • Finite domain integers:
  • Additions:
  • Added INT_VAL_RANGES_MIN (and INT_VAL_RANGES_MAX) as value selection for branching: it tries the values from the smallest (largest) range first, if the variable's domain has several ranges, otherwise it splits the domain. (minor)
  • Added AFC-based branching strategies for integer and Boolean variables: INT_VAR_AFC_MIN, INT_VAR_AFC_MAX, INT_VAR_SIZE_AFC_MIN, INT_VAR_SIZE_AFC_MAX. For details, see "Modeling with Gecode". (major)
  • Other changes:
  • The semantics of division and modulo has changed to match the C standard. This means that the operations round towards zero, and that the result of the modulo has the same sign as its first argument. (minor)
  • Bug fixes:
  • Fixed segfault in matrix element constraint. (major)
  • Added missing dispose function for linear disequality of Boolean variables (the only problem was that with a proper dispose function more memory can be reused when the propagator becomes subsumed, so really a tiny quirk). (minor)
  • Performance improvements:
  • Element constraints for integer arrays now accept shared integer arrays (IntSharedArray). By this, the very same array can be shared among several element constraints. Models require no change, as IntArgs are automatically coerced to IntSharedArrays. See "Modelling with Gecode" for more explanation. (minor)
  • Optimized element for matrices (in special cases, the propagator is up to six times as efficient as before). (minor)
  • Finite integer sets:
  • Additions:
  • Added AFC-based branching strategies for set variables: SET_VAR_AFC_MIN, SET_VAR_AFC_MAX, SET_VAR_SIZE_AFC_MIN, SET_VAR_SIZE_AFC_MAX. For details, see "Modeling with Gecode". (major)Other changes
  • Split rel-op.cpp and rel-op-const.cpp into several compilation units, to avoid excessive memory and time usage of the gcc compiler. (minor)
  • Minimal modeling support:
  • Performance improvements:
  • Conversion of a regular expression to a DFA would crash on regular expressions with several million nodes (due to running out of call stack space). (minor, thanks to Håkan Kjellerstrand)
  • Example scripts:
  • Additions:
  • Added word square puzzle. (minor , contributed by Håkan Kjellerstrand)
  • Added crossword puzzle (thanks to Peter Van Beek for providing access to some crossword grids). (minor, thanks to Peter Van Beek)
  • Other changes:
  • Sudoku and GraphColor now uses smallest size over accumulated failure count (AFC) as the default heuristic. (minor)
  • Bug fixes:
  • The Nonogram example no longer crashes on empty lines. (minor, thanks to Jan Wolter)
  • Gecode/FlatZinc:
  • Bug fixes:
  • Fixed statistics output (number of solutions was sometimes wrong). (minor)
  • General:
  • Other changes:
  • Now posting of propagators and branchers take an object of class Home (rather than just a space) that can carry additional information relevant for posting (for example, groups and accumulated failure information). Models do not need to be changed in any way! (major)

New in version 3.2.0 (October 7th, 2009)

  • This release has some important bug fixes (in particular for global cardinality aka count), the documentation has been improved (worked around some issues with generation by doxygen), integrates the FlatZinc interpreter into the Gecode source tree, provides propagators for disjunctive scheduling (experimental), and lots of small changes and fixes. For more consistent names, branchings are branchers now and branching descriptions are choices (this you might have to adapt to).

New in version 3.0.2 (March 28th, 2009)

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

New in version 3.0.1 (March 26th, 2009)

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

New in version 3.0.0 (March 13th, 2009)

  • 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).

New in version 2.2.0 (August 26th, 2008)

  • 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: Removed ViewTuple. Just not useful enough... (minor)
  • Cleaned up Reflection::Var type, overloading did not conform to the C standard. (minor)
  • 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)
  • Fixed explanation of ES_FIX and ES_NOFIX for advisors (description was mixed up). (minor, thanks to David Rijsman)
  • Finite domain integers: 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)
  • All functional linear and arithmetic constraints now put sharp bounds on the output variable (eases interfacing to modelling languages). (minor)
  • 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)
  • Added documentation for domain consistent absolute value (abs) propagator. (minor)
  • Finite integer sets: The set selection constraints are now called element. (minor)
  • The ternary intersection propagator was incorrect if any of the sets had a maximum cardinality of Set::Limits::card. (major)
  • Example scripts: Example-based support for SAC (singleton arc consistency) has been removed. Might be reintroduced later in a more general fashion. (minor)
  • General: 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)
  • 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)

New in version 2.1.1 (April 10th, 2008)

  • 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)
  • Non-shared copying of dfa was broken (matters only for parallel execution). (minor)
  • The CpltSet variables are now in the correct documentation group. (minor)
  • Fixed redraw artefacts on Windows. (minor)
  • Fixed boost serialization. (minor)

New in version 2.1.0 (March 1st, 2008)

  • 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)
  • 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)
  • Fixed bug in unreflection of empty VarArrays. (minor)
  • 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)
  • 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)
  • 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)
  • 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)
  • IntSet have been reimplemented for efficiency. (minor)
  • Boolean variables consume 20% less memory. (minor)
  • 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)
  • 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)
  • 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)
  • Support reified linear expressions with Boolean variables. (minor)
  • All minimodel functionality now understands both IntConLevel and PropKind arguments. (minor)
  • Added sqrt function. (minor)
  • Removed scheduling abstractions. (minor)
  • 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)
  • Simple Singleton Arc Consistency pre-processing has been added as an optional step for examples. (minor)
  • 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)
  • 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)
  • 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)
  • Function prototypes are now highlighted in the detailed function documentation. (minor, thanks to Martin Mann)