FAKE PLASTIC TREES

On peut mesurer l'interaction de 3, 4 réparations, "ce qui reste quand on a retiré tous les sous-groupes". C'est exactement l'outil qu'il fallait pour découper le score d'une semaine en morceaux réutilisables. ça porte un nom qui m'effraie un peu, l'inversion de Möbius, mais l'idée tient en un exemple.

l'inversion de möbius

Reprenons trois réparations A, B et C, et le gain réel (rejoué dans willowengine) de chaque combinaison :

On démonte de bas en haut, en retirant à chaque fois ce qui est déjà expliqué :

les morceaux simples : A = 40, B = 5, C = 30;

la paire A+B : 70 − 40 − 5 = +25 (la synergie du dernier post);

la paire A+C : 45 − 40 − 30 = −25 (visent le même trou);

la paire B+C : 35 − 5 − 30 = 0 (peut être indépendantes);

le trio : 80 − (40 + 5 + 30) − (25 − 25 + 0) = +5,
ce que le trio apporte en plus de tout le reste.

Et dans l'autre sens, le gain de n'importe quel plan se remonte en additionnant les morceaux qu'il contient : A + B + C = 40 + 5 + 30 + 25 − 25 + 0 + 5 = 80. Voilà! On a le score sans appel lourd à l'oracle!
Le principe vient de la combinatoire, la référence est Gian-Carlo Rota, On the foundations of combinatorial theory I: Theory of Möbius functions (1964).

2^n, non.

Pour démonter, il faut le score de tous les sous-groupes. Avec à peu près 350 réparations candidates, c'est 2^350 combinaisons, y a pas assez d'atomes dans l'univers. Deux observations:

1. on démonte par ressource. Le score d'une semaine, c'est la somme des scores de chaque groupe et de chaque enseignant. Or un groupe ne voit que les réparations qui le touchent mais quelques dizaines max, pas 350. On fait donc une petite inversion par ressource (une cinquantaine par semaine en PeiP), et une réparation qui touche le groupe G4 et le prof T apparaît simplement dans les deux tables.

graph LR
        R["Réparation A"] --> G["Table du groupe G4"]
        R --> T["Table du prof T"]
        S["Réparation B"] --> G
        U["Réparation C"] --> T

        style R fill:#111,stroke:black,color:white
        style S fill:white,stroke:black,color:black
        style U fill:white,stroke:black,color:black
        style G fill:white,stroke:black,color:black
        style T fill:white,stroke:black,color:black

2. on ne garde que les sous-groupes sûrs. Inutile de démonter des combinaisons qui ne peuvent pas exister, avec une propriété importante : si un groupe est gardé, tous ses sous-groupes le sont aussi (sinon on ne pourrait plus démonter de bas en haut). Un ensemble de réparations est donc clos par le bas, si on retire une réparation de l'ensemble, il restera toujours valide.

Résultat sur l'année : 236 783 morceaux pour 36 semaines, de quelques centaines à ~24 000 par semaine selon sa densité. C'est infiniment moins que 2^350!

la chauffe

Mais démonter ça coûte cher. Il faut rejouer chaque sous-groupe sûr dans willowengine pour connaître son vrai score. Hors de question de le faire pendant que quelqu'un attend devant son écran, donc on le fait à froid et on enregistre le résultat dans un fichier, un certificat.

C'est la chauffe : on paye une fois hors ligne, et ensuite le serveur n'a plus qu'à lire.

ne recalcule que ce qui bouge

C'est là que ça devient vraiment intéressant. Quand quelque chose change, on n'a presque rien à refaire :

si une contrainte change, on retire du certificat tous les bouts qui contiennent la réparation refusée, et on cherche le meilleur plan dans ce qui reste, le rejet est devenu un filtre.

si on change la préférence étudiants / enseignants, on prépare deux certificats, un qui ne compte que le score des étudiants, un qui ne compte que celui des enseignants. Une préférence, c'est juste un mélange des deux :

score = (1 − p) × étudiants + p × enseignants

Le curseur de l'interface ne fait que changer p, les morceaux eux ne bougent pas.

Avant tout ça, changer la préférence voulait dire tout recalculer soit une petite minute d'attente. Avec la chauffe complète, on devrait servir la réponse en 0.2 seconde dans la grande majorité des cas.

la suite

Bon, les morceaux sont prêts et ça a l'air de bien marcher. Mais il reste à chercher le meilleur plan dedans. et il reste 6.7 × 10^18 combinaisons à traiter. C'est probablement le moment d'introduire la ligne de Pareto, on va pré-calculer d'un coup tous les bons compromis entre budget, étudiants et enseignants, pour qu'au runtime on ait plus qu'à choisir.

//pekmi