Gecode Changelog

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)