Global Constraint Catalog

about the catalog

The catalog presents a list of 423 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 pdf version of the catalog is periodically updated by Nicolas Beldiceanu and Mats Carlsson. Feel free to contact the first author for any questions about the content of the catalog.

about this website

This website provides the online version of the catalog. It is generated from the Prolog and LaTeX source files of the pdf document using, in particular, Tralics, a TeX-to-XML/MathML translator, and MathJax, a javascript library for rendering maths from MathML.

The online version is conceived to ease the search through the catalog and to make available its electronic counterpart. These are Prolog and XML files describing global constraints and combinatorial problems, which can be used in systematic ways. See the pages below for a description of these two formats:

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

The table below sets side by side the constraints in the catalog with their analog in the systems Choco, Gecode, Jacop, and SICStus:

• Catalog-Systems correspondence table

Note on 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.

• 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.
• Chrome, Safari use by default the HTML-CSS output mode of MathJax and web fonts. Consider to install the STIX General Fonts (v.1.1.0) locally on your computer in order to improve the page loading speed.
• Old browsers (and perhaps MSIE ?) are not supported as pages are served as application/xhtml+xml instead of text/html. Some browsers are also not compatible with MathJax. In this case, consider the current pdf versions of the catalog.

contact

Corresponding author: Nicolas Beldiceanu nicolas.beldiceanu AT mines-nantes.fr
Online version: Sophie Demassey sophie.demassey AT mines-paristech.fr

see also

• the global constraint seeker by Nicolas Beldiceanu and Helmut Simonis and the help page
• Helmut Simonis's constraint applications blog
• Hakan Kjellerstrand's constraint programming blog and its global constraint models
• constraint programming standardization site

change log

2014-08-31 pdf version update

• compilation and format revision, minor corrections
• update links to librairies and solvers

2014-06-05 working version update: 423 constraints

• 69 new constraints including several variants of disequality and of sequence constraints.
• new sections: different facets of a global constraint and functional dependency invariants.
• electronic catalog, new description fields: quiz (modelling exercices), argument properties, counting (number of solutions), all solutions (example of a non ground instance and all the solutions associated), conditional implications (for learning models)
• links to miniZinc
• web: extract/generate all tikz images, new CSS, new URL.

2010-11-18 working version update: 354 constraints

• new constraints: abs_value, same_sign, opposite_sign; consecutive_groups_of_ones, consecutive_values; in_interval_reified.
• electronic catalog, modified description field See also providing links to semanticaly related global constraints: the related constraints are now grouped according to their relation type.
• electronic catalog, new description field Symmetries describing symmetries between the arguments of the constraint.
• electronic catalog, 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, and arithmetic constraints, etc.
• electronic catalog, new description field Systems: synonyms in the constraint systems Choco, Gecode, Jacop, and SICStus(see also: gccat_systems.xml).
• electronic catalog, new description field Logic for geometrical constraints: reformulation as first order logical formulae.
• new description field Reformulation: decomposition as conjunctions of constraints.
• automata: generation from constraint parameters.
• automata: $ transitions removed (the few remaining will be also removed)
• new Getting Started section
• alphabetical index of the constraints, keywords, global index
• convert all jpeg in png

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.
• electronic catalog: geost-based models of puzzle problem instances are provided in XML and Prolog format.
• graphical view of the resolution of squared squares problems using of geost.
• permanent url of each keyword page: just add a "K" prefix and ".html" suffix to the keyword name.

2008-09-18 working version update: 311 constraints

• new constraints: geost, in_intervals, alldifferent_consecutive_values
• electronic catalog: 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.

2008-02-03 working version update: 308 constraints

• new constraints: geometric constraints, arithmetic constraints, etc.
• electronic catalog: 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]
• new general index of the catalog with back references

2006-09-30 working version update: 276 constraints

• new constraints: open constraints
• electronic catalog: prolog source files available
• new 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