Quelques liens pour ceux qui auraient lu cet article du Monde :
Un peu de programmation linéaire en nombres entiers aujourd'hui, appliquée à la constitution d'une collection de CD. Depuis son édition intégrale des oeuvres de Mozart en 2005, Brilliant Classics a récidivé avec Bach en 2006, Chopin et Beethoven en 2007, Brahms et Haydn et Rachmaninov en 2008. A chaque fois avec des prix canons. Pour Schubert et Dvorak, en revanche, il faut être patient, et ça m'embête bien...
Alors comment réunir une intégrale d'un compositeur en achetant le minimum de CD (sans pirater bien sûr !) ? Cela correspond précisément au problème SetCover. Les données : des éléments (les oeuvres), et des ensembles de ces éléments (les CD qui réunissent une ou plusieurs oeuvres). Le problème : sélectionner un minimum de ces ensembles pour couvrir tous les éléments. Si vous voulez optimiser non pas le nombre de CD mais le prix total, il faut considérer la version pondérée du problème, en attribuant à chaque CD un poids qui correspond à son prix, et en cherchant à couvrir tous les éléments par des ensembles dont la somme des poids est minimale.
Illustrons cela sur les 9 symphonies de Dvorak. Le graphe biparti ci-dessous représente les CD sur la ligne du haut, les symphonies sur la ligne du bas, et chaque CD est relié aux symphonies qu'il contient.
La solution est montrée en rouge. Comment l'ai-je trouvée ? Le problème est NP-complet, il n'existe donc probablement pas d'algorithme rapide (qui s'exécutera en temps polynomial par rapport à la taille de l'entrée du problème) pour le résoudre. Cependant, il existe un moyen rapide en pratique pour de petites instances du problème : le coder par un programme linéaire en nombres entiers (cette expression barbare est déjà apparue dans le billet précédent). Vulgarisons un peu pour montrer comment ça fonctionne, en utilisant les mêmes notations que l'article Wikipedia sur SetCover : il s'agit d'associer à chaque CD appelé S une variable binaire c(S) qui prend la valeur 1 si le CD fait partie de la solution, 0 sinon. En appelant x(S) le coût du CD S, pour calculer le coût total de la solution, que l'on cherche à minimiser, il faut faire la somme (pour tout S) des x(S)*c(S). On ajoute des contraintes pour assurer que chaque symphonie est bien présente dans un des CD de la solution : pour toute symphonie e, la somme des c(S), pour l'ensemble des CD S qui contiennent la symphonie e, est supérieure ou égale à 1.
Et maintenant que le problème est ainsi formulé de manière mathématique, comment trouver les valeurs solutions pour les variables c(S) ? En théorie, on résout rapidement une relaxation du problème (c'est-à-dire la version du problème où on laisse prendre à c(S) n'importe quelle valeur entre 0 et 1, comme si on avait le droit d'acheter des portions de CD...), puis une fois cette solution trouvée, on va essayer d'en déduire (et c'est cette étape qui risque de prendre du temps) une solution où les c(S) prennent soit la valeur 0, soit la valeur 1. En pratique, on utilise par exemple le programme GLPK qui est gratuit, et s'installe aussi sous Windows. On commence par s'inspirer du fichier exemple (ou on lit la doc') pour formuler le problème dans le langage voulu, et on obtient le fichier de paramètres dvorak.mod. On exécute alors GLPK avec la ligne de commande :
"C:\Program Files\GnuWin32\bin\glpsol.exe" -m "C:\Program Files\GnuWin32\bin\examples\dvorak.mod"
La réponse s'affiche : "Optimal set cover has cost 4460 with 3 elements with sets: 3 8 16", ce qui correspond à ma solution en rouge qui coûte donc 44 euros 60.
Vous allez me dire que dans une bonne intégrale de musique classique, le prix n'est pas votre critère de sélection. Vous voulez assurer une certaine cohérence dans votre collection, en achetant toutes les symphonies enregistrées par le même orchestre ? Dans ce cas regroupez en un seul tous les ensembles qui correspondent à ces enregistrements. Vous voulez ajouter un critère de qualité ? N'utilisez pas le simple prix comme pondération, mais, par exemple, divisez-le par votre score de qualité pour chaque CD, score d'autant plus élevé que vous appréciez le CD.
Pour Dvorak, malheureusement, cette modélisation n'a pas suffi à résoudre ma quête d'une intégrale en CD, tout simplement parce que certaines oeuvres ne sont à ma connaissance pas enregistrées. En voici la liste, au cas où vous voudriez vous lancer dans des "world premiere recordings", les numéros de référence correspondent au catalogue Burghauser :
En ce début décembre, de nouveaux classements thématiques de blogs fleurissent sur Wikio. Claire, qui travaille dans leur département marketing, m'a proposé de diffuser celui des blogs en les sciences humaines. Alors ça y est, les informaticiens ont encore frappé, et leurs évaluations à la sauce bibliométrique touchent désormais la blogosphère française de la recherche en SHS ? Allez, pour se faire pardonner, on va organiser à Montpellier en juillet 2011 en satellite de TALN, un colloque (Doctorants, Informatique et Sciences Humaines) où les doctorants en informatique se mettront au service des doctorants en sciences humaines qui leur soumettront des problématiques traitables par l'outil informatique (plus de nouvelles bientôt sur ce blog et sur les canaux habituels de diffusion...).
Comme tout classement, ce qui importe est ce qu'on en fait ! Alors évidemment, le jour où l'ANR commencera à l'utiliser pour attribuer ses financements on pourra se faire du souci. Je le vois plutôt comme une façon de mettre en avant une communauté de blogueurs, et faire découvrir quelques carnets de notes virtuels qui méritent le détour (il est possible de consulter la suite du classement sur Wikio), de manière plus pertinente que la F-list et ses déclinaisons thématiques par exemple. On pourra s'étonner de l'absence de certains grands blogs français de SHS, ils sont peut-être à chercher du côté de la section Sciences de l'information. Si vous repérez d'autres grands absents, vérifiez si Wikio les connaît, signalez-les si non, et citez-les dans vos blogs si oui !
Une autre remarque : dans ce Top 20, on trouve pas moins de 8 carnets de recherche hébergés chez Hypotheses.org. Cela souligne un beau succès de cette plateforme, et je souhaite à Plume! la même réussite avec la plateforme-réseau de blogs de vulgarisation scientifique qu'ils viennent de lancer ("scientifique" inclut bien évidemment les sciences humaines !).
Et comme je n'aime pas faire uniquement du relai d'informations, j'en profite pour diffuser un autre classement polémique, fait maison : celui des villes universitaires françaises, en fonction des demandes de mutation des professeurs d'université et maîtres de conférences. Eh oui, les mathématiciens, dans leur grande bonté, ont dédié une Machine Ouverte aux Universitaires qui Veulent Echanger, qui mentionne les souhaits de mutation. On récupère tout dans un fichier tableur OpenOffice, on fait la différence pour chaque ville des demandes d'arrivée moins les demandes de départ, et on obtient, tada, un Top 15 des villes attractives pour les enseignants-chercheurs :
Pour dissuader ceux qui seraient tentés de l'utiliser de manière sérieuse, je précise que MOUVE propose aussi d'indiquer des régions souhaitées, que je n'ai pas prises en compte ici (pour une raison autre que vouloir faire figurer en tête la ville où j'ai obtenu mon doctorat : ceux qui indiquent vouloir déménager en "région parisienne" sont-ils vraiment prêts à prendre un poste indifféremment au centre de Paris, ou dans les diverses banlieues ?), et que je n'ai même pas pris le temps de refaire l'expérience sur des données à jour (celles-ci datent de mai 2010).
La Fête de la Science a commencé, elle est marquée cette année par la projection sur les murs du Panthéon de 1000 portraits de chercheurs accompagnés d'une phrase sur leur vision de l'avenir (et de vidéos sur le site du CNRS). Pierre Maraval, le photographe à l'origine de ce projet, dévoile les 1000 phrases sur son site web. Voici une visualisation des mots les plus fréquents construite avec le logiciel NuageArboré sur treecloud.org, glissez la souris sur chaque mot pour voir son nombre d'occurrences :
La question du nombre de blagues Carambar était restée sans réponse à la fin de l'épisode 1 de mon étude du nombre de citations de papillotes. El Jj s'y est collé sur son blog Choux romanesco, vache qui rit et intégrales curvilignes. De mon côté j'ai également fini de recueillir les blagues (séquences reconstituées ci-contre) de 3 paquets de Carambar qui traînaient depuis un an (j'en suis visiblement moins friand que des papillotes...), qui me permettent d'apporter quelques nouvelles précisions sur les obstacles à l'application de la "méthodologie-papillotes" à l'estimation du nombre de blagues Carambars, et de proposer des méthodes alternatives. J'avais évoqué ces deux problèmes, et El Jj mentionne également dans son billet, en les négligeant toutefois pour le calcul :
Voter pour ce billet sur Wikio
