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 2500 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 and optimization (branch-and-bound) (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, scheduling (unary and cumulative resources including edge-finding and not-first, not-last propagation), table and regular as extensional constraints, sorted, sequence, circuit, channel, bin-packing, value precedence, no-overlap (also known as diffn), nvalue, lex, and more (more details).

All in all, Gecode implements more than 70 constraints (as of Gecode 3.7.0) from the Global Constraint Catalog and many more that are not listed in the Catalog.

It is simple to add new constraints and branchers (in particular as the complete source code including 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.

Modeling support