L'ingénierie de la décision

Ce que le parcours a mis sur la table

Chaque chapitre a apporté une méthode, et chaque méthode a son prix. Le tableau les rassemble, avec ce que chacune demande avant de rendre quoi que ce soit.

Tous ces chapitres ont produit des chiffres, et aucun n'a dit laquelle choisir. La première partie de celui-ci le dit, pour la plaque P-600 comme pour un autre problème, et montre surtout comment on peut se tromper en le disant.

Comparer pour de bon

Le chapitre sur le recuit simulé a posé cinq règles, à propos de deux méthodes. Elles tiennent en une phrase : plusieurs graines, la meilleure, la médiane et la pire, à budget égal, avec l'écart à une référence, des réglages faits avec le même soin sur d'autres graines. Elles valent pour toutes les méthodes. Ce qui change avec dix méthodes, c'est le risque de tricher sans le vouloir, parce que chaque comparaison de plus offre une occasion de plus de choisir le budget, la graine ou le réglage qui arrange.

Le protocole, écrit une fois

Un protocole refait à la main à chaque comparaison finit bâclé. Il vaut mieux l'écrire une fois : une fonction par méthode, qui reçoit un budget et une graine et rend le coût de la meilleure solution trouvée, puis une boucle qui les lance toutes sur les mêmes budgets et les mêmes graines. Le programme qui suit applique ce protocole à un second problème de Valdrome, plus grand que celui du chapitre 5 : trente opérateurs à répartir sur trente postes, dont les temps sont engendrés par une formule reproductible (graine 1). Deux méthodes y sont comparées, les redémarrages de descentes et le recuit, avec le budget compté en évaluations : une par voisin examiné pour les descentes, une par itération pour le recuit, dont on retire les 200 évaluations qui ont servi à régler la température. Une évaluation se calcule ici avec quatre lectures de la matrice, comme pour un 2-opt : variation rend ce que change l'échange de deux postes.

La référence n'est pas cherchée mais calculée. L'affectation est un problème pour lequel un algorithme exact rend l'optimum en un temps qui ne compte pas : linear_sum_assignment, de scipy, qui implémente l'algorithme hongrois. La suite y revient : c'est une leçon en soi.

Le programme affiche d'abord, pour chaque budget et chaque méthode, la meilleure, la médiane et la pire des dix graines, avec leur écart à l'optimum de 255 minutes. À 500 évaluations, la médiane des redémarrages est à 104,5 % de l'optimum : une descente depuis un ordre tiré au hasard demande, sur trente postes, bien plus de 500 évaluations, et le budget est épuisé avant qu'elle soit finie. Le recuit, lui, est à 21,6 % : chaque évaluation lui sert. À 2 000 évaluations l'écart reste net (72,0 % contre 7,5 %). À 10 000, il se resserre : 7,6 % pour les redémarrages, 4,5 % pour le recuit.

La suite de l'affichage montre trois façons de lire ces mêmes nombres, et l'une seulement est honnête.

• Une seule graine. Au budget de 10 000 évaluations, le recuit bat les redémarrages sur 8 graines sur 10. Sur les 2 autres, c'est l'inverse : qui aurait comparé les deux méthodes sur une graine aurait pu annoncer le contraire, avec les mêmes programmes.
• Le meilleur tirage. À 10 000 évaluations, 259 minutes contre 265 : un écart de six minutes, qui ne dit rien de ce qu'on obtient d'ordinaire. La médiane, 266,5 contre 274,5, et surtout le pire tirage, 273 contre 289, en disent davantage.
• Le profil de performance, dernière ligne du programme : la part des tirages qui restent à moins de $x$ % de l'optimum. Avec 10 000 évaluations, aucun tirage de redémarrages n'est à moins de 2 %, un sur dix à moins de 5 %, sept sur dix à moins de 10 % ; pour le recuit, un sur dix, six sur dix, et tous. C'est la distribution entière, résumée en trois seuils. Lue le long de l'axe des budgets au lieu de l'axe des écarts, la même information donne la courbe « qualité en fonction du budget » : pour chaque budget, la médiane, et la bande du meilleur au pire tirage.

Un dernier mot sur ce programme : il tient en une centaine de lignes, budgets, graines et référence compris. Le protocole n'est pas un luxe de chercheur, c'est un petit outil, et il se réutilise tel quel pour la méthode suivante.

Toutes les méthodes sur la plaque P-600

