2 + 2 = 5

Dans KACHOW, j'avais écrit : "Résoudre vite, maintenant on sait faire. Mais pour rappel, le calcul s'effectue sur un seul cours, il reste très localisé. Le gain en est restreint, ce n'est qu'une réparation. Je pense à ajouter un script léger (DFS/bnb) pour cummuler ces réparations quand elles vont ensemble, pour additionner les gains."
C'est ce que j'ai fait, et additionner a tout cassé

cumuler les réparations

L'optimiseur sort pour chaque cours ses meilleures réparations locales (déplacements et cascades). Une scolarité ne va évidemment pas appliquer 300 réparations dans ADE, ce qu'on veut c'est un plan de semaine donc au plus 5, 10 ou 20 modifications, choisies pour que la semaine de tout le monde soit la meilleure possible dans ce budget de mouvements.
L'idée était un DFS qui empile les réparations compatibles (pas la même salle, pas le même prof au même moment, pas deux fois le même cours), additionne leurs gains, et garde la meilleure pile qui rentre dans le budget, magnifique!

Le DFS trouvait bien des plans. Sauf qu'en les rejouant dans willowengine, le score réel s'écartait de la somme annoncée, parfois en dessous parfois au dessus, et quelques rares fois le plan n'était même plus applicable. Le calcul était juste mais l'hypothèse était fausse :
les gains de deux réparations ne s'additionnent pas.

la paire de fous

Aux échecs, un fou vaut à peu près 3 pions, deux fous valent donc 6? Pas tout à fait : les moteurs (stockfish compris) donnent un bonus de paire de fous, parce qu'à deux ils couvrent les cases blanches et les noires, ce qu'aucun des deux ne fait seul. La valeur de la paire n'est pas la somme des valeurs des pièces.

Dans un emploi du temps c'est pareil, en pire. Exemple sur un mardi avec un gros trou l'après-midi :

Réparation A : avancer un TD de 16h45 à 13h15;

Réparation B : décaler d'une heure un cours du matin;

Réparation C : placer un autre cours dans le créneau de 13h15.

graph LR
        A["A · TD 16h45 → 13h15"] ---|"synergie (+)"| B["B · cours du matin décalé"]
        A ---|"anti-synergie (−)"| C["C · autre cours à 13h15"]

        style A fill:#111,stroke:black,color:white
        style B fill:white,stroke:black,color:black
        style C fill:white,stroke:black,color:black

A seule réduit le trou. B seule ne sert presque à rien. A et B ensemble referment la journée.

Le duo rapporte plus que la somme des deux, c'est une synergie!!.
A et C, elles, visent le même trou, chacune est bonne seule mais ensemble, la deuxième ne rapporte plus rien (quand elle peut encore se poser), c'est une anti-synergie.
Avec notre précédente hypothèse, on comptait A + C comme deux fois un bon coup.

mesurer la synergie

On peut chiffrer ça proprement. L'interaction de deux réparations, c'est ce qui reste quand on retire leurs effets isolés :

interaction(A, B) = gain(A + B) − gain(A) − gain(B)

positif : synergie;

négatif : elles se marchent dessus;

nul : elles s'ignorent (parfois une conséquence d'indépendance).

On peut faire pareil à 3, 4 réparations (ce qui reste quand on a retiré tous les sous-groupes), j'y reviendrai plus tard, je trouve que la solution mérite son propre post.

J'ai fait ce découpage sur les 36 semaines de l'année. Le score d'un plan devient une somme de petits morceaux :

• le gain propre de chaque réparation (ce que mon DFS additionnait);
• le bonus ou malus de chaque paire de réparations;
• le bonus ou malus de chaque groupe de 3 réparations ou plus.

Ensuite on regarde quelle part du score vient de chaque famille. Un malus de −50 compte autant qu'un bonus de +50.

Plus de 90% du score vient des interactions, et trier les réparations par leur gain isolé, c'est regarder 7.5% de l'information.
Un détail qui m'a le plus surpris : à l'ordre 2, il y a deux fois plus d'interactions négatives que positives (90 629 contre 45 794). Les réparations se gênent beaucoup plus souvent qu'elles ne s'entraident, en général parce qu'elles visent le même trou, la même salle ou le même prof, ce qui me conforte dans l'idée que de nouvelles hypothèses valides exploseraient la qualité des plans générés.

problème du sac à dos

Formellement, on résolvait un sac à dos, càd chaque réparation a un poids (son nombre de modifications) et une valeur, on remplit au mieux un sac de capacité B. C'est un problème super classique et très parcouru,,, à condition que les valeurs s'additionnent. Quand on ajoute un bonus ou un malus par paire, on tombe sur le sac à dos quadratique (Gallo, Hammer et Simeone, 1980, puis le très bon survey de David Pisinger, The quadratic knapsack problem—a survey, 2007), déjà bien plus dur. Nous, on a aussi des interactions d'ordre 3, 4, 5...

Sur les 36 semaines, à paramètres égaux :

*mesures faites avant d'avoir aligné une règle de battement (15 min entre deux cours), l'ordre de grandeur tient après.

Plus le budget grandit, plus il y a de paires et de triplets dans le plan, et plus l'erreur additive se creuse : presque 15% du gain perdus à 10 modifications. Sur une semaine, c'est la différence entre « le trou du mardi disparaît » et « il est un peu plus petit ».

la suite

Pour choisir les bonnes réparations, il faut un modèle qui connaisse toutes ces interactions, et une recherche exacte capable de s'en servir sans exploser : choisir 10 réparations parmi ~350 candidates, c'est environ 6.7 × 10^18 combinaisons. Un DFS ne suffira pas, il faut un vrai moteur de sélection, voilà que naît SPARROW.
Je pense qu'une bonne suite serait de creuser la façon de démonter le score d'une semaine en petits morceaux réutilisables. Je pense que ça nous permettrait de gérer les changements de contraintes en ne devant recalculer que les réparations touchées.

//pekmi