Bornes et méthodes exactes

Juger sans connaître la réponse

Retour à la sélection du lundi : C4, C1 et C9, 97 heures, 13 200 €. Le chapitre 1 l'a évaluée ; elle est réalisable, et rien n'indique qu'elle soit la meilleure. Pour dire si elle est bonne, il faudrait connaître l'optimum, et on ne le connaît pas : c'est justement ce qu'on cherche.

Le premier réflexe est de trouver un nombre que l'optimum ne peut pas dépasser, sans le calculer. Un premier nombre s'écrit sans réfléchir : la somme de toutes les marges.

C'est une vraie borne : aucune sélection ne peut rapporter plus que la somme de toutes les marges. Mais elle affirme que la sélection est à au plus 54 % de l'optimum, ce qui ne rassure personne. Une borne trop lâche est vraie et inutile. Tout l'art est d'en trouver une serrée, qui coûte peu à calculer.

Pourquoi l'écart garanti majore-t-il l'écart réel ? Pour une maximisation, $v \le \text{opt} \le B$. L'écart réel est $(\text{opt} - v)/\text{opt} = 1 - v/\text{opt}$, et $1 - v/x$ croît avec $x$ : remplacer l'optimum par la borne, plus grande, ne peut qu'augmenter la fraction. Pour une minimisation, $L \le \text{opt} \le v$, l'écart réel est $(v - \text{opt})/\text{opt} = v/\text{opt} - 1$, et $v/x - 1$ décroît avec $x$ : remplacer l'optimum par la borne, plus petite, ne peut là aussi qu'augmenter la fraction. C'est cette phrase, « à au plus 3 % », que le directeur peut entendre : elle ne suppose pas qu'on ait résolu le problème.

Une borne ne se calcule pas avec l'optimum, elle se prouve. Ce qu'on demande à une preuve, c'est d'être correcte et de tenir en peu de calcul. Il y a deux sources de bornes, et ce chapitre les emploie toutes les deux.

• Des raisonnements de bon sens : le nombre de barres ne peut pas être inférieur à la longueur totale divisée par celle d'une barre.
• Une relaxation : on desserre une contrainte du problème jusqu'à ce qu'il devienne facile à résoudre. Le problème desserré a au moins autant de solutions, donc un optimum au moins aussi bon. C'est l'objet de la section suivante.

Toute solution réalisable est aussi une borne, de l'autre côté : dans une maximisation, elle minore l'optimum. La marge de 13 200 € dit que l'optimum vaut au moins 13 200 €, et la relaxation dira qu'il vaut au plus un certain nombre. Les heuristiques du reste du parcours fournissent le côté « au moins », les relaxations le côté « au plus ».

Relaxer : autoriser une fraction de commande

Retour aux commandes. La contrainte qui rend le problème difficile est le « tout ou rien » : une commande se lance en entier ou pas. Il suffit de la desserrer : on s'autorise à ne lancer qu'une fraction d'une commande, la moitié, un tiers, avec une marge et des heures proportionnelles. C'est la relaxation continue du sac à dos.

Le problème desserré est facile. Chaque heure de machine doit aller à la commande qui la rentabilise le mieux, c'est-à-dire celle dont la marge par heure est la plus grande. On classe donc les commandes par rendement décroissant, on les remplit dans cet ordre tant qu'elles tiennent, et la première qui ne tient plus est prise en partie, juste de quoi combler les heures restantes.

Pourquoi le résultat est-il une borne ? Parce qu'une sélection en tout ou rien est un cas particulier d'une sélection fractionnaire : lancer une commande en entier, c'est en lancer la fraction 1, en ne pas lancer, la fraction 0. Toute sélection réalisable du vrai problème est donc réalisable dans le problème desserré. Ce dernier a plus de solutions, son meilleur optimum est au moins aussi grand, et il majore celui du problème d'origine. La preuve tient en deux lignes et ne suppose rien de l'optimum.

La figure suivante fait faire le chemin dans l'autre sens. On y charge une sélection de commandes dans le conteneur, en glissant les caisses, en les cliquant ou au clavier, et on demande ensuite la comparaison à la borne. La figure ne dit jamais si la sélection est la meilleure : la borne est une preuve, pas une référence.

Voici le même calcul, à la main puis par un solveur de programmation linéaire, écrit avec PuLP, la bibliothèque de modélisation du chapitre 3. Les variables y sont continues, chacune entre 0 et 1 : c'est la relaxation. Le premier bloc qui importe pulp met quelques secondes à démarrer : le solveur se charge une fois, puis tout va vite.

