Bornes et programmation linéaire

Juger sans connaître la réponse

Reprenons 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.

Relaxer : autoriser une fraction de commande

Revenons aux commandes. La contrainte qui rend le problème difficile est le « tout ou rien » : une commande se lance en entier ou pas. Desserrons-la : 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. Le premier bloc qui importe scipy met quelques secondes à démarrer : la bibliothèque 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.

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. Notons la faible marge : 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. Les sections suivantes disent de combien.

La programmation linéaire : une intuition à deux variables

La relaxation du sac à dos est un programme linéaire : maximiser une somme de termes proportionnels aux variables, sous des contraintes qui sont des inégalités entre une somme proportionnelle aux variables et une constante. On n'en retient ici que l'intuition, qu'un exemple à deux variables suffit à donner. Le détail de la méthode graphique est traité dans le chapitre optimiser sous contraintes du parcours Mathématiques appliquées ; on ne le refait pas.

Valdrome fabrique aussi deux références en lots, sans rapport avec les dix commandes de la semaine : des poulies, qui rapportent 500 € le lot, et des bielles, 400 € le lot. Un lot de poulies demande 6 heures de tournage et 1 heure de fraisage ; un lot de bielles, 4 heures de tournage et 2 heures de fraisage. Le tournage dispose de 24 heures, le fraisage de 6. Les variables $x$ et $y$ sont les nombres de lots.

Chaque contrainte est un demi-plan, et leur intersection est un polygone, le domaine réalisable. La marge $500x + 400y$ est constante sur une droite, et cette droite glisse parallèlement à elle-même quand la marge change. La figure dessine le polygone et cette droite. Les lots entiers réalisables sont les points pleins de la grille. Avant toute explication, chercher à la main le lot le plus rentable : glisser la droite vers les grandes marges, choisir un point plein, puis demander à la figure si c'est le meilleur.

L'optimum est atteint au dernier point du polygone que la droite touche en glissant vers les marges croissantes, et il y a toujours un sommet parmi les points optimaux : jamais seulement l'intérieur. Il suffit donc d'examiner les sommets, quatre ici : (0 ; 0), (4 ; 0), (3 ; 1,5) et (0 ; 3), de marges 0, 2 000, 2 100 et 1 200. Le programme suivant confie le calcul à un solveur, d'abord sans exiger l'entier, puis en l'exigeant.

Le meilleur sommet est à $x = 3$ lots de poulies et $y = 1{,}5$ lot de bielles, pour 2 100 €. Un lot et demi n'est pas une décision d'atelier. Si les lots sont indivisibles, l'optimum tombe à 2 000 €, avec 4 lots de poulies et aucun de bielles. Et le point entier obtenu en arrondissant le sommet continu vers le bas, 3 lots de poulies et 1 de bielles, ne rapporte que 1 900 € : arrondir n'est pas résoudre, l'optimum entier est ici dans un autre coin du polygone.

Deux leçons pour la suite. La première : le continu donne une borne (2 100 €), et le problème en nombres entiers est plus dur que son relâché continu. On sait résoudre le second pour des milliers de variables ; le premier reste difficile en général. La seconde : le solveur milp traite directement le cas où l'on impose l'entier, c'est ce que la section suivante emploie.

Résoudre les petits cas : milp

scipy.optimize.milp résout un programme linéaire dont certaines variables sont contraintes d'être entières : en français, la programmation linéaire en nombres entiers (PLNE) ; en anglais, mixed integer linear programming (MILP). On lui donne le vecteur de coût (le solveur minimise : pour maximiser, on passe l'opposé), les contraintes sous forme de matrice, et un tableau integrality qui dit, variable par variable, si elle est entière (1) ou continue (0). 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 : integrality à 1 et bornes de 0 à 1. Une contrainte : la somme des heures des commandes lancées ne dépasse pas la capacité. Le programme résout aussi la version relâchée, avec integrality à 0, pour comparer.

