La tendance actuelle est d’encourager les chercheurs à faire beaucoup de publications et à évaluer les chercheurs et les laboratoires sur la base du nombre de leurs publications en revues et conférences avec comités de lecture. En conséquence, une contribution ayant une très grande portée scientifique publiée dans un article de Workshop sera considérée comme moins importante qu’une contribution de moins grande portée, mais publiée en revue. D’autres critères sont parfois aussi mis en avant, comme le nombre de fois où ces publications sont citées dans la littérature scientifique, mais toujours dans l’esprit de chiffrer les performances des chercheurs. Un autre défaut du système est qu’il est difficile de savoir quelle est la contribution de chaque auteur dans un article publié par plusieurs chercheurs…
Si vous vous intéressez à mes publications, vous pouvez les consulter via ces liens :
Ce que je souhaite mettre en avant ici, ce sont mes principales contributions scientifiques, parce que le contenu me parait plus important que le contenant.
Recherche locale stochastique
Dans ma thèse, je propose des algorithmes permettant un échantillonnage statistique uniforme de différentes strates des paysages de recherche, c’est à dire le tirage aléatoire d’assignations satisfaisant un nombre donné de clauses (toutes les clauses dans le cas limite de l’échantillonnage des solutions). Mes algorithmes permettent également de mesurer la répartition des assignations et des extremums locaux en fonction du nombre de clauses satisfaites. Ces outils ont pour vocation la réalisation de mesures dans le cadre de l’étude des algorithmes de recherches locale stochastique.
En 1998, j’ai trouvé une méthode permettant d’utiliser un processus de recherche locale stochastique pour réaliser une estimation non biaisée du nombre de solution d’un problème.
J’ai co-encadré avec Jean-Jacques Chabrier la thèse d’Alain Sidaner, intitulée « Contribution à l’étude de l’algorithme de recherche locale stochastique WalkSAT sur des instances SAT aléatoires ». Outre l’encadrement scientifique, une de mes contributions à ce travail est l’idée d’une métrique et d’un algorithme efficace pour mesurer la dispersion spatiale des processus de recherche locale. Ces outils ont été utilisés par Alain Sidaner pour l’étude des phases d’intensification et de diversification d’un algorithme de recherche locale stochastique appelé WalkSat.
Difficulté des instances de problèmes
J’ai introduit au cours de mes années de doctorat une technique de production d’instances de problèmes difficiles pour un algorithme donné, basée sur l’utilisation de la recherche locale stochastique pour faire évoluer des instances du problème avec comme fonction objectif le temps de résolution par l’algorithme ciblé. Cette technique peut être utilisée pour des mesures de robustesse de solveurs de problèmes NP-difficiles.
Problèmes NP-diffciles et complexité
En 1999, j’ai découvert un nouveau problème NP-complet qui pouvait facilement se décomposer, en faisant varier la valeur d’un paramètre entier, en une collection in nie de problèmes de complexité en temps linéaire. Avec Pierre Marquis, nous avons étudié la complexité de ce problème, que nous avons appelé distance-sat, et de certaines variantes. Parallèlement, j’ai proposé un algorithme efficace pour la résolution de ce problème.
Automates cellulaires
En 2001, j’ai proposé à Emmanuel Sapin un sujet de thèse un peu ambitieux : la recherche par algorithmes évolutionnaire d’automates cellulaires capables de réaliser des calculs (par exemple par simulation de portes logiques), voire d’automates ayant, à l’instar du jeux de la vie, la puissance d’expression de la machine de Turing. Ce travail, que j’ai co-dirigé avec Jean-Jaques Chabrier, à donné lieu notamment à la découverte d’une plusieurs automates cellulaires calculateurs universels.
Traduction de contraintes
En 2003, j’ai découvert un système de codage de contraintes Booléennes de cardinalité en clauses propositionnelles (formule sous forme CNF) permettant à la propagation unitaire de restaurer la consistance d’arcs. Validé et expérimenté en collaboration avec Yacine Boufkhad, ce codage a permis d’améliorer l’efficacité de la résolution par des solveurs SAT de problèmes comportant des contraintes Booléennes de cardinalité.
En 2006, j’ai proposé un codage sous forme CNF de contraintes pseudo-Booléennes qui permet à la propagation unitaire, appliquée sur les clauses produites, de réaliser les mêmes déductions que la restauration de la consistance d’arc sur les contraintes initiales. Ce codage a été développé, validé, et sa complexité a été étudiée en collaboration avec Olivier Roussel et Yacine Boufkhad. Il a pour principal défaut de produire, dans le pire des cas, un nombre de clauses exponentiel en fonction de la taille de la contrainte à traduire.
En 2009, j’ai découvert un codage sous forme CNF de contraintes pseudo-Booléennes ayant les mêmes propriétés, en terme de puissance de propagation, que celui de 2006 précédemment mentionné, mais avec une complexité polynomiale dans le pire des cas. Ce codage a été validé et expérimenté en collaboration avec Olivier Roussel et Yacine Boufkhad, qui a par ailleurs proposé une variante nécessitant beaucoup moins de clause en contre partie d’une puissance de propagation plus faible.
J’ai réalisé une bibliothèque JAVA dédiée à la traduction de contraintes pseudo-Booléennes en CNF. Cette bibliothèque implante toutes les techniques que j’ai introduites et contribuer à introduire, ainsi que d’autres techniques présentée dans la littérature scientifique. Cette bibliothèque est hébergée sur le site sourceforge sous l’intitulé BoolVar/PB.
Re-découvertes
Peut être est-ce un sujet un peu tabou, mais il arrive que des chercheurs redécouvrent sans le savoir des choses qui ont déjà été publiées. Il s’agit bien sur d’un piège du métier dans lequel il faut éviter de tomber autant que possible. Cela m’est arrivé deux fois et j’ai fait le choix d’une totale transparence sur ces évènements parfois difficiles à éviter.
En 1996 j’ai redécouvert une technique d’échantillonnage des chemins dans un arbre de recherche qui avait été publiée antérieurement par Donald Knuth. J’avais appliqué cette technique au dénombrement statistique des solutions de problèmes de satisfaction de contraintes. J’ai publié ces résultats à AAAI 96 sans mentionner la paternité de l’algorithme, que j’ignorais. A l’époque, peu de travaux scientifiques étaient accessibles par Internet. Une recherche bibliographique sur un sujet nécessitait des mois, voire des années, avec l’échange de nombreux courriers postaux entre bibliothèques universitaire. Il était toujours possible de passer à coté d’un résultat…
En 2010, j’ai soumis à publication des résultats qui me semblaient avoir une portée scientifique importante et qui montraient notamment l’existence de contraintes impossibles à traduire en CNF avec la double exigence de conserver la puissance de la restauration de la consistance d’arc généralisée et de produire un nombre polynomial de clauses. L’essentiel du contenu de cet article, qui s’intitulait « On the expressive power of unit resolution », résultait de plusieurs années de travail, dont des centaines d’heures de rédaction et recherche d’un formalisme ayant pour objet de rendre les résultats clairs et accessible. L’article a été refusé un an plus tard et j’ai re-soumis certains des résultats dans un nouvel article en 2011. Ce n’est qu’en 2012, après le rejet du nouvel article, que j’ai découvert que l’essentiel des résultats avaient été publiés en 2009 dans un article intitulé « Circuit complexity and decomposition of global constraints ». Ni moi, ni aucun des relecteurs des deux articles que j’avais soumis sur le sujet, ne nous sommes aperçu avant de cette situation. D’une part, les termes utilisés étaient très différents, et d’autre part j’avais fait mes recherches bibliographique au moment où j’ai commencé à travailler sur les sujets concernés, avant la publication de l’article original. Depuis, je suis plus vigilent et j’ai revu mes pratiques de veille bibliographique.