La comparaison qui précède oppose deux méthodes sur un problème que ce chapitre vient d'introduire. La figure suivante en oppose neuf sur la plaque P-600 des chapitres 5 à 9, dont l'optimum, 2 788,70 mm, est prouvé. Chaque méthode est écrite comme dans son chapitre, avec le même décompte du budget : là où ces chapitres publient un résultat (le recuit et les redémarrages du chapitre 6, GRASP et les fourmis à 300 000 et à un million d'évaluations, le mémétique à 100 000), les dix premières graines redonnent exactement les nombres publiés. Les réglages sont ceux des chapitres pour le recuit, le tabou, GRASP, les fourmis et le mémétique, cherchés sur des graines à part pour le génétique (la section qui suit le dit). Les tirages ne sont pas calculés dans la page : ils ont été faits une fois, vingt graines par méthode et par budget, par un script du dépôt.

• PPV + 2-opt : le plus proche voisin du chapitre 4, puis la descente du chapitre 5. Aucun hasard : une seule valeur.
• Redémarrages : des descentes 2-opt depuis des ordres tirés au hasard, tant que le budget le permet.
• GRASP : un plus proche voisin randomisé, puis la descente, recommencés (chapitre 9).
• Recuit : le chapitre 6, à 5 % de dégradations acceptées au départ.
• Tabou : le chapitre 7, durée 30.
• Génétique : une population de cinquante tournées, croisement OX, mutation par inversion, sans recherche locale (chapitre 8).
• Mémétique : six tournées, chaque enfant étant amélioré par des tirages 2-opt (chapitre 8).
• Fourmis et Fourmis + 2-opt : la variante Max-Min du chapitre 9, avec et sans descente de la meilleure tournée de chaque itération. L'Ant System, dominé par Max-Min au chapitre 9, n'est pas repris.

La question posée est celle du directeur : pour un budget donné, laquelle confier à l'atelier ? La figure demande de miser avant de voir, sur quatre budgets, de 100 000 à 3 millions d'évaluations. Rien des résultats n'apparaît avant la mise, ni la référence.

Le tableau suivant est la mémoire de la figure : l'écart de la médiane à l'optimum, pour chaque méthode et chaque budget. À lire après avoir joué.

Sept constats, chacun dans son cadre : cette plaque, ces réglages, vingt graines.

• Une construction suivie d'une descente est un concurrent sérieux à petit budget. Le plus proche voisin puis le 2-opt donne 5,57 % au-dessus de l'optimum, une seule fois, pour 26 596 évaluations. À 100 000 évaluations il fait mieux que les redémarrages (7,26 %), le tabou (7,26 %), le génétique (6,01 %) et les fourmis Max-Min (17,2 %), sans aucun réglage.
• Redémarrages et tabou ne sont pas encore différents à 100 000 évaluations. Une descente depuis un ordre tiré au hasard demande de l'ordre de cent mille évaluations sur soixante trous : à ce budget, les deux méthodes sont la même descente, interrompue au même endroit, d'où des écarts identiques. La mémoire du tabou n'a pas encore servi. Elles se séparent à 300 000 (4,23 % contre 2,71 %).
• GRASP fait mieux que les redémarrages à chaque budget (2,90 % contre 7,26 % à 100 000, 0,64 % contre 1,14 % à 3 millions) : partir d'une construction gloutonne randomisée épargne à la descente la moitié de son chemin.
• Sans recherche locale, les fourmis perdent : 17,2 % à 100 000 évaluations, 3,71 % à 3 millions. Avec la descente de la meilleure tournée de chaque itération, elles passent de 3,25 % à 0,70 %. C'est la conclusion du chapitre 9, et elle se lit ici sur quatre budgets.
• Le génétique seul progresse lentement, de 6,01 % à 1,39 %, et le mémétique le devance à chaque budget (3,69 % contre 6,01 % à 100 000 évaluations), l'écart se réduisant à 3 millions (1,36 % contre 1,39 %). Le réglage pèse plus lourd que la méthode : avec le réglage de départ du chapitre 8 (cent individus, tournoi de trois, mutation à 30 %), le génétique seul est à 17,1 % à 100 000 évaluations ; le réglage cherché sur d'autres graines, dans une grille de douze, le ramène à 6,01 %, avec le même programme.
• Le recuit est en tête à un et trois millions d'évaluations (0,58 % et 0,59 %), avec des meilleurs tirages à 0,00 %, c'est-à-dire l'optimum. À 3 millions, GRASP (0,64 %) et les fourmis avec 2-opt (0,70 %) ne s'en distinguent guère.
• Le vainqueur dépend de ce qu'on regarde. À la médiane, c'est le recuit à 100 000 évaluations, les fourmis avec 2-opt à 300 000, le recuit encore à un et trois millions. Au meilleur tirage, à 100 000 évaluations, c'est GRASP (0,31 % contre 0,40 % pour le recuit) ; à 300 000, trois méthodes tombent sur l'optimum. Annoncer « le recuit a trouvé l'optimum à 300 000 évaluations » est exact, et c'est la moins représentative des phrases vraies : sa médiane à ce budget est à 1,56 %.

Un rang ne se lit pas sans les tirages. À 300 000 évaluations, quatre méthodes sont à moins de quatre dixièmes de point l'une de l'autre (1,19 %, 1,31 %, 1,54 %, 1,56 %), et les bandes de la figure se recouvrent : c'est pourquoi elle liste les méthodes dont la médiane tombe dans la boîte du premier. Le recuit en donne un exemple : sa médiane est à 1,56 % à 300 000 évaluations et à 0,83 % à 210 000 (le budget d'une demi-seconde, plus bas), un écart près du double de celui qui sépare le premier du quatrième de ces méthodes. Avec vingt graines, la médiane d'une méthode au hasard bouge de quelques dixièmes de point d'un budget voisin à l'autre.

Une évaluation n'est pas une seconde

Le budget en évaluations a un mérite, celui du chapitre 6 : il ne dépend ni de la machine ni du langage. Il a un défaut, que la figure précédente ne montrait pas : une évaluation ne coûte pas la même chose selon la méthode. Celle d'un voisin 2-opt tient en quatre lectures d'une matrice de distances. Celle d'un génétique est la longueur d'une tournée entière, soixante et une lectures. Celle d'un recuit est un tirage de deux positions, un test d'acceptation et, parfois, un retournement de segment. Le tableau donne les débits mesurés, pour ces programmes Python, sur le poste qui a produit les tirages.

