Blog professionnel

La fin de l'année civile correspond aux dernières semaines du premier semestre de l'année universitaire.

Enseignement

Mes enseignements en Master, qui concernent la programmation par contraintes appliquée à la résolution de problèmes, sont terminés. J'ai réalisé un sujet d'examen, participé à la surveillance de l'épreuve, et corrigé les copies. Cette pratique est une spécificité universitaire : les maquettes et programmes d'enseignements sont définis localement (bien que soumis à l'approbation du ministère) , et les sujets d'examens de chaque unité d'enseignement sont conçus par le ou les enseignants qui en assument la responsabilité pédagogique. Toutefois, l'anonymat des étudiants est respecté pendant les corrections.

Les projets de master sont en cours de réalisation et font l'objet de réunions régulières avec les étudiants concernés. Le projet de développement d'un logiciel d'aide à la réalisation des emplois du temps des étudiants de l'UFR Sciences et Techniques avance rapidement. Celui ayant pour objet la réalisation d'une plate-forme de pédagogie participative n'a pas encore vraiment décollé. Je suis pessimiste quand à la perspective d'essayer un premier prototype pour mes enseignements du second semestre.

Recherche

J'ai conssacré l'essentiel de mon temps de recherche de ce mois-çi à la poursuite du développement de la bibliothèque logicielle BoolVar, dédiée à la résolution indirecte (via traduction en clauses propositionnelles ou en contraintes pseudo-Booléennes) de problèmes spécifiés à l'aide de contraintes.

J'ai travaillé à l'implantation d'un système de gestion de quota d'utilisation de la mémoire qui, associé à une heuristique de choix d'une technique de codage, permet une sélection automatique d'un algorithme (parmi plusieurs variantes possibles) de traduction de contraintes pseudo-Booléennes en clauses propositionnelles. Il y a en effet un compromis à trouver entre la taille de la formule propositionnelle produite et l'efficacité de la résolution. Les codages les plus efficasses s'avèrent parfois inutilisables parce que trop gourmands en mémoire.

J'ai implanté un codage suggéré par un collègue parisien, avec qui je travaille à distance via internet. J'ai également intégré au système un analyseur syntaxique permettant, en association avec un solveur SAT, de résoudre directement des instances de problèmes de décision spécifiés à l'aide de contraintes pseudo-Booléennes. J'ai confié le bébé à un collègue de l'Université d'Artois qui s'est chargé d'évaluer ses performances sur des benches utilisés dans une compétition internationale mettant en concurrence différents solveurs pseudo-Booléens. Il s'avère que le système consomme trop de mémoire, ce qui l'empêche de résoudre une majorité des instances. Il va falloir examiner de très près le comportement des processus de traduction pour déterminer s'il est possible de corriger en partie ce problème et d'envisagher de soumettre notre solveur indirect à la prochaine compétition, i.e., PB09. Indépendamment de ces problèmes techniques, je pense que les nouveaux codages proposés apportent une contribution théorique significative qui mérite une publication. Mais celle-ci sera plus facile à placer si elle est accompagnée de bon résultats expérimentaux...

J'ai également créé un programme permettant de produire des instances d'un problème de planification difficile. L'intérêt est de pouvoir créer des instances réalistes de problèmes de décision à contraintes pseudo-Booléennes avec la possibilité de doser la taille des contraintes et les valeurs de leurs coefficients. Cela offre un espace d'expérimentation intéressant pour la comparaison des différents codages.

Il reste beaucoup de travail avant de pouvoir tirer les premières conclusions sur la pertinence et l'intérêt des nouveaux codages de contraintes pseudo-Booléennes en logique propositionnelle qui sont implantés dans BoolVar.