L’agenda des TechDays 2009 a été entièrement construit avec Microsoft Solver Foundation
Comme vous devez le savoir, l’agenda des TechDays 2009 a officiellement été publié ce lundi 12 janvier 2009 au matin et le site d’inscription à cet événement est désormais ouvert :
Je tenais, dans ce billet, à partager avec vous la manière dont cet agenda a été construit cette année. Comme certains d’entre vous le savent peut-être déjà, le backend qui gère les TechDays s’appelle Vinci et a été développé par mes soins à l’occasion des TechDays 2008. Malgrès cela, le processus de création d’un agenda tel que celui des TechDays a, jusqu’à présent, été quelque chose de très lourd et surtout de très manuel et donc, par définition, très imparfait.
Voici donc l’envers du décor de la création de l’agenda de de l’édition 2009. En première mondiale chez Microsoft, il a été entièrement résolu à l’aide d’une toute nouvelle bibliothèque appelée Microsoft Solver Foundation :
Quelques chiffres sur la difficulté du problème à résoudre :
- 294 sessions dont 50 fixées à l’avance, soit 244 sessions à répartir sur 244 paires créneau horaire/salle
- Plus de 240 speakers impliqués
- Aucun speaker ne doit présenter plus d’une session à un créneau horaire donné (14 créneaux horaires disponibles sur les 3 jours de l’événement)
- 1 743 contraintes de créneau horaire (La session X doit être présentée à tel créneau horaire)
- 105 contraintes de salle (La session X doit être présentée dans tel type de salle, en terme de capacité)
- 42 contraintes de TrackPrecedences (La session X doit avoir lieu avant la session Y)
soit près de 2 000 contraintes à respecter.
De plus, une des contraintes supplémentaires était de minimiser le nombre de sessions d’un même parcours jouées au même moment.
Si on devait tester systématiquement toutes les combinaisons possibles, il faudrait passer en revue 1E478 ( = 244! ) combinaisons pour l’agenda des TechDays 2009 ! A raison de 1 seconde de calcul par itération, il faudrait donc 1E470 années de calcul sur un seul ordinateur. En supposant que l’on dispose de 1 000 000 d’ordinateurs pour effectuer ces calculs en parallèle, il faudrait donc 1E464 années pour tester toutes les combinaisons possibles, à mettre en rapport avec l’âge de l’Univers qui est 1E9 années ou encore le nombre d’atomes estimés dans l’univers qui est 1E79. Autant dire impossible ! :-)
Microsoft Solver Foundation nous a permis de résoudre notre problématique en 52 secondes sur un laptop dual core de dernière génération et 32 secondes sur un 24 cores avec 16Go de RAM. Cependant, il a fallu un travail de 9H d’affilée pour préparer les données et éliminer les contraintes qui rendaient le problème infaisable, et ce à chaque nouvelle itération (= tout changement de données). Pour information, il y’a eu 10 itérations avant de construire cet agenda.
La solution trouvée répond à 99.4% des contraintes exprimées, c’est à dire que seules 13 contraintes sur près de 2 000 n’ont pas pu être respectées !
Un grand merci à l’équipe Corp. de Microsoft Solver Foundation qui nous a énormément aidée en écrivant tout le code de déclaration du modèle. Cette mise en œuvre leur a tellement plu qu’ils vont l’intégrer comme un sample de leur SDK. Il est possible que j'écrive un article technique sur le sujet.
A noter qu'une session sur Microsoft Solver Foundation sera justement présentée lors de ces TechDays, par Lucas Bordeaux de Microsoft Research Cambridge :
Microsoft Solver Foundation (REC313)
Pour finir, voici ce qui se passait sur le 24 cores pendant que je faisais les optimisations :
Comments
Anonymous
January 13, 2009
Pascal BELAUD a publié un article sur la préparation des TechDays sur son blog dans lequel il n’a pasAnonymous
January 13, 2009
Salut Pascal Tu as fait évoluer Vinci par rapport a l'année dernière ? Tu t'es mis à WPF ? ;)Anonymous
January 19, 2009
Here is a post that describes a recent use case of Microsoft Solver Foundation in real world applications.Anonymous
February 28, 2009
Whew - an exciting and tiring week is over. We had hundreds of employees stop by our TechFest booth toAnonymous
April 27, 2009
Hi, I'm reading this through Google translate, but still interesting. Would it be possible to release the scheduling problem as a general benchmark somewhere? It could be a fun real-world example for others to try.Anonymous
July 25, 2010
If you work at Microsoft for any significant period of time you will change offices. I've been aroundAnonymous
August 05, 2010
If you work at Microsoft for any significant period of time you will change offices. I've been around