Gecode 1.3.1 review

Gecode is a accessible, portable, and efficient environment for developing constraint-based systems and applications. Gecode is ra

License: BSD License File size: 877K Developer: Guido Tack

0

Gecode is a accessible, portable, and efficient environment for developing constraint-based systems and applications.

Gecode is radically open for programming, meaning that it can be easily interfaced to other systems. It supports the programming of new propagators (as implementation of constraints), branching strategies, and search engines.

New variable domains can be programmed at the same level of efficiency as finite domain and integer set variables that come predefined with Gecode.

Here are some key features of "Gecode":
Kernel

Gecode's kernel provides a comprehensive programming interface to construct new variable domains (including propagators as implementations of constraints and branchings) and search engines. It is slim (around 1000 lines of code) and requires no modification or hacking for adding new variable domains or search engines.

Search

Search in Gecode is based on recomputation and copying. Advanced techniques include adaptive (speeds up further search) and batch recomputation (drastically reduces propagation during recomputation). Currently, Gecode supports search for some solutions, optimization (branch-and-bound), and limited discrepancy search (more details). Parallel thread-based search is currently under development.

Finite domain constraints

Gecode comes with finite domain constraints implemented on top of the generic kernel. It offers standard constraints such as arithmetics, Boolean, linear equations, and global constraints such as: distinct (alldifferent, both bounds and domain consistent), global cardinality (both bounds and domain consistent), element, cumulatives, regular, sortedness, and lex. It is simple to add new constraints and branchings (in particular as the complete source code with the above constraints as examples is available).

Finite set constraints

Gecode also provides finite integer set variables. The standard set relations and operations are available as constraints, plus some specialized constraints such as convexity, global reasoning for distinctness of sets, selection constraints, weighted sets, and constraints connecting finite domain and finite set variables. As for the finite domain constraints, the library can be easily extended with new constraints and branchings.

Basic modeling support

Even though Gecode has been designed to be easy to interface to and not to be easy to model with, it comes with some basic modeling support. This supports expressing linear and Boolean constraints in the standard way as expressions build from numbers and operators.

What's New in This Release:
This is a minor release which fixes a major bug that appears when using branch-and-bound search.