Le solveur et le calcul à la main s'accordent : la borne de la relaxation est de 13 704,4 €. La relaxation lance C8, C1 et C9 en entier (83 heures) puis 17 des 45 heures de C4, soit 38 % de la commande, pour 2 304,4 € de marge. Aucune sélection réelle ne peut rapporter davantage, donc la sélection du lundi, à 13 200 €, est à au plus 3,7 % de l'optimum. Ce nombre annonce ce qu'il est impossible de dépasser, non ce qu'il est possible d'atteindre : lancer 38 % d'une commande n'est pas une décision d'atelier, et prendre C4 en entier mènerait à 128 heures.

Deux bornes en une ligne : la découpe et l'affectation

Deux autres problèmes de Valdrome ont leur borne, et elle tient en une ligne de calcul.

La découpe des barres. Vingt pièces sont à tirer de barres de 6 000 mm. Une barre ne contient au plus que 6 000 mm de pièces, donc il en faut au moins autant que la longueur totale divisée par 6 000, arrondie au-dessus : on ne commande pas 4,92 barres. C'est une borne inférieure.

L'affectation des opérateurs. Huit opérateurs, huit postes, un temps par couple. Chaque opérateur mettra au minimum le temps de sa meilleure case, donc le temps total est au moins la somme des minima de chaque ligne. C'est aussi une borne inférieure : elle relâche la contrainte « un opérateur par poste », en laissant deux opérateurs prendre le même.

La découpe donne une borne de 5 barres. Une règle simple, qui range les pièces de la plus longue à la plus courte, en utilise 6 : elle est à au plus 20 % de l'optimum, et il reste à savoir si la barre de trop est évitable. La borne dit qu'on n'ira pas sous 5 ; elle ne dit pas qu'on y arrive. La marge est faible : les 29 500 mm de pièces occupent presque tout l'espace de 5 barres (30 000 mm), il ne reste que 500 mm de jeu.

L'affectation donne une borne de 88 minutes, et le programme montre pourquoi aucune affectation ne l'atteint : chacun prend son meilleur poste, et Dimitri et Amel visent tous deux le tournage, Chloé et Hugo le fraisage, Élise et Farid la peinture, tandis que la soudure, le montage et le contrôle n'ont pas de preneur. Cette affectation-là n'existe pas, puisqu'elle met deux opérateurs au même poste. C'est le cas typique d'une borne qui n'est pas atteinte : elle est correcte, elle est utile, et elle est plus basse que l'optimum. Ce qui trahirait une erreur, c'est l'inverse : une solution réalisable en dessous d'une borne inférieure, ou au-dessus d'une borne supérieure. Ce test, écrit dans un programme, attrape les erreurs de calcul d'un coût sans connaître l'optimum.

Résoudre les petits cas : un solveur en nombres entiers

Un programme linéaire dont certaines variables sont contraintes d'être entières s'appelle, en français, un programme linéaire en nombres entiers (PLNE) ; en anglais, mixed integer linear programming (MILP). PuLP l'écrit comme un programme linéaire : une variable se déclare entière à sa création, cat="Integer", ou cat="Binary" pour une variable qui vaut 0 ou 1. Le même modèle se résout en nombres entiers par prob.solve(), et sa relaxation continue par prob.solve(HiGHS_SCIPY(mip=False)). Dans la page, PuLP confie le calcul à HiGHS, le solveur de scipy ; sur un poste, il appelle par défaut un autre programme de résolution, CBC, qui rend les mêmes valeurs optimales, mais peut rendre une autre solution quand plusieurs sont à égalité. Les trois problèmes de Valdrome tiennent chacun en quelques lignes.

Les commandes. Une variable par commande, égale à 1 si elle est lancée et 0 sinon. Une contrainte : la somme des heures des commandes lancées ne dépasse pas la capacité. Le programme résout d'abord la relaxation, pour comparer, puis le problème en nombres entiers, en redonnant chaque fois son solveur à solve : sans argument, le second appel reprendrait le premier, mip=False compris.

Le solveur retient C4, C6 et C8 : 98 heures, marge de 13 300 €. C'est l'optimum, prouvé par le solveur, et le seul : aucune autre sélection n'atteint 13 300 €, si bien que CBC rendrait les trois mêmes commandes. La sélection du lundi (13 200 €) était donc à 100 € de l'optimum, bien mieux que ce que l'écart garanti de 3,7 % laissait craindre, et la relaxation à 13 704,4 € en était à 404 € au-dessus.

L'affectation. Une variable $x_{ip}$ par couple opérateur-poste, égale à 1 quand l'opérateur $i$ tient le poste $p$. Chaque opérateur tient un poste, chaque poste a un opérateur : 16 égalités.