Une évaluation de génétique coûte 27 fois celle d'une descente, celle d'un recuit 7 fois. Les autres se ressemblent : le budget des fourmis compte les candidats examinés, une unité bon marché, et celui du mémétique un tirage 2-opt, à peine plus cher qu'un voisin de descente. Comparer à évaluations égales revient donc à donner au génétique 27 fois plus de temps qu'à une descente, et au recuit 7 fois plus. La figure suivante refait la comparaison à temps de calcul égal : chaque méthode reçoit le même nombre de secondes, et donc le nombre d'évaluations que son débit permet (la colonne « Évaluations permises » du tableau sous la figure le dit).

Le classement se réordonne, et il faut lire les évaluations permises pour comprendre pourquoi. Une demi-seconde donne à GRASP, aux redémarrages et au tabou plus d'un million d'évaluations, mais au recuit 210 k et au génétique 52 k. À 2 secondes, GRASP est en tête (0,41 %), suivi des redémarrages (0,69 %) et des fourmis avec 2-opt (0,70 %) : les redémarrages, dans les derniers à 100 000 évaluations, sont deuxièmes, parce que 100 000 évaluations de descente ne demandent que quelques centièmes de seconde. À 8 secondes, GRASP est à 0,10 % et les redémarrages à 0,26 %, devant le recuit (0,52 %), qui a eu le temps de refroidir. Les fourmis Max-Min, qui perdaient à un million d'évaluations, retrouvent 0,70 % avec 45 millions d'évaluations : il leur fallait du temps, pas une autre méthode. Le tabou, à durée fixe de 30 pas, plafonne (1,73 % à 8 secondes). Le génétique, le plus coûteux par évaluation, reste loin (2,82 %).

Ces classements sont ceux de ces programmes Python, pas ceux des méthodes. Un recuit écrit dans un langage compilé ferait cent fois plus d'itérations par seconde, une descente vectorisée aussi, et les rapports changeraient. Ce qui se retient n'est pas un rang, c'est un geste : mesurer les deux unités, et dire laquelle a servi à égaliser. Un budget en évaluations dit ce que coûte un algorithme, un budget en secondes dit ce que coûte un programme, et c'est le second que paie l'atelier.

Un second problème : trente postes

