Ce qui rend un problème difficile

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 exacte, ce qu'elle renvoie est un optimum. 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 ; la force brute le prouve, puisque toutes les autres sélections ont été vues.

La force brute, en vrai, sur la plaque

Reste la plaque : combien d'ordres de perçage faudrait-il essayer ? La figure suivante fait parier avant tout calcul : on y retient des trous de la plaque P-217, on écrit le nombre d'ordres qu'on attend, et la page les essaie réellement tous, 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 ne change rien à ce qui suit : un facteur constant ne pèse rien devant une croissance qui multiplie.

La figure calcule vite, avec un code que le navigateur optimise. Le même calcul écrit en Python est plus lent, et il dure assez pour être senti.

Les nombres d'ordres ne dépendent d'aucun appareil : 720, 5 040, 40 320 et 362 880. La colonne du rapport est celle qui compte. En principe, elle vaut 8 puis 9, le nombre de trous qu'on vient d'atteindre ; la mesure, bruitée, s'en écarte d'un ou deux selon l'appareil et l'instant, mais elle reste loin de 2, le rapport d'une croissance en $2^n$, et ne retombe pas vers 1. 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 : 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.

Les nombres seuls ne disent rien : il faut les traduire en temps, pour un ordinateur remarquable qui évaluerait un milliard de solutions par seconde. Avant de lancer le programme qui le fait, le calculer soi-même pour les ordres de perçage.

Le programme convertit en durées les trois croissances, pour des tailles de 10 à 60.

Les trois colonnes se ressemblent pour dix éléments, quelques millisecondes ou moins, et se séparent ensuite. 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.

La frontière entre « on peut tout essayer » et « on ne peut pas » est donc raide : entre douze et vingt trous, on passe d'une demi-seconde à des dizaines d'années.

Une machine plus rapide ne sauve rien

La réaction naturelle est d'acheter du matériel. Avec une heure de calcul, jusqu'où va-t-on, et de combien recule 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 reste dérisoire : de 41 à 51 commandes pour un facteur mille, à 61 pour un million.

La raison se lit en une ligne. Pour $2^n$, chaque élément ajouté double le travail : multiplier le budget par $F$ fait gagner autant d'éléments qu'il faut de doublements pour atteindre $F$, soit $\log_2 F$, dix pour $F = 1\,000$. Pour $n!$, chaque trou ajouté multiplie le travail par une quinzaine dans la zone étudiée ici, et un facteur mille n'en paie que deux ou trois. La vitesse de la machine déplace la frontière ; l'algorithme décide de sa raideur.

Une question à réponse oui ou non

La théorie de la difficulté ne parle ni de la tournée la plus courte ni de la marge la plus grande, mais de questions plus modestes, à réponse oui ou non : une telle réponse se compare d'un problème à l'autre bien plus facilement qu'une tournée à une marge.

La version décision n'est pas plus difficile que le problème d'optimisation. Qui connaît la tournée la plus courte, 633,23 mm, répond à toute question « au plus $k$ ? » par une comparaison : oui pour 640, non pour 630. Si la question oui ou non est difficile, trouver l'optimum l'est donc au moins autant.

L'autre sens est moins évident, et tout aussi vrai : un oracle, un programme qui reçoit un seuil et répond seulement oui ou non, suffit à retrouver l'optimum, à condition de l'interroger plusieurs fois. La marge optimale des commandes est un entier entre 0, puisque la sélection vide est toujours réalisable, et 28 500 €, la somme de toutes les marges. On demande « au moins 14 250 € ? », le milieu ; selon la réponse, on garde la moitié haute ou la moitié basse, et l'on recommence. C'est la dichotomie : chaque question coupe en deux l'intervalle où l'optimum peut encore se trouver.

Le bloc suivant écrit l'oracle par force brute, en essayant les 1 024 sélections : seul compte ici le nombre de questions qu'on lui pose. Il retrouve ensuite la sélection elle-même, toujours par oui ou par non, en interdisant les commandes une à une.