Le solveur rend 95 minutes, avec poste_de = [6, 2, 4, 0, 7, 5, 3, 1], la seule affectation à 95 minutes parmi les 40 320 possibles. La borne des minima de ligne, 88, était 7 minutes sous l'optimum : elle n'était pas fausse, elle n'était pas atteinte, parce qu'elle ne pouvait pas savoir que trois postes étaient sans preneur.

Une remarque sur la relaxation de l'affectation : si l'on donne au solveur les mêmes 64 variables sans exiger qu'elles soient entières, par prob.solve(HiGHS_SCIPY(mip=False)), il rend 95 exactement, la même valeur. C'est un fait propre à cette structure, que le problème de transport du chapitre 3 montre aussi (les sommets du domaine réalisable, en dimension 64, sont tous entiers), et ce n'est vrai ni du sac à dos, dont la relaxation était à 13 704, ni de la découpe. La relaxation est parfois exacte, souvent serrée, jamais garantie de l'être. L'affectation est d'ailleurs le seul des cinq problèmes de Valdrome à se résoudre en temps polynomial : la méthode hongroise (scipy.optimize.linear_sum_assignment) rend 95 minutes instantanément.

La découpe. Une variable $x_{ib}$ égale à 1 quand la pièce $i$ est dans la barre $b$, une variable $y_b$ égale à 1 quand la barre $b$ sert. Chaque pièce est dans une barre, et la longueur des pièces d'une barre ne dépasse pas 6 000 mm si la barre sert. On minimise le nombre de barres qui servent. On offre au modèle 6 barres, ce que la règle simple a déjà réussi.

Le solveur trouve 5 barres, la borne. Une solution qui atteint une borne inférieure est optimale, et la preuve est complète : personne ne fera mieux que 5, et le modèle en a trouvé une avec 5. La barre de trop de la règle simple était donc évitable.

Ce que dit le statut, et ce qu'il ne dit pas. Sur un problème plus gros, une limite de temps, prob.solve(HiGHS_SCIPY(timeLimit=60)), peut arrêter le solveur avec la meilleure solution trouvée, sans avoir prouvé l'optimum. Le statut dit alors encore "Optimal", comme avec CBC, et c'est prob.sol_status qui distingue : 1 pour un optimum prouvé, 2 pour une solution trouvée sans preuve. Par défaut, HiGHS s'arrête aussi dès que l'écart entre sa meilleure solution et sa borne passe sous 0,01 % ; cela ne change rien aux petits cas de ce chapitre, et pour une preuve exacte on lui demande un écart nul, HiGHS_SCIPY(gapRel=0), comme le fait la boucle de la tournée plus loin. Le chapitre 13 y revient.

Séparer et évaluer

Quand le solveur prouve un optimum, il ne teste pas toutes les solutions. Il fait ce que fait l'arbre suivant, appelé séparation et évaluation (en anglais branch and bound).

Sur le sac à dos, la variable qu'on sépare est celle que la relaxation a coupée en fraction : c'est elle qui empêche la solution relâchée d'être une vraie sélection. Au sommet de l'arbre, la relaxation coupe C4 en fraction. On sépare donc « C4 est lancée » d'un côté, « C4 n'est pas lancée » de l'autre, et chaque côté a sa propre relaxation, calculée avec cette décision fixée. Quand une relaxation ne coupe plus aucune commande, elle est une vraie sélection, une solution entière, et l'on peut mettre à jour la meilleure connue.

Le programme suivant déroule l'arbre en profondeur, la branche « lancée » d'abord. Il n'affiche que les nœuds qui apprennent quelque chose : les deux premiers niveaux, les améliorations de la meilleure solution, et les premiers élagages.

Le sommet de l'arbre a pour borne 13 704,4 et sépare sur C4 : la branche « C4 lancée » vaut au plus 13 684,2, la branche « C4 non lancée » au plus 13 640,9. Aucune ne peut être élaguée tout de suite, elles peuvent l'une comme l'autre contenir de bonnes sélections. L'arbre descend, trouve d'abord une sélection à 12 600 €, puis 12 700, 13 200 et enfin 13 300. Dès qu'il détient 13 200, tout nœud dont la relaxation est à 13 200 ou moins est coupé, et il y en a beaucoup : la borne a servi de détecteur de branches sans avenir.

À la fin, 93 nœuds ont été visités au lieu des 2 047 de l'arbre complet, et la dernière meilleure valeur, 13 300, est prouvée : toute branche non explorée avait une borne d'au plus 13 300. C'est la même preuve que le solveur.