Le classement obtenu sur la plaque n'est pas une propriété des méthodes. Il suffit de changer de problème pour s'en convaincre : la figure suivante reprend les trente postes du début du chapitre, avec six méthodes (les fourmis, propres aux tournées, n'y jouent pas ; le mémétique non plus) et quatre budgets de 10 000 à 500 000 évaluations. Le voisinage est l'échange de deux postes, l'évaluation celle d'une affectation entière, et l'optimum exact est 255 minutes.

Le vainqueur n'est plus le même, et les places non plus. GRASP a la meilleure médiane à chaque budget (3,14 %, 1,96 %, 1,18 %, 0,78 %), à égalité avec la règle par case suivie d'une descente à 10 000 évaluations (3,14 %, sans le moindre hasard) et avec le recuit à 500 000 (0,78 %). Le tabou est deuxième à 30 000 et à 100 000 évaluations (2,75 % et 1,37 %), lui qui est dans le bas du classement de la plaque. Le recuit, en tête de la plaque à 100 000 évaluations, est ici troisième à 10 000, 30 000 et 100 000. Le génétique est dans le bas du classement, sauf à 500 000 évaluations. Quant à la règle par case suivie d'une descente, elle coûte 3 046 évaluations et donne 3,14 % : elle bat les redémarrages, le génétique et le recuit à 10 000 évaluations, et les redémarrages et le génétique à 30 000. Il faut savoir la mettre dans la comparaison, parce qu'elle bat des métaheuristiques réglées avec soin. Les redémarrages et le tabou sont, ici encore, la même descente tant que le budget est court.

Et l'algorithme hongrois rend 255 en un instant. Ce constat mérite qu'on s'y arrête : sur ce problème, aucune de ces comparaisons n'avait d'enjeu pratique. Elles servent à s'exercer là où la réponse est connue, ce qui est précisément la manière d'apprendre à juger une méthode avant de l'appliquer là où elle ne l'est pas.

Le même soin pour chacun

La règle 5 dit que les réglages se font avec le même soin, sur d'autres graines que celles qui jugent. Ici, les graines de jugement sont 0 à 19, et les réglages ont été cherchés sur les graines 100 à 104 pour la plaque, 100 à 109 pour les postes, par une grille par méthode. Le tableau donne ce qui a été essayé, et ce qui a été retenu.

Chaque grille est tenue par une médiane sur cinq graines (dix pour les postes), à un budget donné. C'est peu : les réglages retenus sont un bon choix, pas le bon. Trois retenues ne sont d'ailleurs pas la meilleure médiane de leur grille. Le recuit garde 5 %, milieu du plateau du chapitre 6, alors que 10 % fait 1,3 % contre 1,8 %. GRASP garde alpha à 0,05, celui du chapitre 9, alors que 0,5 fait 1,4 % sur cinq graines contre 1,9 % : la courbe des médianes n'est pas monotone (0,2 fait 4,2 % quand 0,5 fait 1,4 %), signe que cinq graines ne distinguent pas ces valeurs. Le mémétique garde les six individus du chapitre 8, alors que dix font 1,5 % contre 2,0 %. Et le nombre de réglages ouverts n'est pas le même d'une méthode à l'autre, ce qui est dans leur nature : une méthode à trois paramètres coûte plus d'essais qu'une méthode à un paramètre. Ce qu'exige la règle, c'est que chacune ait reçu une recherche honnête, pas le même nombre d'essais.

Ce qui fausse une comparaison

Métaheuristique maison ou solveur

Toute la partie précédente a mesuré des méthodes que le parcours a écrites à la main, avec quelques dizaines de lignes chacune. Avant de mettre l'une d'elles en production, il faut se demander si elle est nécessaire : il existe des logiciels dont c'est le métier de résoudre ce genre de problème, écrits par des équipes qui y passent leur vie.

Ce que font les solveurs

Ce qui les distingue des méthodes du parcours tient en trois traits. Ils exigent un modèle : le problème doit s'écrire dans le langage de l'outil (des inéquations linéaires, des contraintes prédéfinies, un graphe de distances), là où une métaheuristique n'exige qu'un coût à évaluer. Ils donnent une garantie : une borne, un écart, parfois une preuve, quand une métaheuristique ne rend qu'une solution. Et ils sont écrits par d'autres, testés pendant des années sur des milliers de cas, ce qui se paie en dépendance à une bibliothèque et en une part d'opacité.

Le même problème, deux solveurs

L'ordonnancement des dix ordres du chapitre 4 (somme des retards, optimum de 17 heures) s'écrit pour les deux premiers solveurs. Pour milp, il faut le rendre linéaire. Le modèle indexé par le temps le fait : une variable binaire $x_{j,t}$ vaut 1 si l'ordre $j$ commence à l'heure $t$. Le retard d'un ordre est alors connu d'avance pour chaque $t$, donc l'objectif est une somme de coûts fixes. Chaque ordre commence une fois ; à chaque heure, la machine fait au plus un ordre.

Le nombre de variables croît comme $n \times H$, produit du nombre d'ordres par l'horizon : c'est le prix d'un modèle linéaire qui discrétise le temps. Pour dix ordres, ce prix est modeste.

Le solveur rend un statut, 0 (optimum prouvé), une somme des retards de 17 heures, un ordre (l'un des douze qui atteignent 17 heures), et un écart à la borne de zéro : c'est la preuve. Le modèle a 424 variables et 56 contraintes.

Le même problème pour CP-SAT s'écrit autrement : une variable entière par ordre, son heure de début, un intervalle par ordre, et une seule contrainte, add_no_overlap, qui dit qu'il n'y a qu'une machine. Le code n'est pas exécutable dans la page : OR-Tools n'est pas disponible dans le moteur Python du navigateur. Il se lance sur un poste, après pip install ortools, et il est montré ici dans un encadré de texte que le site n'exécute jamais.

from ortools.sat.python import cp_model

DUREES = [2, 3, 2, 2, 5, 5, 2, 9, 7, 9]
ECHEANCES = [29, 37, 17, 27, 18, 31, 20, 26, 11, 32]
n, horizon = len(DUREES), sum(DUREES)

modele = cp_model.CpModel()
debuts = [modele.new_int_var(0, horizon, f"debut_{i}") for i in range(n)]      # une variable entiere par ordre
intervalles = [modele.new_fixed_size_interval_var(debuts[i], DUREES[i], f"ordre_{i}") for i in range(n)]
modele.add_no_overlap(intervalles)                       # une seule machine : jamais deux ordres a la fois

retards = []
for i in range(n):
    retard = modele.new_int_var(0, horizon, f"retard_{i}")
    modele.add(retard >= debuts[i] + DUREES[i] - ECHEANCES[i])       # le retard vaut au moins le depassement
    retards.append(retard)
modele.minimize(sum(retards))                            # et la minimisation le pousse a n'en valoir pas plus

solveur = cp_model.CpSolver()
solveur.parameters.max_time_in_seconds = 10
statut = solveur.solve(modele)
print(solveur.status_name(statut), "retards :", int(solveur.objective_value))
print("ordre :", [f"O{i + 1}" for i in sorted(range(n), key=lambda i: solveur.value(debuts[i]))])
print("borne :", solveur.best_objective_bound)

Les deux modèles rendent les mêmes 17 heures, et leurs formes diffèrent : le premier discrétise le temps et compte 424 variables, le second en a dix, avec des intervalles, et se lit presque comme l'énoncé. L'ordre affiché peut changer d'un lancement à l'autre : plusieurs ordres valent 17 heures, et un solveur qui travaille en parallèle n'a aucune raison de toujours tomber sur le même. Pour dix ordres, CP-SAT rend l'optimum en environ un dixième de seconde.

Quand le solveur gagne

Il gagne, et souvent de loin, dans quatre situations.

• Un modèle propre. L'ordonnancement ci-dessus, l'affectation, la découpe de barres (chapitre 3) : les contraintes s'écrivent, l'objectif est linéaire.
• Une instance de taille moyenne. Le solveur passe là où l'énumération et les métaheuristiques n'ont qu'une réponse approchée.
• Une preuve utile. Savoir que la solution est à 0 % de l'optimum, ou à au plus 2 %, change ce qu'on peut promettre.
• Des contraintes qui changent souvent. Ajouter une contrainte est ajouter une ligne au modèle, sans relire la recherche.

Le programme suivant en donne une démonstration qui touche le parcours de près. Il recalcule, dans la page, l'optimum de la plaque P-600, celui que les chapitres 5 à 9 emploient depuis le début comme référence : un modèle en nombres entiers avec une variable binaire par arête, deux arêtes par point, et des coupes de sous-tours ajoutées tant que la solution comporte plusieurs boucles. C'est ainsi que les solveurs traitent le voyageur de commerce : on relâche la contrainte de connexité, on résout, on regarde, on ajoute ce qui manque.

Quatre tours de résolution suffisent : la première solution, sans contrainte de connexité, fait 2 607,22 mm en onze boucles, la deuxième 2 698,48 en sept, la troisième 2 756,18 en deux, la quatrième 2 788,70 en une seule. La borne monte à chaque tour et rejoint la solution : l'optimum est prouvé. Il fallait une demi-seconde de calcul sur un poste, et de quelques secondes à une dizaine dans la page, dont une bonne part sert à charger la bibliothèque.

Et c'est mieux que tout ce que la première partie a mesuré : à une demi-seconde, les meilleures médianes des méthodes du parcours sont à près d'un pour cent de l'optimum, quand le solveur donne l'optimum, et sa preuve. La bibliothèque de routage d'OR-Tools, avec la construction et la recherche locale guidée d'un seul appel (code plus bas), rend 2 790,44 mm, soit 0,06 % au-dessus de l'optimum, avec un dixième de seconde de recherche.

from math import dist
from ortools.constraint_solver import pywrapcp, routing_enums_pb2

# POINTS : le depart (0, 0) puis les 60 trous de P-600, comme au chapitre 5.
N = len(POINTS)
ECHELLE = 100                                    # OR-Tools calcule en entiers : des centiemes de millimetre
DISTANCE = [[round(dist(a, b) * ECHELLE) for b in POINTS] for a in POINTS]

gestionnaire = pywrapcp.RoutingIndexManager(N, 1, 0)          # N points, un vehicule, depart au point 0
routage = pywrapcp.RoutingModel(gestionnaire)
cout_de_l_arc = routage.RegisterTransitCallback(
    lambda i, j: DISTANCE[gestionnaire.IndexToNode(i)][gestionnaire.IndexToNode(j)])
routage.SetArcCostEvaluatorOfAllVehicles(cout_de_l_arc)

reglages = pywrapcp.DefaultRoutingSearchParameters()
reglages.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC   # construire (chapitre 4)
reglages.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH  # puis chercher
reglages.time_limit.FromMilliseconds(500)

solution = routage.SolveWithParameters(reglages)
i, ordre = routage.Start(0), []
while not routage.IsEnd(i):
    ordre.append(gestionnaire.IndexToNode(i))
    i = solution.Value(routage.NextVar(i))
longueur = sum(dist(POINTS[a], POINTS[b]) for a, b in zip(ordre, ordre[1:] + ordre[:1]))
print(f"{longueur:.2f} mm")

Quand cesse-t-on d'y arriver ? Sur les n premiers trous de la même suite de plaques, le même modèle, avec les coupes ajoutées de la même façon, donne les temps suivants, mesurés sur le poste qui a produit les tirages. La colonne de droite donne l'écart à l'optimum de la bibliothèque de routage, pour trois durées de recherche.

L'exactitude coûte de plus en plus cher : de l'ordre de 0,3 seconde pour soixante trous, 9,8 secondes pour cent, 40 secondes pour deux cents et 2,5 minutes pour trois cents, avec ce modèle et cette façon simple d'ajouter les coupes (un solveur spécialisé, Concorde, irait bien plus loin). Le routage d'OR-Tools a l'allure inverse. Il est excellent sur soixante trous (0,06 % au-dessus de l'optimum dès un dixième de seconde), et perd du terrain à court terme quand la plaque grandit : à deux cents trous, 6,89 % au bout d'une demi-seconde et 5,89 % au bout de cinq secondes ; à trois cents, 7,29 % puis 1,81 %. Il donne donc, en cinq secondes, une tournée à 1,81 % de l'optimum là où l'exact demande 2,5 minutes. Le temps de l'exact dépend de l'instance autant que de sa taille : cent cinquante trous se sont résolus plus vite que cent. Ce compromis, une bonne solution vite ou la meilleure plus tard, est celui d'une métaheuristique, et la bibliothèque le propose déjà écrit.

Quand la métaheuristique maison gagne

Elle gagne, mais sur d'autres critères que la qualité brute d'un problème standard, où on vient de voir que le solveur la bat.

• Un coût qui ne s'écrit pas comme un modèle : non linéaire, calculé par une simulation, qui dépend de la séquence entière. Une métaheuristique n'exige qu'une fonction cout(solution).
• Une très grande instance, hors de portée de l'exact et du routage standard, où il faut une solution acceptable en un temps fixé.
• Le temps réel : une recherche qui peut être interrompue à tout instant en rendant la meilleure solution vue, et qui repart de la solution courante quand un ordre arrive.
• Des contraintes bizarres, propres à l'atelier, qu'aucune contrainte prédéfinie ne dit.
• Le contrôle : pas de dépendance, un code qu'on lit en entier, qui s'exécute sur n'importe quelle machine, et dont chaque décision de la recherche s'explique.

Un exemple montre le premier point. La perceuse de Valdrome perce la plaque P-217 en 12 trous. Deux trous à moins de 40 mm l'un de l'autre, percés à trois rangs d'écart au plus, chauffent la tôle localement, qui doit refroidir : deux secondes d'attente par paire. Le coût réel n'est plus la longueur, c'est un temps qui dépend de la séquence par fenêtre glissante, ce qu'un modèle qui compte des arêtes ne voit pas. Pour le squelette du chapitre 5 et la règle du chapitre 6, une seule fonction change.

La tournée la plus courte, celle qui fait 633,23 mm, coûte 37,1 secondes : 21,1 s de déplacement, et huit paires percées trop vite, qui ajoutent 16 s d'attente. La meilleure tournée trouvée par la même recherche avec le nouveau coût est plus longue en distance (806,44 mm, 27 % de plus) et plus courte en temps réel (28,9 s, 22 % de moins) : elle ne garde qu'une paire trop rapprochée. Les six recherches rendent la même valeur, ou presque (la pire fait 30,1 s). Le coût était faux, la solution du chapitre 5 était optimale pour lui, et changer la fonction a suffi. C'est ce qu'on gagne à écrire la recherche soi-même.

Choisir

La bonne pratique est souvent de faire les deux : un solveur pour la référence sur les instances qu'il traite, qui sert d'étalon, et pour les décisions où il passe ; une méthode écrite pour le reste, jugée contre cet étalon avec le protocole de la première partie. C'est ce parcours.

Faire vivre la décision dans l'entreprise

Un solveur ou une métaheuristique rend une solution. Une entreprise a besoin d'une décision, c'est-à-dire d'une solution que quelqu'un exécute, à qui on peut l'expliquer, et qui tient jusqu'au lendemain. Les paragraphes qui suivent racontent une semaine de Valdrome, la semaine 41, et ce qui s'y passe entre le plan calculé et l'atelier.

D'où viennent les données

Le plan des dix ordres du chapitre 4 s'appuie sur des durées et des échéances. Elles viennent de l'ERP de l'entreprise : les temps standards du bureau des méthodes, qui donnent la durée d'un ordre, et les échéances promises aux clients. Ces données ne sont pas fausses, elles sont approximatives d'une manière biaisée : un temps standard est mesuré dans de bonnes conditions, un ordre réel a des reprises, des attentes de matière, des changements d'équipe. Sur ce genre de données, un plan optimal sur le papier peut être un mauvais plan pour l'atelier.

Le programme mesure la différence. Il tire des durées « réelles » plus longues que les temps standards (de 10 % de moins à 40 % de plus, 15 % de plus en moyenne), et juge trois plans sur 2 000 semaines simulées : l'optimum du papier (17 heures), l'échéance croissante (23 heures), et un plan robuste, cherché en minimisant la moyenne des retards sur un lot de 100 semaines simulées, différent du lot qui juge.

L'optimum du papier, qui n'a que 17 heures de retard avec les temps standards, en a 48,1 heures en moyenne dès que les durées bougent, et 65,1 heures une semaine sur dix. Le plan robuste a 25 heures de retard sur le papier, huit de plus, et 37,6 heures en moyenne : dix heures de mieux, avec un pire cas de 56,7 heures contre 88,1. Il ne fait pas mieux sur le papier, il fait mieux sur l'atelier. Deux enseignements. Le premier : la qualité d'un plan se juge sur les données qu'on aura, pas sur celles qu'on a, ce qui demande de mesurer l'écart entre le standard et le réel, dans l'historique de l'ERP. Le second : le prix d'une donnée fausse est plus grand que celui d'une méthode médiocre. Régler à un pour cent près un recuit sur des durées qui se trompent de quinze pour cent est un travail sans objet.

Ce que le chef d'atelier voit en premier

Le solveur rend son plan, 17 heures de retard. Le chef d'atelier le regarde : « il me fait changer de montage six fois en dix ordres ». Personne n'avait posé la question, au moment de recueillir les données, et pourtant changer de montage coûte deux heures. La contrainte n'était écrite nulle part, et il n'y avait aucun moyen de la connaître sans lui montrer une solution : la première solution est un outil pour révéler le modèle.

Le programme suivant l'ajoute. Chaque ordre exige un montage (A, B ou C) et deux heures s'ajoutent à chaque changement. La recherche est celle du chapitre 5, et une seule fonction change, le calcul du planning. Il affiche ensuite, pour le nouveau plan, ce qui répond à la question suivante : pourquoi cet ordre ?

Le plan du papier, l'un des douze ordres à 17 heures (celui du chapitre 4), coûte 68 heures une fois les réglages comptés, avec six changements de montage ; le meilleur de ces douze ordres en coûte 54, le pire 94 (énumération des 3 628 800 ordres, hors de la page). Le plan de l'atelier, cherché avec le nouveau coût, fait 37 heures, avec trois changements seulement : O9 et O5 sur le montage C, puis O3, O7, O8 et O1 sur le A, puis O4, O2 et O6 sur le B, et O10, du montage C, en dernier. C'est l'unique optimum : la même énumération le confirme.

Le tableau qui suit le plan est l'explication. La dernière colonne donne, pour chaque paire d'ordres voisins, ce que coûterait de les intervertir. Le chef d'atelier y lit que passer O3 avant O5 ferait perdre 25 heures, et O4 avant O1 15, parce que deux changements de montage s'ajouteraient, alors que deux ordres du même montage se remplacent presque sans effet (O9 et O5 : une heure, O3 et O7 : une heure, O2 et O6 : une heure). Il peut contester un rang en connaissant son prix. Un plan sans cette colonne est une décision à prendre sur parole, et il n'est pas suivi longtemps.

Un solveur absorbe la même contrainte, à un prix différent : en CP-SAT, il faut écrire une variable booléenne par paire d'ordres et une condition de séparation qui inclut le réglage, soit 45 booléens et 90 contraintes conditionnelles. Le modèle rend les mêmes 37 heures, en une seconde environ. La métaheuristique a changé une fonction de six lignes, le solveur a demandé de réécrire le modèle. Aucune des deux voies n'est meilleure par principe : la première est plus souple, la seconde donne une preuve.

Le plan du lendemain

Le plan de 37 heures est retenu. Le lendemain matin, un onzième ordre arrive : O11, 4 heures, échéance 24, montage B. Les deux premiers ordres du plan sont déjà lancés et ne bougent plus. Il faut replanifier. Le plus simple est de tout recalculer. Le résultat peut être très différent du plan de la veille : les opérateurs avaient préparé les gabarits, les matières étaient sorties.

Le programme mesure la stabilité. Il compte, pour un plan, le nombre d'anciens ordres dont le rang a changé (O11 mis à part), et compare cinq plans : l'insertion de O11 à sa meilleure place sans rien déplacer, le recalcul complet, et trois recherches qui ajoutent au coût un poids par ordre déplacé.

Trois lectures. Insérer sans rien bouger donne 61 heures de retard et aucun ordre déplacé. Tout recalculer donne 52 heures, 9 de moins, mais en déplace 5 : c'est le prix de la stabilité, 9 heures de retard pour éviter de toucher 5 ordres. À retards égaux, la recherche ne voit aucune raison d'en déplacer moins : un poids de 1 heure par ordre déplacé retrouve 52 heures de retard avec 4 ordres déplacés seulement, sans rien perdre. Le poids n'est pas un réglage de technicien : c'est ce qu'une heure de désordre coûte à l'atelier, et il se demande au chef d'atelier. Vers 3 heures par ordre, la recherche préfère ne plus rien bouger, et retombe sur l'insertion minimale à 61 heures.

L'horizon gelé (les deux premiers ordres) est le second outil : ce qui est lancé ne se replanifie pas. Une méthode qui l'ignore propose des plans que l'atelier ne peut pas suivre.

Temps de calcul, maintenance, humain dans la boucle

Trois questions d'ingénierie restent, et aucune n'a de programme.

Le temps de calcul acceptable dépend de qui attend.

Une métaheuristique a cette propriété que le chapitre 6 a fait voir sans la nommer : elle est interruptible. On l'arrête à la seconde voulue, elle rend la meilleure solution vue. Un solveur en nombres entiers a une propriété voisine (une limite de temps, et l'écart à la borne rendu avec la meilleure solution), mais sa première solution peut arriver tard.

