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:
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:
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.
- 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.
- 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
- 2010-11-18 working version update: 354 constraints
- 2010-07-01 pdf version update
- 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
- 2008-11-15 working version update: 313 constraints
- 2008-09-18 working version update: 311 constraints
- 2008-02-03 working version update: 308 constraints
- 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
- constraints indexed on the elements (characteristics, restrictions, arc/set generators) of their graph description
- fix broken internal links / numbering / anchors
This website is automatically generated from the LaTeX source files of the catalogue using
Tralics, a TeX-to-XML/MathML translator,
and several web formatting tools:
Other docs and resources:
math and css (1),
math and css (2),
- 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)