Gecode Changelog

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)