La maintenance. Le code qui décide devra être relu, corrigé, porté sur une nouvelle version de la bibliothèque, par quelqu'un qui ne l'a pas écrit. Trois pratiques comptent. Tester avec le protocole de comparaison, réduit : sur les petites instances où l'optimum est connu, la médiane de l'écart doit rester sous un seuil ; si une modification le dégrade, le test le dit. Fixer les graines dans les tests, pour qu'ils soient reproductibles, et les tirer au hasard en production. Écrire le modèle : la décision, les contraintes, la fonction de coût, ce qui a été volontairement laissé de côté. Un modèle est une hypothèse, et une hypothèse non écrite ne se discute pas. Tests et automatisation ont leur chapitre dans le parcours de génie logiciel. Enfin, le plus simple qui tienne : un plus proche voisin suivi d'un 2-opt, sans réglage, est plus facile à reprendre qu'un recuit, et le recuit plus facile qu'un génétique.

L'humain dans la boucle. L'outil propose, le chef d'atelier décide. Trois fonctions le rendent possible : verrouiller un ordre à un rang (l'horizon gelé en est un cas), interdire une séquence, et chiffrer une dérogation : « faire passer O10 en tête coûte 24 heures de retard de plus, 61 au lieu de 37, et O9 finit 32 heures après son échéance » (le meilleur plan qui commence par O10, trouvé par énumération des 9! ordres restants). Un chef d'atelier qui déroge en connaissant le prix est un chef d'atelier qui fait confiance à l'outil. Celui qui ne peut pas déroger le contourne, et l'outil finit par ne plus servir.

