Global Constraint Catalog

About the catalogue

The catalogue presents a list of 348 global constraints issued from the literature in constraint programming and from popular constraint systems. The semantic of each constraint is given together with a description in terms of graph properties and/or automata.

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:

• the last working version (2010-01-29) (about 15 Mo)
• the edited version (2005-08) (Sicstus technical report, 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 (Prolog and XML) files describing constraints and problems for use in systematic ways.

The two formats of the electronic catalogue are defined here:

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

This website is still under construction and test. You are invited to send any suggestions about this website or to report bugs to Sophie Demassey.

WARNING: This document actually uses XHTML+CSS following (as much as possible) the W3C recommendations. Internet Explorer/Windows may not correctly render the pages.

ChangeLog

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

See also

• Hakan Kjellerstrand's constraint programming blog and its global constraint models

Latex-to-XHTML: Resources

This website is automatically generated from the LaTeX source files of the catalogue using Tralics, a TeX-to-XML translator, 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

• referring of constraint systems from the catalog: consider arguments and restrictions
• automate the management of the keywords
• provide other problem instances in the XML format (n-queen, sudoku, etc.)
• search by synonyms (for now, see the general index)
• XSL for XML+MathML version / print / XML constraint models
• fix mathematic display and css issues (fractions (ex: invariants), tables (ex: elem),...)
• TEST: OK for Firefox+Safari / Mac OS X with fonts Helvetica Neue UltraLight, Helvetica Neue Light, Monaco,...