La première question, « au moins 14 250 € ? », reçoit un non ; la deuxième, « au moins 7 125 € ? », un oui. Après quinze questions, l'intervalle ne contient plus qu'une valeur, 13 300 €, alors qu'il en contenait 28 501 au départ : chaque question en écarte la moitié, et $2^{15} = 32\,768$ dépasse 28 501. Dix questions de plus donnent la sélection : une commande dont l'interdiction laisse 13 300 € atteignables n'est pas nécessaire, et reste interdite ; C4, C6 et C8 sont les seules sans lesquelles l'optimum tombe. Vingt-cinq questions en tout, quand la force brute examine 1 024 sélections.

Pour la tournée, dont la longueur est un nombre réel, la dichotomie s'arrête à une précision choisie. Entre 0 et 1 079,76 mm, la longueur de l'ordre d'écriture, il faut 17 questions pour connaître l'optimum au centième de millimètre, et chaque décimale de plus en coûte trois ou quatre. Le nombre de questions suit le nombre de chiffres des données, et non leur valeur.

Optimiser et décider ont donc la même difficulté : si l'une des deux versions se résolvait en temps polynomial, l'autre aussi. C'est pourquoi la théorie peut ne parler que de questions à réponse oui ou non sans rien perdre de ce qui compte pour l'atelier.

Vérifier n'est pas trouver

Une réponse oui a une preuve toute trouvée : la solution elle-même. Qui affirme qu'une tournée d'au plus 640 mm existe n'a qu'à la montrer, et le doute se lève en un calcul.

Le vérificateur contrôle que chaque trou figure une fois, additionne treize distances et compare. Le premier certificat est accepté : 633,23 mm pour un seuil de 640, la réponse est oui, et la preuve tient en une ligne. Le deuxième est refusé pour un seuil de 630, et ce refus ne prouve pas que la réponse est non, seulement que ce certificat-là ne convient pas : la réponse est bien non, mais c'est une méthode exacte qui le dit. Le troisième oublie T1 : il mesurerait 632,18 mm et passerait sous les deux seuils, et seul le contrôle des trous l'arrête, comme le test de validité du chapitre 1.

Cette asymétrie est le cœur de la notion : trouver une tournée d'au plus 640 mm demande de chercher parmi 239 500 800 tournées distinctes, vérifier celle qu'on propose demande treize distances. Une réponse non n'a pas en général de certificat aussi court : pour convaincre qu'aucune tournée ne descend à 630 mm, il faut un argument sur toutes, une borne inférieure par exemple (chapitre 4). Le chapitre complexité nomme cette question, celle de la classe co-NP : elle est ouverte.

Ce que veut dire « difficile »

Pour l'ordre de perçage (le voyageur de commerce) ou la découpe de barres (le bin packing), personne ne connaît de méthode qui résolve toutes les instances, avec certitude d'atteindre l'optimum, en un temps qui croisse comme une puissance de leur taille ($n^2$, $n^3$). La théorie range ces problèmes avec quatre mots, définis sur les problèmes de décision, que le chapitre complexité du parcours Satisfiabilité pose en détail sur l'exemple de SAT ; ils s'appliquent ici aux problèmes de Valdrome.

Quatre problèmes sur cinq sont du côté difficile, et ce classement ne se devine pas : il se démontre. La section suivante le fait pour la tournée.

En une idée : un problème NP-complet est au moins aussi dur que tous les problèmes de NP, une vaste famille dont beaucoup n'ont pas non plus de méthode rapide connue, et une méthode rapide pour un seul les résoudrait tous. Savoir si elle existe est la question « P = NP ? », ouverte ; la plupart des spécialistes pensent que non, sans l'avoir démontré.

Deux 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 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 : elle n'interdit pas les méthodes exactes qui profitent de la structure d'un problème.

Ramener un problème à un autre

Démontrer qu'un problème est NP-difficile ne demande pas de le comparer à tous les problèmes de NP : il suffit de lui ramener un seul problème qu'on sait déjà NP-difficile, puisque tout ce qui se ramène au premier se ramène alors au second.

