Global Constraint Catalog

html+MathJax / 2010-12-06

Search constraints by:

usage: see the [Beldiceanu et Simonis, CP'11] introduction paper and the basic help page

Keywords (ex: Assignment, Bound consistency, Soft constraint,...) can be searched by Meta-keywords (ex: Application area, Filtering, Constraint type,...)

Constraint Systems referenced are: Choco, Gecode, Jacop, and SICStus.

WARNING: Browser Compatibility

Displaying a page that contains mathematical expressions does not "just work" for most browsers. The Vismor Milieu.

Recommended configurations (see details):

Firefox 3.5+ after downloading the STIX open fonts: the cleanest and fastest way to see these pages (even if some big formula may not be rendered at all)
Any up-to-date browser other than MSIE: more robust but slower
MSIE and old browsers are not supported: consider the old html+css or the current pdf versions of the catalog.

About the catalogue

The catalogue presents a list of 354 global constraints issued from the literature in constraint programming and from popular constraint systems. The semantic of each constraint is given together with some typical usage and filtering algorithms, and with reformulations in terms of graph properties, automata, and/or logical formulae. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms.

The catalogue is periodically updated by Nicolas Beldiceanu, Mats Carlsson and Jean-Xavier Rampon. Feel free to contact the first author for any questions about the content of the catalogue.

Download the Global Constraint Catalog in pdf format:

last working version (2012-10) (about 23 Mo)
2nd Edition, revision a (SICS Technical Report 2012-02)) (about 12 Mo)
1st edition (SICS Technical Report 2005-08) (about 7 Mo)

About this website and the electronic catalogue

This website provides the online version of the catalogue. As the pdf version, it is generated from the Prolog and LaTeX source files of the document. The online version is first conceived to ease the search through the catalogue: constraints can be searched by name, keyword, author, graph description, etc. Moreover, it makes available the electronic files in Prolog and XML formats, describing each a global constraint or a combinatorial problem. These files can be used in systematic ways.

The two formats of the electronic catalogue are defined in the following pages:

Prolog format
XML format (see also the XML Schema + XSL)

Last, it provides correspondence tables (gccat_systems.xml) between the constraints in the catalog and the constraints available in the systems Choco, Gecode, Jacop, and SICStus.

Browser compatibility

This website is based on XHTML+MathML+CSS and on the MathJax javascript library for rendering mathematics in any browser that does not support MathML natively, i.e. about any browser except Firefox.

MSIE and old browsers are not supported as pages are served as application/xhtml+xml instead of text/html.
Firefox uses by default the native MathML (preferred) output but requires to download math fonts such as the STIX open fonts. As an alternative, you may also turn off the MathML output mode by right-clicking or ctl-clicking a formula and selecting Settings/Math Renderer/HTML-CSS in the contextual menu.
Other browsers use by default the HTML-CSS output mode of MathJax and web fonts. Some browsers are not compatible. In this case, consider the old html+css or the current pdf versions of the catalog.

You are invited to send any suggestions about this website or to report bugs to Sophie Demassey.

ChangeLog

2011-09-09 pdf version update: 364 constraints

electronic catalogue, new description field Argument Properties describing the properties of the constraint arguments, e.g. functional dependency, contractible, extensible, aggregate

2011-06-14 online version update