La semaine 41, en résumé

Le lundi, le plan des dix ordres sort à 17 heures de retard : l'optimum prouvé, par milp comme par CP-SAT. Le chef d'atelier le lit, et ajoute deux heures pour chaque changement de montage : le plan coûte 68 heures, et le vrai optimum 37. Quand les durées réelles remplacent les temps standards, l'optimum du papier perd 30 heures en moyenne, et un plan un peu moins bon sur le papier en gagne 10. Le mardi, un onzième ordre arrive, et le plan de la veille, recalculé de zéro, déplace cinq ordres ; avec un poids de stabilité, il en déplace quatre pour le même retard, et à 3 heures il n'en déplace aucun, pour 9 heures de plus. Aucun de ces événements n'est un défaut de la méthode. Tous relèvent de l'ingénierie : mesurer, écouter, chiffrer ce qui compte, et garder la main ouverte.

Les erreurs d'un débutant

Exercices type

La méthode

1. Poser le problème : la décision, les contraintes, le coût réel, et ce qui a été volontairement laissé de côté.
2. Regarder si l'exact passe : un algorithme polynomial, un solveur en nombres entiers, un solveur par contraintes ; garder son optimum ou sa borne comme référence.
3. Si l'exact ne passe pas, choisir la méthode d'après le problème : une règle constructive et une descente d'abord, puis la métaheuristique que justifie ce qui reste.
4. Régler avec le même soin, sur d'autres graines que celles qui jugent, et écrire ce qui a été essayé.
5. Comparer : plusieurs graines, meilleure, médiane et pire, budget égal dans une unité dite (évaluations et secondes), écart à la référence, sans oublier la règle simple.
6. Tester la robustesse aux données : durées, échéances, ce qui varie, et préférer le plan qui tient.
7. Montrer tôt une solution à l'atelier, écouter ce qui la contredit, et ajouter les contraintes trouvées.
8. Rendre le plan explicable : ce que coûte chaque rang, et ce que coûte une dérogation.
9. Mesurer et pondérer la stabilité d'un jour à l'autre, avec un horizon gelé.
10. Fixer le temps de calcul d'après qui attend, et prévoir l'interruption.
11. Écrire le modèle et le test de non-régression, pour que quelqu'un d'autre puisse reprendre le code.

