Gecode: Overview

Gecode features a generic kernel on top of which modules such as search, finite domain integer constraints, and so on are provided.

Kernel

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

Search

Search in Gecode is based on a hybrid of recomputation and copying. Advanced techniques include parallel search (utilizes today's multi-core architectures), adaptive (speeds up further search) and path recomputation (reduces propagation during recomputation). Currently, Gecode supports search for some solutions, optimization (branch-and-bound), and limited discrepancy search (more details).

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), count (global cardinality, both bounds and domain consistent), element, cumulatives, table and regular as extensional constraints, sorted, circuit, channel, and lex (more details). It is simple to add new constraints and branchers (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 (more details). As for the finite domain constraints, the library can be easily extended with new constraints and branchers.

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 modeling support. This supports regular expressions for extensional constraints and expressing linear and Boolean constraints in the standard way as expressions build from numbers and operators (more details).