link to the Global Constraint Seeker by Nicolas Beldiceanu and Helmut Simonis. Usage: see the [Beldiceanu et Simonis, CP'11] introduction paper and the basic help page.

2010-11-18 working version update: 354 constraints

new constraints: abs_value, same_sign and opposite_sign; consecutive_groups_of_ones, consecutive_values; in_interval_reified.
electronic catalogue, modified description field See also providing links to semanticaly related global constraints: the related constraints are now grouped according to their relation type (e.g. is implied by or is a soft variant of).
electronic catalogue, new description field Symmetries describing symmetries between the arguments of the constraint.
electronic catalogue, new description field Typical describing the conditions typically satisfied by the arguments of the constraint (e.g. alldifferent has at least 2 variables in argument) in progress.
new exercices of modelisation with global constraints.
update of the correspondence tables with constraint systems.
add MathJax+MathML javascript library for rendering mathematics.
change to the open serif font family Fontin by Jos Buivenga.
extract all included images.

2010-07-01 pdf version update

SICS-T--2010-07--SE.pdf: second technical report edition of the catalog.

2010-01-29 pdf version update

new keyword reified automaton describing constraints for which the reified version can be mechanically constructed from the automaton.

2009-12-16 working version update: 348 constraints

new constraints: graph, order, vector, arithmetic constraints...
electronic catalogue, new description field Systems: synonyms in the constraint systems Choco, Gecode, Jacop, and SICStus(see also: gccat_systems.xml).
electronic catalogue, new description field Logic for geometrical constraints: reformulation as first order logical formulae (see e.g. meet_sboxes)
new description field Reformulation: decomposition as conjunctions of constraints (see e.g.: tree).
automata: generation from constraint parameters (see e.g. stretch_path, pattern)
automata: $ transitions removed (the few remaining will be also removed)
Getting Started section
alphabetical index of the constraints, keywords, global index
convert all jpeg in png (firefox ?)

2009-04-03 online version update

gccat_systems.xml: references to global constraints implemented within the constraint systems Choco and Gecode
gccat_schema.xml: the XML Schema of the catalog schema.xsd with a stylesheet
navigation bar (prev/next) added
google tools added: search and analytics

2008-11-15 working version update: 313 constraints

new constraints: all_equal and soft_all_equal_ctr, hard and soft equality constraints.
electronic catalogue: geost-based models of puzzle problem instances are provided in XML and Prolog format: packing almost squares, Partridge, pentomino, smallest square for packing consecutive dominoes, smallest rectangle for packing rectangles, smallest square for packing rectangles.
graphical view of the resolution of squared squares problems using of the geost constraint.
permanent url of each keyword page: just add a "K" prefix and ".html" suffix to the keyword name (see e.g. Kcompulsory_part.html)

2008-09-18 working version update: 311 constraints

new constraints: geost, a generic geometrical constraint for a large variety of puzzles, packing and placement problems; in_intervals, alldifferent_consecutive_values
electronic catalogue: the example instance of each constraint is provided as an XML file, avalaible on the constraint page. Helmut Simonis conceived the XML schema of the catalog.
permanent url of each constraint page: just add a "C" prefix and ".html" suffix to the constraint name (see e.g. Calldifferent.html)

2008-02-03 working version update: 308 constraints

new constraints: geometric constraints, arithmetic constraints,...
electronic catalogue: the prolog description files [.pl] are now available on each constraint page, as well as the printable version of the page [.pdf] and the graphical specification of the constraint [.png]
index: the general index of the catalogue with back references

2006-09-30 working version update: 276 constraints

new constraints: open constraints
electronic catalogue: prolog source files available
biblio: index of the bibliographic citations with back references
new arrangement for the constraint descriptions
scaled delimiters for the multi-line formulae

2006-06-12 working version online: 270 constraints

introduction page
figures automatically generated and resized
page names = section numbers

2006-05-12

constraints indexed on the elements (characteristics, restrictions, arc/set generators) of their graph description
fix broken internal links / numbering / anchors

Latex-to-XHTML: Resources

This website is automatically generated from the LaTeX source files of the catalogue using Tralics, a TeX-to-XML/MathML translator, MathJax, a javascript library for rendering mathematics from MathML, and several web formatting tools: XML, XSL, XSLT, XPath, and xsltproc, DTDs, CSS, XHTML, MathML.

Other docs and resources: XSL FAQ, w3schools, math and css (1), math and css (2), character search, ghostscript.

ToDo

interactive visualization of the relation graph (see also) between the constraints
correspondence with constraint systems: consider the arguments and restrictions of the constraints
automatic management of the keywords
new problem instances in the XML format (n-queen, sudoku, etc.) + XSL
search by synonyms (for now, see the general index)
TESTS on MacOSX: Firefox/MathML+STIX (some formula are not rendered), Firefox/MathJax (ok but slow), Chrome-Safari/MathJax (no line breaks in table formula)