Many tasks in artificial intelligence, and more generally in computer science, require the resolution of difficult problems from a computational point of view.

The “Constraints” axis deals with the modeling and practical solution of of combinatorial problems under constraints. Two formalisms are mainly studied in the axis: SAT (Satisfiability Testing), where the variables are boolean and CSP (Constraint Satisfaction Problem) where the variables are defined on finite domains. These two formalisms are part of the general field of constraint programming (CP for Constraint Programming). Among the problems studied are satisfaction problems (existence of a solution), optimization problems (search for a “best” solution), counting problems (calculation of the number of solutions), enumeration problems (of solutions). The work carried out in this area ranges from theoretical developments (study of complexity, analysis of the properties of languages and algorithms) to the development of software (called solvers) allowing the practical solution of the problems studied.

Among the research themes of the “Constraints” axis, we find :

  • the development of general modeling languages and associated tools
  • the design of efficient mechanisms for traversing the search space
  • the design of inference and learning mechanisms within solvers
  • the upstream compilation of combinatorial problems in order to carry out, a posteriori, a set of queries on these problems in an efficient way.

Within the “Constraints” axis, the CRIL is therefore interested in various questions ranging from representation to the resolution of combinatorial problems. Work focuses on the extension of existing frameworks and the use of techniques from SAT, CSP and related formalisms (pseudo-boolean, quantified boolean formulas) to enlarge the fields of application. For example, many of the tools developed in the axis are used to address fundamental problems for explainable and robust AI.

The development of generic open-source solvers and the resolution of real (industrial) problems are also part of the activities conducted within the axis.

Activity report (in french)