L'explosion combinatoire

Tant que ça tient : tout essayer

Elle a deux qualités que les méthodes des chapitres suivants n'auront pas. Elle est simple : une boucle et la fonction de coût du chapitre précédent suffisent. Et elle est exacte : ce qu'elle renvoie est un optimum, pas une bonne solution. Sur les commandes de Valdrome, les dix cases à cocher se traduisent en un entier écrit en binaire, et parcourir les entiers de 0 à 1 023 parcourt les sélections.

Les 1 024 sélections sont examinées en quelques millisecondes, 406 sont réalisables, et la meilleure est C4, C6 et C8 : 98 heures, 13 300 €. Aucune règle de bon sens ne pouvait l'affirmer, et la force brute le prouve, puisque toutes les autres sélections ont été vues. C'est la référence contre laquelle le chapitre précédent jugeait déjà les solutions plausibles.

La force brute, en vrai, sur la plaque

Reste la plaque. Une tournée est un ordre de perçage des trous, et la question est de savoir combien d'ordres il faudrait essayer. Avant tout calcul, la figure suivante permet de parier : on y retient des trous de la plaque P-217, on écrit le nombre d'ordres qu'on attend, et la page essaie réellement tous les ordres, un par un, en chronométrant. L'estimation n'est jugée qu'après.

Ce que la figure a compté a une formule. Une tournée est une permutation des trous, et le nombre de permutations de $n$ objets se compte en choisissant le premier trou parmi $n$, puis le deuxième parmi $n-1$, jusqu'au dernier :

Ce nombre s'appelle la factorielle de $n$. Il grandit à une vitesse qu'on sous-estime toujours.

Un ordre et son inverse mesurent la même longueur, puisque l'outil part de l'origine et y revient : il n'y a que $n!/2$ tournées distinctes, soit 239 500 800 pour douze trous. Diviser par deux est un facteur constant : il ne change rien à ce qui suit, et la partie sur la machine plus rapide dira pourquoi.

La figure travaille dans le navigateur, avec un code que le navigateur optimise, donc vite. Le même calcul écrit en Python est plus lent, et c'est ce qui le rend instructif : il dure assez pour être senti.

