My Constraint Programming Blog

Guido Tack has released libmzn, a prototype implementation of a modular compilation architecture for MiniZinc.

From the presentation:

This project proposes to develop an infrastructure for constraint modeling based on MiniZinc, rather than just a modeling language. This will ensure a greater impact of MiniZinc, and a better chance of it being accepted as a standard.

The infrastructure will feature Application Programming Interfaces (APIs) in C and C++ for both modeling and solving. This architecture will make it easy to integrate the MiniZinc toolchain into applications and general-purpose programming languages, as well as provide a direct interface for solver backends.

libmzn is presented in the position paper (to be presented at the 2011 MiniZinc workshop): libmzn - A modular CP infrastructure based on MiniZinc (PDF). The abstract:

The main obstacle to a successful integration of MiniZinc models within general applications is the monolithic, text-based interface to the MiniZinc toolchain. Both the frontend and the individual solver backends require a custom, error-prone implementation of data exchange via text files.

This position paper proposes to develop an infrastructure for constraint modeling based on MiniZinc, rather than just a modeling language. This will ensure a greater impact of MiniZinc, and a better chance of it being accepted as a standard. Such an infrastructure could be based on a modular library for MiniZinc, called libmzn, featuring Application Programming Interfaces (APIs) in C and C++ for both modeling and solving. This architecture will make it easy to integrate the MiniZinc toolchain into applications and general-purpose programming languages, as well as provide a direct interface for solver backends.

Posted by hakank at 06:10 PM | Permalink

Gecode version 3.6 released. (Download.)

From the Changelog:

This release adds new constraints (value precedence constraints for integer and set variables, no-overlap constraints for rectangles, constraints for Hamiltonian paths), improves and cleans up a number of existing constraints (scheduling, channeling, relation, bin-packing, lexicographic relations), and adds new functionality (support for externalization of choices for distributed search, support for incremental propagation).

Some models might have to be changed as the graph and scheduling modules have been incorporated into the integer module (removing the respective include directives is sufficient).

On top, there are many small fixes, in particular for FlatZinc.

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

Also, don't forget to read Modeling and Programming with Gecode.

Posted by hakank at 08:37 AM | Permalink