TechDays 2009 : une utilisation originale du ‘solver foundation’

Issu des travaux menés par Microsoft Research Cambridge, le Solver Foundation est une solution .NET en pur code managé, capable de résoudre des problèmes d’une grande complexité.

Cette librairie dispose de plusieurs particularités : elle traite les contraintes en parallèle et peut écarter à la volée celles qui ne sont pas utiles, ce qui réduit le temps de traitement. De plus, elle exploite parfaitement la puissance des systèmes multicœurs ou multiprocesseurs. Sur le papier, elle est unique en son genre. Il manquait malgré tout de véritables cas pratiques d’utilisation qui exploitent cette puissance de traitement.

Nous avons eu le plaisir de rencontrer Pascal Belaud de Microsoft France, qui a su montrer encore une fois que les plus compétents des programmeurs sont souvent français. Ce dernier a tiré parti du Microsoft Solver Foundation (MSF) pour créer une application de gestion des agendas adaptée aux gros évènements… et en particulier aux TechDays. 244 séances à répartir sur 244 paires créneau horaire/salle, cela semble relativement simple. Toutefois lorsque nous prenons en compte les problèmes liés à cet agenda (respect des parcours, taille des salles, minimisation des déplacements, optimisation du planning des speakers, etc.), ce sont près de 2.000 contraintes qui apparaissent.

« La première tâche a consisté à modéliser les contraintes. Le code MSF a pu ensuite être généré. Une grande partie du problème fut toutefois de créer le code permettant de repérer et d’éliminer les contraintes bloquantes, le respect de toutes les contraintes ne donnant aucune solution valide. Le logiciel se charge donc d’éliminer des contraintes, jusqu’au moment où il trouvera un résultat. Dans la pratique, il a su trouver une solution après l’élimination de cinq contraintes », explique Pascal Belaud.

Une fois les contraintes sélectionnées, le calcul de l’agenda s’effectue en 32 secondes sur une machine 24 cœurs pourvue de 16 Go de mémoire. Préparer les données et éliminer les contraintes bloquantes aura cependant nécessité neuf heures de calculs, un travail qui a du être relancé chaque fois que les données étaient modifiées. Cela peut sembler beaucoup, mais il ne faut pas oublier que 1,4^E478 combinaisons (la factorielle de 244) ont dû être passées en revue à chaque itération.

Cette success-story à la française a rapidement fait son chemin : l’application de Pascal Belaud intégrera prochainement les exemples livrés avec MSF. On nous souffle également que Microsoft pourrait fort la réutiliser pour optimiser les agendas de ses autres rassemblements.

Notez enfin que Pascal Belaud est aussi l’auteur du , une application pour Windows Mobile qui a permis aux visiteurs de profiter au mieux de cet évènement. Les habitués des rendez-vous développeurs savent combien il est complexe de participer à toutes les sessions qui les intéressent. Avec cet outil, les TechDays auront été plus que jamais placés sous le signe de la productivité, faisant de cet évènement français un exemple en matière d’organisation.