Le solveur retient C4, C6 et C8 : 98 heures, marge de 13 300 €. C'est l'optimum, prouvé par le solveur. 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. Ce que la borne annonçait comme « au plus 3,7 % » était en réalité de moins de 1 %.

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 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. Le solveur donne l'optimum, et à 95 on n'a plus besoin de se demander si la solution est bonne : on sait qu'aucune affectation ne fait mieux.

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, il rend 95 exactement, la même valeur. C'est un fait propre à cette structure, à admettre ici (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. Elle reste dans le fil rouge parce que sa représentation est un bon terrain d'essai pour les méthodes qui suivent, pas parce qu'elle serait difficile.

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.

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. Prenons 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 : 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, en quelques secondes au plus : 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. milp 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.

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 : à cinq mille commandes, la programmation dynamique de ce bloc demande plus de dix secondes sur l'ordinateur qui a servi aux mesures. Pour la tournée, la boucle de la section précédente prouve l'optimum des soixante trous de P-600 en quelques secondes, puis met de l'ordre d'une demi-minute pour cent trous, d'une minute pour cent cinquante et de deux minutes et demie pour deux cents (les 100, 150 et 200 premiers trous de la formule qui engendre P-600, décrite au chapitre recherche locale ; sur cet ordinateur, avec 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.

Les erreurs de débutant

Exercices type

La méthode

1. Écrire ce qu'on maximise ou minimise, et dire quel côté une borne doit garder : supérieure pour une marge, inférieure pour un coût.
2. Chercher une borne par le bon sens : une somme, un rapport arrondi au-dessus, un minimum de chaque ligne.
3. Chercher une borne par relaxation : desserrer la contrainte qui rend le problème dur (le tout ou rien, un opérateur par poste) et résoudre le problème desserré.
4. Vérifier le sens de la borne avec une solution connue : elle doit se trouver du bon côté.
5. Calculer l'écart garanti de chaque solution trouvée, et le présenter comme « au plus », jamais comme « exactement ».
6. Sur un cas que l'exact sait traiter, résoudre exactement avec milp, lire le statut, et garder l'optimum comme référence. Pour une tournée, ajouter les coupes de sous-tour au fur et à mesure, jusqu'à une seule boucle.
7. Quand l'exact ne suit plus (temps trop long, nombre de nœuds qui explose), ne plus chercher l'optimum : chercher de bonnes solutions et les juger par la borne.

Synthèse

• Une borne supérieure pour une maximisation, une borne inférieure pour une minimisation : un nombre que l'optimum ne peut franchir, prouvé sans le connaître.
• L'écart garanti $(B - v)/B$ ou $(v - L)/L$ majore l'écart réel à l'optimum : c'est le « à au plus x % » qu'on sait annoncer.
• Une borne trop lâche est vraie et inutile ; une borne serrée coûte souvent un tri ou une division.
• La relaxation continue autorise des fractions. Elle a plus de solutions que le problème d'origine, donc un meilleur optimum, donc une borne. Sur le sac à dos, on remplit par rendement décroissant et l'on coupe la dernière commande : 13 704,4 € pour Valdrome.
• Bornes simples de Valdrome : 5 barres pour la découpe (29 500 divisé par 6 000, arrondi au-dessus), 88 minutes pour l'affectation (somme des minima de ligne), non atteinte par aucune affectation.
• En programmation linéaire à deux variables, l'optimum est à un sommet du polygone réalisable ; arrondir cet optimum ne donne pas l'optimum entier.
• scipy.optimize.milp résout les petits cas en nombres entiers : 13 300 € pour les commandes, 95 minutes pour l'affectation, 5 barres pour la découpe. Il minimise, et son statut se lit.
• La séparation et évaluation coupe les solutions en deux par une variable, évalue chaque moitié par sa relaxation, élague les moitiés dont la borne ne bat pas la meilleure solution connue. C'est ainsi que s'obtient une preuve sans tout énumérer.
• La tournée se met en nombres entiers (une variable par arête, deux arêtes en chaque point). Ce modèle laisse passer plusieurs boucles, le piège du chapitre 1 : on ajoute des coupes de sous-tour et l'on relance, jusqu'à une seule boucle. C'est ainsi que se prouvent les 633,23 mm de la plaque P-217, et l'optimum des soixante trous de P-600 au chapitre 5.
• Le temps d'une méthode exacte est imprévisible et dépend de la structure du problème autant que de sa taille : l'arbre naïf du sac à dos explose sur des instances corrélées, alors que la programmation dynamique et milp les résolvent en une fraction de seconde. Les bornes, elles, continuent de coûter peu et de certifier les solutions des heuristiques.

Et ensuite

Le chapitre suivant reprend le problème par l'autre bout : des règles simples de construction, le plus proche voisin sur la plaque, le rangement par longueur décroissante sur les barres, dont on connaît désormais l'écart garanti. On y jugera chaque règle contre l'optimum quand il est connu, et contre la borne sinon. Sur la question de savoir pourquoi l'exact ne suit pas, le chapitre explosion combinatoire donne les ordres de grandeur, et la notion de difficulté est posée dans complexité.