Le sens de lecture. Une réduction $A \leq_p B$ dit que $B$ est au moins aussi difficile que $A$, et elle se lit de deux façons.
Si $B$ se résout vite, $A$ aussi : traduire, puis résoudre. C'est l'usage pratique, celui d'un solveur.
Si $A$ est difficile, $B$ l'est aussi : sinon, on résoudrait $A$ en passant par $B$. C'est l'usage théorique.
Pour prouver qu'un problème est difficile, il faut donc traduire un problème difficile vers lui, et jamais l'inverse.

Du cycle hamiltonien à la tournée

Un cycle hamiltonien d'un graphe passe une fois et une seule par chaque sommet, puis revient au départ, en n'empruntant que des arêtes du graphe. Décider si un graphe en possède un est NP-complet : le chapitre familles remarquables du parcours Graphes le rappelle, et l'oppose au cycle eulérien, qui se décide en comptant des degrés. La traduction vers la version décision de la tournée tient en trois règles, pour un graphe de $n$ sommets :

1. les $n$ sommets deviennent les $n$ points de la tournée, qui part de l'un d'eux, passe par tous les autres et revient ;
2. deux sommets reliés par une arête sont à distance 1, deux sommets non reliés à distance 2 ;
3. le seuil vaut $k = n$.

La réponse est la même des deux côtés, et cela se vérifie dans les deux sens.

• Si le graphe a un cycle hamiltonien, la tournée qui le suit emprunte $n$ paires reliées par une arête : elle mesure $n$, et la tournée répond oui.
• Si une tournée mesure au plus $n$, elle emprunte $n$ paires de points, chacune à distance 1 au moins : elles sont donc toutes à distance 1, ce sont des arêtes, et la tournée suit un cycle hamiltonien du graphe.

La traduction remplit un tableau de $n \times n$ distances : elle est polynomiale. La tournée est donc au moins aussi difficile que le cycle hamiltonien, et elle est dans NP, puisqu'une tournée proposée se vérifie en un passage : sa version décision est NP-complète. Le bloc suivant applique la traduction à deux graphes de cinq sommets, la maison (un carré surmonté d'un toit) et le papillon (deux triangles qui se touchent par un sommet), puis à cent graphes de sept sommets tirés au hasard, chaque paire étant reliée avec une probabilité de 0,4 (graine 7). Pour chacun, il répond aux deux questions par force brute et compare.

La maison a un cycle hamiltonien, le tour du toit et des murs, et sa traduction a une tournée de longueur 5, le seuil : oui des deux côtés. Le papillon n'en a pas, puisque passer d'un triangle à l'autre et revenir obligerait à traverser deux fois le sommet commun ; sa traduction a une tournée la plus courte de 6, au-dessus du seuil : non des deux côtés. Sur les cent graphes tirés, vingt sont hamiltoniens, et les cent réponses coïncident : les tournées des vingt mesurent 7, celles des autres de 8 à 11. Un essai ne prouve rien, la preuve est le raisonnement en deux sens ; il attrape en revanche une traduction fausse.

Reste à lire ce que la réduction prouve. La version décision de la tournée est NP-complète pour des distances quelconques, ici 1 et 2. La plaque P-217 est un cas particulier, aux distances euclidiennes entre des points du plan, et la réduction, à elle seule, ne dit rien de ce cas : un cas particulier peut être facile. Celui-là ne l'est pas, mais il a fallu une autre réduction, plus longue, pour l'établir. Le même procédé, parti du problème du partage (des nombres entiers peuvent-ils se répartir en deux groupes de même somme ?), établit que la version décision du sac à dos est NP-complète, et celle de la découpe aussi.

Ce qui rend un problème difficile

Voici réunies les formes de la difficulté que rencontre le parcours.

L'explosion combinatoire condamne la force brute, pas toute méthode : elle accompagne la difficulté sans la prouver.

La difficulté au pire cas ne dit rien de l'instance du lundi, qui n'est peut-être pas de celles où toute méthode connue explose. Le chapitre complexité le montre sur SAT : des formules de plusieurs millions de variables se résolvent en quelques secondes, quand le principe des tiroirs à quatorze casiers, 210 variables, résiste.

