Global Constraint Catalog

html+MathJax / 2010-12-06

### 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.

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.

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.

### 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

• 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
• 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
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
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)