french TASC - INRIA Rennes - LINA CNRS UMR 6241

Constraint solving system and extensions

The CHOCO library


In 1999, the OCRE project was initiated by people from École des Mines of Nantes, from ONERA in Toulouse, from Montpellier University, from INRA in Toulouse and from the private laboratory e-lab of the Bouygues group. The goal of this project is to provide to the constraint programming community an experimental platform involving tools, algorithms, examples and testbeds.

CHOCO is initially the kernel of the OCRE platform: a Java library provides the basic foundations of a constraint system such as variables and their domains, constraints, propagation and tree search.

CHOCO is distributed under the BSD licence scheme allowing both an academic as well as a commercial use.

The IBEX/QUIMPER library


IBEX is a software designed for the engineers/scientists that want to resort to set-membership methods to get reliable solutions of problems expressed with numerical constraints (global optimization, systems of equations, model inversion, etc.). Reliability means that any form of uncertainty can be taken into account, would it come from floating-point representation of numbers, round-off errors, linearization truncatures, model uncertainties, measurements noises, etc. The answer supplied by the solver must be compatible with all these aspects of uncertainty.

IBEX is a free C++ library under the GPL licence. The main feature is its ability to build solver/paver strategies declaratively through the contractor programming paradigm. The high-level QUIMPER language is an implementation of this paradigm. Hence, IBEX comes with a compiler of the QUIMPER language as well as several graphical tools dedicated to end users which take QUIMPER files as input (executables named qPave, qTraj, qSolve).

Algorithms in IBEX combine constraint propagation and interval methods. This combination is known to be very efficient for performing reliable numerics in a error-bounded context.

IBEX/Quimper has today around thirty regular academic users from different French universities and institutes (I3S at Nice, UTC at Compiègne, ENSIETA at Brest, LIRMM at Montpellier or IMS at Bordeaux,...).

global constraints library

We develop and integrate new global constraints in CHOCO: classical constraints from the research community that show up in a lot of applications (alldifferent, global cardinality, regular, etc.), as well as constraints from our research activities (tree, geost, multi-cost regular, etc.).

VISEXP: a visualisation library for explanations

In the context of the RNTL OADYMPPAC project the Contraintes team developed a tool to visualize explanations. This tool takes as input the generic trace produced by the execution of a constraint program. VISEXP uses the functionalities of VISADJ which is a tool to visualize a matrix developed within Ecole des Mines of Nantes by the Modeling and Interactive Design team.

Constraints learning

In the context of the constraint learning platform of LIRMM laboratory from Montpellier, we developed within CHOCO (in collaboration with Christian Bessière and Remi Coletta) a learning algorithm that, from a set of ground instances, learn implied global constraints. While being completely generic, the prototype is focussed on learning global_cardinality-like constraints.

Constraints Classification

GCCat: Global Constraint Catalog

The global constraint catalog...

GCSeek: Global Constraint Seeker

The seeker of global constraints...

Systematic filtering of constraints

We continue our work (with Mats Carlsson of the Swedish Institute of Computer Science) on the use of automata for the systematic construction of filtering algorithms. We have developed a prototype where, for a given constraint, we automatically construct a filtering algorithm from the automaton that accepts the solutions of the corresponding constraint. This technique was applied to about 50 constraints. We have also developed automata that compute lower and upper bounds for some common graph properties that occur in the graph based description of global constraints.



The web site about explanations...



Taking opportunity from the Sudoku mania, Narendra Jussien has animated a campaign for promoting constraint programming within the media (Nouvel Observateur, Science et Vie, France Inter, Canal+,etc.) from February to May 2006.

W3C: XHTML - last update : may 2011, SD