Le discret. Au chapitre 3, les lots de poulies et de bielles ont un optimum continu de 1 680 €, en (1,5 ; 3,75), et un optimum entier de 1 560 €, dans un autre coin du polygone. La programmation linéaire en variables réelles se résout en temps polynomial, on le sait depuis 1979 ; en nombres entiers, elle est NP-difficile, puisque le partage s'y ramène en une seule contrainte.

La structure de l'instance. Au chapitre 4, le même arbre de séparation et d'évaluation visite, sur cinq instances de trente commandes tirées de la même famille, de 41 à 120 283 nœuds. Une structure particulière peut aussi rendre un problème facile : l'affectation des opérateurs, qui a l'air d'un problème de permutations comme la tournée, a une relaxation continue exacte et se résout en temps polynomial.

Les optimums locaux. Sur la plaque P-217, la tournée T1, T7, T9, T11, T10, T8, T3, T12, T2, T6, T5, T4 mesure 647,35 mm, 2,2 % au-dessus de l'optimum, et aucun échange de deux trous, aucun déplacement d'un trou, aucun retournement d'un morceau de l'ordre ne la raccourcit. Le chapitre 7 la rencontre, et les chapitres 8 à 11 apprennent à sortir de tels pièges.

Ce qui n'est pas une preuve de difficulté

• « Je n'ai pas trouvé d'algorithme rapide. » L'échec d'une recherche, même longue, dit quelque chose de la recherche, pas du problème.
• Un espace de solutions immense. Les dix ordres de fabrication ont $10! = 3\,628\,800$ ordres de passage. Pour la somme des instants de fin, un tri suffit : la durée croissante donne 179 heures, le minimum. Pour la somme des retards, sur les mêmes ordres, le problème est NP-difficile.
• Une ressemblance. Passer une fois par chaque arête d'un graphe se décide en comptant des degrés ; passer une fois par chaque sommet est NP-complet. 2-SAT se résout en temps linéaire, 3-SAT est NP-complet.
• Un programme lent, ou un solveur qui peine. Il mesure une méthode sur une instance, pas un problème : la force brute est lente sur le sac à dos, la programmation dynamique ne l'est pas.
• La difficulté du cas général, prêtée à un cas particulier. La tournée dont tous les trous sont sur une même demi-droite issue de l'origine se résout sans rien chercher.

La seule preuve est une réduction polynomiale, depuis un problème qu'on sait NP-difficile. Et savoir qu'un problème est difficile ne dit pas qu'il faut renoncer à le traiter, mais à quoi renoncer : à la garantie d'un optimum, en temps raisonnable, sur toutes les instances.

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.

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. Le code suivant en essaie la plus rudimentaire : 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.

Après vingt mille ordres tirés au hasard (graine 217), le meilleur est à 7,3 % de l'optimum : loin d'être absurde, pour 0,004 % de l'espace essayé. Mais la progression est lente. Passer de mille à vingt mille essais a gagné vingt points d'écart (de 28,1 % à 7,3 %) ; poussé à cent mille tirages avec la même graine (un calcul trop long pour la page, fait à part), le meilleur n'est qu'à 6,6 %, 674,87 mm : cinq fois plus de travail pour moins d'un point. Le plus proche voisin, une règle de construction présentée au chapitre 6, donne 692,06 mm, à 9,3 %, en douze petits choix, plus de 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 4.

Plus fin que la force brute : Held et Karp

Exact ne veut pas dire « essayer les $n!$ ordres ». Pour le voyageur de commerce, la programmation dynamique de Held et Karp est exacte et bien plus fine que la force brute. 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.

Vingt trous passent de soixante-dix-sept ans à moins d'une demi-seconde. Mais à trente trous, Held et Karp demandent seize minutes, et surtout une mémoire de plusieurs centaines de gigaoctets, un résultat par sous-ensemble de trous ; à soixante, 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 en une heure pour la force brute à une trentaine), elle ne la fait pas disparaître.

Ce n'est qu'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 4 en montre le principe sur cette plaque P-217, puis prouve ainsi l'optimum d'une plaque de soixante trous, que le chapitre recherche locale prend pour référence. Elle n'offre aucune garantie de temps : 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

Mettre en pratique