Constraints & Applications

The C&A team's research is organized around three themes: combinatorial optimization using operations research and constraint programming, concurrency theory and formal methods applied to biology and neuroscience.

The first theme consists of several recurring topics such as the solution of complex combinatorial optimization problems, in particular the Traveller's Problem (TSP) and the Bin Packing problem, the parallelization of constraint programming solvers, the development of efficient algorithms for multi-valued decision diagrams (MDD) and problem solving using MDD. We also have a strong interest in modeling and solving scheduling problems. Recently, we have produced some original models for constrained text or music production.

In the second theme, we use formal methods to study properties (such as safety or liveness) of concurrent systems.

Another theme concerns the modeling and formal verification of dynamic systems. The methodology we employ consists of three steps: (i) we describe the system in question as a graph which models the system's possible states and transitions, (ii) we formalize dynamic properties concerning the temporal evolution of the system's variables, (iii) we use automatic tools (model checkers) to test whether the encoded proprieties are verified by the modeled system.

In the field of biology and neuroscience, the formal methods we advocate essentially comprise two complementary approaches.
The first approach uses a well-known and proven automatic tool: Model-Checking.

The second approach is more recent, and very promising. We propose to use highly expressive logical frameworks, such as the Calculus of Inductive Constructions, to both model and study biological systems, providing semi-automatic and/or certified proofs.

The research team “Constraints & Applications” (C&A) gathers experts in:

  • operational research, artificial intelligence with a focus on constraint programming;
  • concurrency theory and logics applied to biology and neurosciences.

We are involved in the following hot topics identified in the Villani report on AI:

  • artificial intelligence and algorithmic approach;
  • decision aid;
  • knowledge representation and reasoning;
  • automatic learning (machine learning, deep learning, big data analysis);
  • natural language processing;
  • logics and formal proofs.