Ce résumé ne dit pas tout, et ce qu'il ne dit pas compte. Le nombre de nœuds dépend de l'ordre dans lequel on visite les branches et de la meilleure solution déjà connue au départ : un meilleur point de départ élague davantage. Un solveur industriel ajoute d'autres bornes, d'autres règles de choix de la variable, et des heuristiques pour trouver de bonnes solutions tôt. L'idée reste celle-ci : des bornes sûres pour ne pas tout explorer.

Et la tournée ?

Le voyageur de commerce de Valdrome, la tournée de la perceuse, se met lui aussi en nombres entiers, et c'est là que le solveur montre à quoi servent les coupes. Soit la plaque P-217 : le départ et les douze trous font treize points.

Le modèle. Une variable par arête, c'est-à-dire par paire de points : elle vaut 1 quand l'outil passe directement de l'un à l'autre, 0 sinon. Treize points font $13 \times 12 / 2 = 78$ variables. On minimise la somme des longueurs des arêtes retenues, et chaque point doit avoir exactement deux arêtes retenues, celle par où l'outil arrive et celle par où il repart : treize égalités.

Ce que le modèle laisse passer. « Chaque point a deux arêtes » décrit aussi bien une seule grande boucle, la tournée, que plusieurs boucles séparées qui couvrent ensemble les treize points. C'est le piège du chapitre 1 sous une autre forme : la représentation « pour chaque trou, le trou suivant » passait son test de validité avec deux boucles de trois trous. Le modèle a donc plus de solutions que le problème : c'est une relaxation, et sa valeur est une borne inférieure de la longueur de toute tournée.

La coupe. Pour une boucle formée d'un ensemble $S$ de points, qui ne contient pas tous les points, on ajoute la contrainte suivante, où $|S|$ est le nombre de points de $S$ : parmi les arêtes dont les deux bouts sont dans $S$, au plus $|S| - 1$ sont retenues. Une boucle qui se ferme sur $S$ en retiendrait exactement $|S|$ : elle est interdite. Une vraie tournée, qui entre dans $S$ et en ressort, n'a jamais $|S|$ arêtes à l'intérieur de $S$ : elle n'est pas touchée. Une contrainte qui écarte des solutions fausses sans écarter une seule solution vraie s'appelle une coupe ; celle-ci est une coupe de sous-tour.

La boucle. On résout, on cherche les boucles de la solution, on ajoute une coupe par boucle, et l'on recommence, jusqu'à ce que la solution soit d'un seul tenant. Une solution d'un seul tenant est une tournée, et comme sa longueur est le minimum du modèle relâché, aucune tournée ne peut faire mieux : c'est l'optimum.

La première passe rend 633,23 mm, mais en deux boucles : l'une autour du départ (départ, T1, T4, T7, T9), l'autre avec les huit autres trous. Ce n'est pas une tournée, et pourtant ce nombre est déjà une borne inférieure de toute tournée. À la passe suivante, après une coupe par boucle, le solveur rend une seule boucle, de la même longueur : elle atteint la borne, elle est optimale, et c'est le 633,23 mm que la programmation dynamique de Held et Karp avait donné au chapitre 2. Un hasard de la plaque fait ici que les deux solutions ont la même longueur : T7, T9, T10 et T11 forment un carré de 30 mm de côté, et l'on peut en relier les côtés de deux façons de même longueur, l'une qui ferme une boucle à part, l'autre qui garde une seule tournée.

Le plus souvent, la solution à plusieurs boucles est plus courte que la meilleure tournée, et il faut plusieurs passes. Sur les soixante trous de la plaque P-600, la longueur rendue par le solveur monte de 2 607 mm (onze boucles) à 2 788,70 mm (une seule) en quatre passes : c'est l'optimum que le chapitre recherche locale prend pour référence. Held et Karp n'est donc qu'une méthode exacte parmi d'autres, et celle-ci va beaucoup plus loin en pratique. Elle n'offre pourtant aucune garantie de temps, ce que la section suivante mesure.

Quand l'exact ne suit plus