Les nombres d'ordres, eux, ne dépendent d'aucun appareil : 720, 5 040, 40 320 et 362 880. La colonne du rapport est celle qui compte (la première ligne n'en a pas, et celle des sept trous, trop courte pour être fiable, en donne un voisin de 7) : elle est voisine de 8 puis de 9, c'est-à-dire du nombre de trous qu'on vient d'atteindre. C'est la factorielle qui se lit : chaque trou ajouté multiplie le travail par le nombre de trous, il ne l'augmente pas d'une quantité fixe. La dernière ligne extrapole, et l'extrapolation dit à peu près ce que la figure disait : dix trous, c'est dix fois plus long que neuf ; douze trous, plus de mille fois plus long ($12!/9! = 1\,320$).

Trois façons de grandir

Trois croissances se rencontrent en optimisation, et on peut les distinguer sans mathématiques avancées.

Les nombres seuls ne disent rien. Il faut les traduire en temps. Le code suivant suppose un ordinateur remarquable, qui évalue un milliard de solutions par seconde, et convertit chaque nombre en durée.

Lire le tableau demande de la lenteur. Les trois colonnes se ressemblent pour dix trous : quelques millisecondes ou moins. Elles se séparent après. Un algorithme en $n^3$ traite soixante trous en moins d'une milliseconde. Pour les $2^n$ sélections de commandes, dix commandes prennent une microseconde, trente une seconde, quarante dix-huit minutes, cinquante treize jours, et soixante trente-six ans. Pour les $n!$ ordres de perçage, douze trous prennent une demi-seconde, quinze prennent vingt-deux minutes, vingt prennent soixante-dix-sept ans, et soixante ne prennent pas un temps : $60!$ vaut environ $8{,}3 \times 10^{81}$, soit $2{,}6 \times 10^{65}$ années, quelque $10^{55}$ fois l'âge de l'Univers. À titre de comparaison, on estime à $10^{80}$ le nombre d'atomes de l'Univers observable.

Une machine plus rapide ne sauve rien

La réaction naturelle est d'acheter du matériel. La question se pose précisément : avec une heure de calcul, jusqu'où va-t-on, et de combien recule-t-on la frontière si la machine va dix, mille, un million de fois plus vite ?

Pour les ordres de perçage, la machine actuelle va jusqu'à quinze trous en une heure. Dix fois plus vite : seize. Mille fois plus vite : dix-sept, soit deux trous de plus. Un million de fois plus vite : vingt. Pour les sélections de commandes, le gain est plus visible mais reste dérisoire : de 41 à 51 commandes pour un facteur mille, de 41 à 61 pour un million.

La raison est mathématique et se lit en une ligne : multiplier le budget par un facteur $F$ fait gagner de l'ordre de $\log_2 F$ éléments pour $2^n$ (dix pour $F = 1\,000$), et à peu près $\log_n F$ pour $n!$, soit deux à trois trous dans la zone étudiée ici. Une croissance qui multiplie le travail à chaque ajout ne se laisse pas rattraper par un gain constant. La vitesse de la machine déplace la frontière ; l'algorithme décide de sa raideur.

Ce que veut dire « difficile »

L'ordre de perçage (le voyageur de commerce), la découpe de barres (le bin packing) : on a beau chercher, personne ne connaît de méthode qui résolve toutes les instances de ces problèmes, avec certitude d'atteindre l'optimum, en un temps qui croisse comme une puissance de leur taille ($n^2$, $n^3$). On dit de ces problèmes qu'ils sont NP-difficiles.

Le mot a un sens précis, que le parcours de Satisfiabilité pose en détail et qu'on n'a pas à refaire ici : le chapitre complexité définit la classe NP, la réduction d'un problème à un autre, et ce que signifie qu'un problème soit NP-difficile. En une idée : un problème NP-difficile est au moins aussi dur que tous les problèmes d'une vaste famille, dont on ne sait pas non plus s'ils ont des méthodes rapides. Une méthode rapide pour un seul les résoudrait tous, et la plupart des spécialistes pensent qu'une telle méthode n'existe pas. Le résultat n'est pas démontré, c'est une conviction très solide, forgée par des décennies de tentatives.

Quatre précisions évitent des contresens.

• Difficile ne veut pas dire insoluble. Douze trous se résolvent. Ce qui est en cause, c'est la façon dont le travail croît quand on ajoute des éléments, pas la possibilité de résoudre un cas donné.
• Difficile ne veut pas dire difficile à évaluer. Évaluer une tournée est facile, on l'a fait au chapitre précédent : la longueur est une somme. C'est la recherche de la meilleure qui ne se laisse pas faire, et cette asymétrie, vérifier facilement et chercher difficilement, est le cœur de la notion.
• Difficile ne veut pas dire sans méthode exacte du tout. Le sac à dos des commandes est lui aussi NP-difficile, et pourtant sa programmation dynamique, du chapitre gloutons et programmation dynamique, le résout vite tant que la capacité reste un petit nombre entier. La difficulté est celle du pire cas, quand la taille des données grandit : elle n'interdit pas les méthodes exactes qui profitent de la structure d'un problème.
• Difficile n'interdit pas les bonnes solutions. Rien n'empêche de trouver une tournée à quelques pour cent de l'optimum en une fraction de seconde. C'est de la garantie de l'optimum qu'on se prive.

Cette dernière précision annonce la suite.

Ce qu'on fait alors

Devant un problème qu'on ne peut pas résoudre exactement en temps raisonnable, il reste deux attitudes.

La première est de ne plus chercher l'optimum : se contenter d'une bonne solution, trouvée vite. C'est le sens du mot qui gouverne tout ce parcours.

Une heuristique se juge sur deux tableaux à la fois : la qualité de la solution (l'écart) et le temps qu'il a fallu pour la trouver. Aucune des deux mesures ne suffit seule. Le code suivant en donne un premier exemple, le plus rudimentaire qui soit : tirer des ordres au hasard, et garder le meilleur vu. Sur la plaque P-217, l'optimum est connu, 633,23 mm (il a été calculé une fois pour toutes par une méthode exacte, évoquée plus bas), ce qui permet de mesurer l'écart.

Le résultat est parlant dans les deux sens. Après vingt mille ordres tirés au hasard, le meilleur est à 7,3 % de l'optimum : loin d'être absurde. Mais ces vingt mille essais ne couvrent que 0,004 % de l'espace, et la progression est lente : passer de mille à vingt mille essais a gagné plus de vingt points d'écart (de 28,1 % à 7,3 %) et coûté vingt fois plus. Poussé à cent mille tirages avec la même graine (un calcul trop long pour être refait ici, fait à part), le meilleur n'est qu'à 6,6 %, 674,87 mm : cinq fois plus de travail pour moins d'un point de gain. Une règle qui construit intelligemment une tournée trouve presque aussi bien en un seul passage : le plus proche voisin, présenté au chapitre 4, donne 692,06 mm, soit 9,3 % d'écart contre 6,6 % pour les cent mille tirages, mais après douze petits choix, soit environ dix mille fois moins de calculs. Tout l'art des chapitres suivants est de gagner sur les deux tableaux.

La seconde attitude n'abandonne pas l'exactitude, elle la rend moins coûteuse. Une méthode exacte intelligente n'essaie pas tout : elle élimine des solutions sans les évaluer, parce qu'une borne prouve qu'elles ne peuvent pas être les meilleures. C'est l'objet du chapitre 3, qui traite des bornes et de ce qu'on peut obtenir d'exact avec un solveur.

Le parcours se déroule donc ainsi :

Plus fin que la force brute : Held et Karp

Exact ne veut pas dire « essayer les $n!$ ordres ». Il existe, pour le voyageur de commerce, une méthode exacte bien plus fine que la force brute : la programmation dynamique de Held et Karp. Elle repose sur l'idée que le chapitre gloutons et programmation dynamique développe : ne pas refaire plusieurs fois le même calcul. Pour une tournée, le meilleur chemin qui part de l'origine, visite un ensemble donné de trous et finit en un trou donné ne dépend pas de l'ordre dans lequel l'ensemble a été visité. On le calcule une fois, on le retient, on s'en sert.

Le travail devient de l'ordre de $n^2 \times 2^n$ opérations, au lieu de $n!$. C'est elle qui a fourni le 633,23 mm de la plaque.

Le gain est immense : vingt trous passent de soixante-dix-sept ans à moins d'une demi-seconde. Mais le tableau est têtu. À trente trous, Held et Karp demandent seize minutes de calcul, et plus encore une mémoire qui se compte en centaines de gigaoctets, parce qu'il faut retenir un résultat par sous-ensemble de trous. À soixante trous, il reste environ cent trente mille ans. La méthode est exacte, elle est aussi exponentielle : elle repousse la frontière d'une quinzaine de trous (de quinze trous en une heure pour la force brute à une trentaine pour Held et Karp), elle ne la fait pas disparaître. C'est cohérent avec ce que dit la notion de difficulté.

Held et Karp ne sont pas pour autant le dernier mot de l'exact : c'est une méthode exacte, parmi d'autres. La programmation linéaire en nombres entiers, avec des coupes qui interdisent les tournées en plusieurs boucles (le piège du chapitre 1), va beaucoup plus loin en pratique : le chapitre 3 en montre le principe sur cette plaque P-217, et le chapitre recherche locale s'en sert pour prouver l'optimum d'une plaque de soixante trous. Elle n'offre aucune garantie de temps, et ne vient pas à bout de n'importe quelle instance : la limite de l'exact bouge avec la méthode et avec l'instance, elle ne disparaît pas.

Les erreurs d'un débutant

Exercices type

La méthode

1. Compter les solutions avant de programmer : $2^n$, $n!$, ou autre.
2. Convertir en temps : diviser par le nombre d'évaluations par seconde, puis traduire en minutes, jours, années.
3. Si le temps est raisonnable, faire la force brute : simple et exacte, et elle sert de référence.
4. Sinon, mesurer la croissance sur trois petites tailles consécutives, chercher le rapport entre deux temps, et identifier la loi avant d'extrapoler.
5. Ne pas espérer que le matériel règle le problème : chiffrer ce que gagnerait un facteur dix, cent, mille.
6. Quand la taille l'interdit, passer aux heuristiques, et annoncer chaque résultat avec son écart à la meilleure solution connue ou à une borne.

Synthèse

• La force brute énumère toutes les solutions, évalue chacune, garde la meilleure réalisable : simple, exacte, et applicable tant que l'espace est petit.
• Les dix commandes ont $2^{10} = 1\,024$ sélections, faciles à tout essayer ; les douze trous ont $12! = 479\,001\,600$ ordres, déjà lourds.
• Chaque trou ajouté multiplie le travail par le nombre de trous : la croissance est factorielle, et le rapport entre deux temps consécutifs en est la signature.
• À un milliard d'essais par seconde : quinze trous demandent 22 minutes, vingt trous 77 ans, soixante trous bien plus que l'âge de l'Univers.
• Une machine mille fois plus rapide ne fait gagner que deux à trois trous sur $n!$, dix éléments sur $2^n$ : l'algorithme décide de la raideur de la frontière.
• Un problème NP-difficile est au moins aussi dur que toute une famille de problèmes ; on ne connaît pas de méthode qui les résolve tous exactement en temps polynomial, et l'on pense qu'il n'en existe pas. Le détail est dans le chapitre complexité.
• Une heuristique cherche une bonne solution vite, sans garantie d'optimum ; on la juge par son écart à la meilleure solution connue et par son temps.
• Held et Karp, par programmation dynamique, sont exacts en $n^2 \times 2^n$ : un progrès énorme, qui reste exponentiel. C'est une méthode exacte parmi d'autres : la programmation en nombres entiers avec coupes (chapitre 3) va plus loin en pratique, sans garantie de temps.