28 février 2011

Compléter sa CD-thèque : Set Cover pour une intégrale Dvorak ?

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 :

  • B11 intégrale des chants du cycle Cyprès,
  • B13 22 Songs,
  • B16 Alfred,
  • B22/B43 Potpourri on King and Charcoal Burner,
  • B48b Nocturne in B major (piano 4 mains),
  • B113 Festival Song,
  • B119 Gallop in E major,
  • B125 Josef Kajetán Tyl,
  • B143 Hymn of the Czech Peasants,
  • B204 Song of the Smith of Lešetín.
A défaut des enregistrements, je suis preneur d'infos sur les partitions ! Et je vous laisse découvrir le reste de son oeuvre sur le site francophone de référence sur Antonin Dvorak.

5 commentaires:

Guyslain a dit…

Cher Philippe,
ton exemple est bien choisi (si ce n'est que Liszt aurait été plus approprié). Je me demandais si je pouvais trouver des valeurs duales pour chaque symphonie, mais les symphonies 7, 8 et 9 posent problème : on peut en acheter exactement deux exemplaires pour seulement 18,39€, alors que avec ton choix tu n'as qu'un exemplaire de ces trois symphonies pour 10,95€. Donc ta solution est strictement moins bonne qu'une solution fractionnaire.
Peux-tu monter une collection avec quelqu'un d'autres et partager les droits des titres achetés ? Dans ce cas tu pourrais faire des économies.
Amicalement.

Philippe a dit…

"bien choisi" : héhé, je me disais justement qu'il serait difficile de choisir un exemple en dehors de la musique classique. Prenez votre chanteur préféré (un qui a fait plus de 4 albums pour que le problème ne soit pas complètement évident) : même si de nombreux coffrets best-of et anthologies à prix réduit sont disponibles, il est probables que certaines oeuvres rares vous forcent à acheter tout simplement tous les albums, sans pouvoir acheter les best-of pour faire baisser le coût. En effet, Liszt aurait été pas mal aussi, et pas seulement parce que les Hongrois sont des pros de l'optimisation combinatoire (il y a aussi quelques pointures à l'Université Charles), mais parce qu'on fêtera son bicentenaire le 22 octobre cette année (je ne vois pas pour l'instant d'intégrale Brilliant Classics se profiler à l'horizon, et l'intégrale de ses pièces pour piano par Howard chez Hyperion est à 173 euros 99, snif...).

Je n'ai pas montré la sortie du programme GLPK qui précise en effet que la solution optimale est fractionnaire, et qu'elle est effectivement optimisée pour obtenir une solution en nombres entiers. Quand tu parles des valeurs duales pour chaque symphonie, il s'agit de quoi exactement ? Tu parles du coût de chaque symphonie, ou bien du problème dual de trouver un nombre maximal de CD qui n'ont aucune symhponie en commun ?

Pas bête ton idée de partage, mais je doute que Madame HADOPI soit de cet avis...

Philippe a dit…

Ca alors, je parle de l'intégrale d'Howard mais il y en a une quasiment trois fois moins chère enregistrée par France Clidat chez Decca.

En fait, la notion d'intégrale est à géométrie variable (si je puis dire) : 14 CD pour France Clidat (certes, intégrale de l'oeuvre pour piano solo, mais bon, il manque les transcriptions) et 99 pour Leslie Howard. 32 pour la série "Complete Piano Music" chez Naxos (qui semble encore en cours d'enregistrement, par des pianistes différents). C'est louche, tout ça...

guyslain a dit…

Cher Philippe,
oui, je parle de donner à chaque symphonie un "prix". Si les prix que je donne sont tels que :

(1) le prix de tout cd est supérieur ou égal à la somme des prix des symphonies qui le compose,
(2) pour les cds que tu as choisi, il y a égalité,

alors (1) m'assure que tu dois payer au moins la somme des prix individuels de chaque symphonie, et (2) que tu atteins cette somme. Dans ce cas, l'optimalité de ta solution est prouvée.

Malheureusement, on ne peut pas avoir (1) et (2) à la fois dans ton exemple. Je te laisse expliquer pourquoi à tes lecteurs plus précisément, et donc leur montrer pourquoi tu dois dépenser au moins 42,85€, puisque ça c'est facile à prouver.

Amicalement.

securite sociale a dit…

très bel exemple :)