Synthèse

• Comparer des méthodes aléatoires demande plusieurs graines, meilleure, médiane et pire, un budget égal dans une unité dite, un écart à une référence, des réglages faits avec le même soin sur d'autres graines. Un protocole s'écrit une fois, en quelques dizaines de lignes.
• Un profil de performance donne la part des tirages à moins de $x$ % de la référence ; une courbe qualité-budget donne la médiane et la bande selon le budget. Aucun nombre seul ne les remplace.
• Sur la plaque P-600 (optimum prouvé 2 788,70 mm), à évaluations égales, le recuit a la meilleure médiane à 100 000 évaluations (2,23 %) et à un million (0,58 %), les fourmis avec 2-opt à 300 000 (1,19 %), sans qu'on puisse départager les premiers ; à temps égal, GRASP et les redémarrages montent (à 2 secondes, 0,41 % et 0,69 %) et le recuit, dont l'évaluation coûte 7 fois plus, recule. Sur trente postes, GRASP a la meilleure médiane à chaque budget, à égalité avec la règle constructive suivie d'une descente à 10 000 évaluations et avec le recuit à 500 000. Aucune méthode ne gagne partout, et un classement dépend de l'unité du budget, du problème, des réglages et du programme.
• Le solveur est le premier candidat, pas le dernier recours : HiGHS (milp) rend l'optimum prouvé de P-600 en quelques tours de coupes, CP-SAT celui de l'ordonnancement de dix ordres en un dixième de seconde, la bibliothèque de routage d'OR-Tools 0,06 % au-dessus de l'optimum de P-600 avec un dixième de seconde de recherche. Ils demandent un modèle, donnent une garantie, et se paient en dépendance.
• La métaheuristique écrite gagne quand le coût ne s'écrit pas en inéquations (une séquence par fenêtre glissante, une simulation), quand l'instance dépasse l'exact, quand il faut interrompre à tout instant, ou quand il faut un code que l'on lit en entier.
• Une décision vit dans un atelier. Les données sont biaisées : un plan optimal sur des temps standards perd trente heures dès que les durées bougent. Les contraintes non écrites se trouvent en montrant une solution. Un plan doit s'expliquer (ce que coûte chaque rang), rester stable (ordres déplacés, horizon gelé), tenir dans un temps de calcul que l'atelier accepte, et laisser l'humain verrouiller, interdire, déroger en connaissant le prix.
• Le code qui décide se maintient : un modèle écrit, un test de non-régression sur des instances à optimum connu, des graines fixées, le plus simple qui tienne.

