ANR Project TUPLES - Programme Blanc 10-BLAN-0210
Tractability for Understanding and Pushing forward the Limits of Efficient Solvers
ANR CRIL GREYC IRIT LSIS
Valid XHTML 1.0 Strict
CSS Valide !

This project focuses on effective resolution of NP-complete problems, especially problems relating to Artificial Intelligence. In summary, the main objective of this project is to significantly push forward the limits currently observed in the effectiveness of "solvers" of combinatorial problems, while simultaneously establishing a theoretical framework that seems necessary to achieve this goal . This project addresses this issue through the development and the implementation of tractable classes. Tractable classes will be also used to explain the relative effectiveness of solvers, using them as tools for this theoretical analysis.

This project will focus on artificial intelligence, especially on generic and classical problems such as SAT (the satisfiability problem in propositional logic) and CSP (Constraint Satisfaction Problems), which have many applications in other fields of computer sciences, such as operations research or bioinformatics. Other related areas of Artificial Intelligence, such as Automated Planning, are also addressed in this project, being considered here primarily as areas of application of the results on a more general level.

The main objective of this project is to significantly improve the effectiveness of current solvers, basing our study on identifying the reasons leading to their effectiveness (in other words, the probably polynomial behavior of algorithms for solving certain classes of instances). This will require the production of new tractable classes which should be usable in practice. By "usable in practice" we mean the ability of these classes to be easily and efficiently implemented in solvers.

TUPLES will adress this problem basing on two complementary approaches.

  1. A theoretical and analytical approach, mainly motivated by the fact that a better understanding of what leads to effective behaviors of solvers in practice (ie polynomial) is now required.
  2. An experimental approach. On the one hand, to understand why the most competitive solvers can solve very large instances (e.g. industrial instances with millions of propositional variables), while exploiting heuristics, constraint propagation techniques, constraint learning, all without using tractable classes. On the other hand, implementing practical systems, significantly improving the power of existing solvers.

This project began in late 2010 for a duration of 4 years.

Keywords: Artificial Intelligence, SAT, CSP, Automated Planning, Computational Complexity, Tractable Classes, Solvers, Practical Efficiency


Le projet TUPLES est centré sur la résolution effective de problèmes NP-Complets, en particulier de problèmes relevant de l'Intelligence Artificielle. En résumé, l'objectif principal de ce projet est de repousser de façon significative les limites actuellement observées au niveau de l'efficacité des «solveurs» de problèmes combinatoires, tout en établissant en même temps un cadre théorique qui semble nécessaire pour atteindre cet objectif. Le projet TUPLES aborde cette question par le développement et l'exploitation de classes polynomiales ainsi qu'en les envisageant comme outils d'analyse pour expliquer l'efficacité relative des solveurs. Cette étude sera centrée sur l'Intelligence Artificielle, en particulier sur les problèmes génériques que sont SAT (le problème de satisfiabilité en logique propositionnelle) et CSP (Constraint Satisfaction Problem), problèmes ayant par ailleurs de nombreuses applications dans d'autres domaines de l'Informatique tels que la Recherche Opérationnelle et la Bio-informatique notamment. D'autres domaines connexes de l'Intelligence artificielle, tels que la Planification Automatique, sont également traités dans ce projet, étant considérés ici principalement comme domaines d'application des résultats obtenus sur un plan plus général.

L'objectif principal du projet consiste donc à améliorer sensiblement l'efficacité pratique des solveurs actuels en fondant notre étude sur l'identification des raisons conduisant à leur efficacité (en d'autres termes, au comportement vraisemblablement polynomial des algorithmes de résolution sur certaines classes d'instances). Cela nécessitera la production de nouvelles classes polynomiales qui devront être opérationnelles en pratique. Par «opérationnelle en pratique», nous entendons notamment la capacité que possèdent ces classes à être facilement et efficacement implémentées dans les solveurs, ce qui correspondra à l'existence d'un test de reconnaissance et à une méthode de résolution d'instances de complexité polynomiale exécutables à faible coût.

La façon dont le projet TUPLES appréhende cette problématique est fondée sur deux approches complémentaires.

  1. Une approche théorique et analytique, motivée principalement par le fait qu'une meilleure compréhension de ce qui conduit à des comportements efficaces en pratique (ie. polynomiaux) est désormais nécessaire.
  2. Une approche expérimentale, afin d'abord, de comprendre pourquoi les solveurs les plus compétitifs permettent de résoudre des jeux données (industriels) de très grande taille grâce à l'exploitation d'heuristiques, de techniques de propagation de contraintes, de méthodes d'apprentissage de contraintes, tout cela, sans recours à l'exploitation de classes polynomiales. L'autre aspect expérimental est lié à la production de systèmes opérationnels améliorant significativement la puissance des solveurs actuels.

Ce projet a débuté fin 2010 pour une durée de 4 ans.

Mots-Clés : Intelligence Artificielle, SAT, CSP, Planification Automatique, Complexité Algorithmique, Classes Polynomiales, Solveurs, Efficacité pratique.