Le sac à dos de dix commandes tient dans un arbre de 93 nœuds. Que devient-il avec vingt, trente, quarante commandes ? Le programme suivant engendre des instances par une formule reproductible et compte les nœuds du même arbre, jusqu'à trente commandes. Les poids sont pris entre 20 et 80 et la marge égale le poids plus 100 ; la capacité est la moitié du poids total. C'est une famille dite fortement corrélée, réputée difficile pour la séparation et l'évaluation : la marge d'une sélection vaut son poids total plus 100 par commande retenue, si bien que les sélections qui remplissent la capacité avec le même nombre de commandes rapportent presque la même chose, et que la relaxation élague mal. Les rendements ne sont pourtant pas égaux (de 2,25 à 6,0 sur l'instance de deux cents commandes plus bas) : c'est la ressemblance des sélections pleines qui gêne, pas celle des commandes.

Le nombre de nœuds est très inégal d'une instance à l'autre, à taille égale : à trente commandes, de 41 à 120 283 nœuds, et l'on ne sait pas d'avance de quel côté on tombera. Il explose ensuite. Deux mesures faites à part, trop longues pour ce bloc, le montrent : à quarante commandes, les mêmes cinq graines donnent de 508 à 247 742 nœuds, alors que l'arbre complet en compterait plus de deux mille milliards ; et sur quarante instances par taille, avec une limite de deux millions de nœuds, aucune instance de trente commandes ne la dépasse, deux instances de quarante la dépassent, sept de cinquante et treize de soixante.

Cela dit ce que vaut cet arbre, qui n'emploie que la relaxation la plus simple et une exploration en profondeur. Cela ne dit pas que le sac à dos est hors de portée de l'exact. Voici les mêmes instances, avec deux cents et mille commandes en plus, résolues de deux autres façons exactes, puis jugées : l'écart d'une règle gloutonne à l'optimum, et sa garantie donnée par la borne.

Les deux méthodes trouvent le même optimum, en moins d'une seconde, jusqu'à mille commandes. La programmation dynamique du chapitre gloutons et programmation dynamique profite de ce que la capacité reste un petit nombre entier (5 067 heures pour deux cents commandes) : son travail est de l'ordre du nombre de commandes multiplié par la capacité, et non de $2^n$. Le sac à dos est NP-difficile, mais seulement au sens « faible » : sa difficulté tient à la taille de ses nombres. HiGHS, le solveur que PuLP appelle dans la page, ajoute à la séparation et évaluation des bornes plus fines, des coupes et des heuristiques que l'arbre du bloc précédent n'a pas. Le premier appel du bloc, sur une seule commande, ne sert qu'à charger le solveur, pour que son chargement ne compte pas dans la première mesure.

Une frontière existe pourtant, et elle dépend de la méthode et de l'instance plus que de la taille seule. Dans cette famille, la capacité grandit avec le nombre de commandes, et le travail de la programmation dynamique avec le produit des deux : il est multiplié par trois à quatre quand le nombre de commandes double, et à vingt mille commandes ce bloc demanderait une quinzaine de secondes dans la page. Pour la tournée, la boucle de la section précédente prouve l'optimum des soixante trous de P-600 en moins d'une seconde, puis met de l'ordre de dix secondes pour cent trous comme pour cent cinquante, et de quarante secondes pour deux cents (les 100, 150 et 200 premiers trous de la formule qui engendre P-600, décrite au chapitre recherche locale ; hors de la page, sur un poste, avec PuLP et HiGHS et une formulation sans raffinement : des logiciels spécialisés vont beaucoup plus loin). Deux leçons : le temps d'une méthode exacte se prévoit mal, il dépend de la structure de l'instance autant que de sa taille ; et une meilleure méthode déplace la frontière de plusieurs tailles, sans la faire disparaître.

Les bornes, elles, ne dépendent d'aucun solveur, et elles restent utiles quand on ne cherche pas l'optimum. La dernière colonne du tableau ne coûte qu'un tri, quelle que soit la taille, et elle certifie qu'une règle gloutonne est à moins de 3,5 % de l'optimum pour quarante commandes, à moins de 0,8 % pour deux cents, à moins de 0,2 % pour mille, sans avoir besoin de connaître l'optimum. Ici on le connaît (3 466, 17 667 et 89 024) : l'écart réel est de 1,2 %, 0,27 % et 0,06 %, ce qui rappelle qu'une borne garantit moins que ce que la solution vaut. C'est le contrat que la suite du parcours reprend : quand on ne cherche pas l'optimum, ou qu'on ne peut pas le prouver, on cherche de bonnes solutions par des heuristiques, et une borne bon marché dit jusqu'où elles pourraient progresser.

Ce que l'exact apporte au parcours. Trois choses, et pas une de plus. Un optimum de référence sur les cas qu'il sait résoudre, pour mesurer honnêtement une heuristique. Des bornes sur tous les autres, pour dire jusqu'où une solution peut encore être améliorée. Une preuve quand une solution atteint la borne. Quand la méthode exacte ne suit plus, on cherche et on borne, et les chapitres 6 à 11 s'occupent de chercher.

Les erreurs de débutant

Mettre en pratique