Ce qu'on sait faire à la fin du parcours

Un ingénieur qui a suivi le parcours sait, devant une décision de production :

• la modéliser : distinguer la décision, les contraintes et le coût, choisir une représentation qui ne laisse rien passer d'impossible, décider entre contrainte dure et pénalité (chapitre 1) ;
• mesurer la difficulté : compter les solutions, voir l'explosion, et savoir qu'une machine plus rapide ne la contourne pas (chapitre 2) ;
• la borner et la résoudre quand elle est petite : relaxation, borne, écart garanti, milp, séparation et évaluation (chapitre 3) ;
• la construire par une règle gloutonne, en sachant ce que la règle sacrifie (chapitre 4) ;
• l'améliorer par recherche locale, écrire un voisinage, compter ses voisins, reconnaître un optimum local (chapitre 5) ;
• en sortir par le hasard (recuit), par la mémoire (tabou), par une population (génétique) ou par des traces (fourmis et GRASP), en réglant en mesurant ;
• comparer honnêtement : graines, trois nombres, budget égal, référence, réglage égal, et dire le cadre ;
• choisir entre une méthode écrite et un solveur, et écrire un même problème pour deux d'entre eux ;
• livrer : des données contestées, un plan expliqué, stable, dans le temps que l'atelier accepte, que l'atelier peut corriger.

Ce qu'il ne sait pas encore faire, et qu'il vaut mieux savoir : traiter des objectifs multiples (retards, énergie, stabilité) sans les fondre arbitrairement en un seul nombre ; décider sous incertitude autrement qu'en moyennant des scénarios ; apprendre les paramètres d'un problème à partir de l'historique ; maintenir une solution pendant des années sans que ses hypothèses vieillissent en silence. Ce sont des sujets d'un autre parcours, et ils commencent tous par la même première question : que se passe-t-il vraiment, dans l'atelier ?

Et ensuite

Pour prolonger ce qui touche à la modélisation exacte, le chapitre optimiser sous contraintes traite la programmation linéaire à deux variables, et le chapitre flots et couplages traite deux familles de problèmes (le débit maximal, l'affectation) que des algorithmes polynomiaux résolvent exactement. Pour comprendre ce que fait un solveur par contraintes de l'intérieur, le parcours Logique et solveurs SAT montre ce qui fait tourner un solveur moderne. Pour les tests d'une décision qui doit être maintenue, le chapitre tests et automatisation. Et pour reprendre la boucle depuis le début, avec une autre question de Valdrome, le chapitre 1 attend : décision, contraintes, coût, représentation.