D'autres modèles de calcul

Un modèle de calcul, ce qu'il accepte et ce qu'il rend

Un modèle de calcul est une façon d'écrire un problème pour qu'une famille de solveurs le résolve. Il fixe ce que peuvent être les variables, ce que peuvent dire les contraintes, la forme de l'objectif. En échange, le solveur promet une réponse d'une certaine nature : un optimum prouvé, une solution sans garantie, ou la preuve qu'il n'en existe aucune. Le parcours en a déjà employé deux, et en croise un troisième dans un autre parcours.

La programmation dynamique fait exception dans ce tableau : c'est une méthode plutôt qu'une langue, et aucun solveur général ne la prend en entrée. Elle y figure parce qu'elle est le troisième grand chemin vers un optimum exact, après la programmation linéaire et la séparation et évaluation.

La programmation par contraintes

Une question sans objectif

Le chef d'atelier de Valdrome reprend l'affectation des huit opérateurs du chapitre 4 sous un autre angle. Il ne demande pas le temps total le plus court : il veut que personne ne soit envoyé à un poste où il perd plus de 4 minutes sur son meilleur temps. Amel, dont le meilleur temps est de 11 minutes, au tournage comme à la peinture, peut donc tenir aussi le montage (15 minutes), mais pas le fraisage (18 minutes). La question est : une telle affectation existe-t-elle, et laquelle ?

Il n'y a pas d'objectif. Il y a huit décisions, une par opérateur, et deux règles. C'est le cadre de la programmation par contraintes.

Le même problème, écrit pour milp au chapitre 4, demandait 64 variables binaires, une par couple opérateur-poste, et 16 égalités pour dire « un poste par opérateur, un opérateur par poste ». Ici, huit variables et une contrainte, qui se lit comme l'énoncé. La règle des 4 minutes ne coûte même pas une contrainte : elle est dans les domaines.

Essayer à la main

La figure pose une version plus sévère de la question : 3 minutes au plus au-dessus de son meilleur temps. À gauche les opérateurs, à droite les postes, une arête quand le poste est dans le domaine de l'opérateur. Placer chacun sur un poste différent revient à choisir huit arêtes sans extrémité commune, un couplage au sens du chapitre flots et couplages.

Le couplage plafonne à 7, quel que soit l'ordre des placements, et la figure en donne la raison : Amel, Dimitri et Farid ne visent, à eux trois, que deux postes, le tournage et la peinture. Trois opérateurs pour deux postes : l'un des trois restera sans poste. C'est une preuve d'impossibilité qui tient en une ligne, la condition de Hall. Avec la candidature d'Amel au montage, l'une de celles qu'ajoute la règle des 4 minutes, un chemin augmentant apparaît et les huit trouvent leur place. L'affectation obtenue est la seule possible : Amel au montage, Bruno au perçage, Chloé à la soudure, Dimitri au tournage, Élise au contrôle, Farid à la peinture, Gaëlle à l'ébavurage, Hugo au fraisage. C'est l'affectation de 95 minutes, l'optimum du chapitre 4, trouvée sans avoir jamais parlé de temps total.

Propager : réduire les domaines

Un solveur par contraintes ne commence pas par essayer. Il commence par propager : chaque contrainte retire des domaines les valeurs qu'aucune solution ne peut employer. Pour « tous différents », la règle la plus simple tient en une phrase : un opérateur dont le domaine n'a plus qu'un poste le tient, et ce poste disparaît du domaine des autres. Un retrait peut laisser un autre opérateur avec un seul poste, qui se propage à son tour : la propagation continue tant qu'un domaine change.

À 4 minutes, trois opérateurs n'ont qu'un poste dès le départ : Dimitri (le tournage), Farid (la peinture) et Gaëlle (l'ébavurage). Le programme suivant est un solveur par contraintes complet, en une cinquantaine de lignes : la propagation, la recherche, et un plafond de temps dont une section plus bas dit l'usage. Il affiche, à chaque étape, ce que la propagation retire.

À 4 minutes, la propagation résout le problème à elle seule, sans une seule décision. Dimitri tient le tournage, qu'Amel perd ; Farid tient la peinture, qu'Amel, Bruno et Élise perdent ; Gaëlle tient l'ébavurage, que Chloé perd ; Amel n'a plus que le montage, qu'elle retire à Chloé et à Hugo ; et la cascade continue jusqu'à ce que chacun ait un seul poste. Sept étapes, onze postes retirés en tout, une affectation, et la preuve qu'elle est la seule : chaque valeur retirée l'a été parce qu'aucune solution ne pouvait l'employer.

À 3 minutes, la cascade tourne court : Dimitri et Farid prennent les deux seuls postes d'Amel, et son domaine se vide. C'est une impasse, et comme aucune décision n'a été prise, elle vaut preuve : aucune affectation ne respecte la règle. Le groupe Amel, Dimitri, Farid de la figure ressort du journal sans avoir été cherché.

La règle du poste unique s'écrit en une quinzaine de lignes. Le bloc suivant la fait écrire sur des domaines donnés comme des listes de noms, et l'éprouve sur les opérateurs de Valdrome.

Le troisième essai dit la limite de cette règle : trois opérateurs qui se partagent deux postes ne laissent aucune liste à un seul poste, et la propagation ne retire rien, alors que le problème est impossible. Pour le prouver, il faut chercher, ou propager plus fort.

Chercher : décider, propager, revenir en arrière

Quand la propagation ne retire plus rien et que des opérateurs ont encore le choix, le solveur décide : il prend l'opérateur qui a le moins de postes possibles, lui donne l'un d'eux, et propage de nouveau. Si une impasse survient, il revient en arrière : il oublie la décision et essaie le poste suivant. Dans le solveur plus haut, la décision se prend sur une copie des domaines, et revenir en arrière consiste à abandonner cette copie.

Le choix du plus contraint d'abord n'est pas un détail. Un opérateur qui n'a plus que deux postes possibles a une chance sur deux de recevoir le bon, et sa décision déclenche aussitôt des retraits ; commencer par Bruno, qui en a cinq, ferait explorer des branches qu'une propagation aurait coupées plus tôt. Remplacer (4, 3) par (5, 6) dans le solveur : la propagation ne suffit plus, et le journal montre les décisions, puis les retours à la décision précédente pour essayer le poste suivant. Il compte 7 affectations à 5 minutes et 12 à 6.

Optimiser : un plafond qui descend

La programmation par contraintes n'a pas besoin d'objectif, mais elle sait en traiter un, à sa manière : en le changeant en contrainte. Pour l'affectation au plus court, la contrainte est « le temps total ne dépasse pas un plafond ». Sa propagation reprend le calcul de borne du chapitre 4 : le temps total est au moins la somme des temps les plus courts que chaque domaine permet encore, et un poste est retiré s'il pousse cette somme au-dessus du plafond. Sans écart imposé, cette somme vaut au départ 88 minutes, la borne des minima de ligne, et elle monte à mesure que les domaines rétrécissent.

Le dernier appel du solveur, resoudre(ecart=99, plafond=999), permet tous les postes et part d'un plafond inatteignable, 999 minutes. À chaque solution trouvée, le plafond descend juste en dessous de son temps, et la recherche continue : elle ne cherche plus qu'une affectation strictement meilleure. Quand elle a tout parcouru, la dernière solution trouvée est prouvée optimale.

La première solution, 125 minutes, est celle de la règle gloutonne du chapitre 6, chacun dans l'ordre au poste libre le plus rapide : tant que le plafond ne gêne pas, la recherche commence comme elle. Suivent 122, 105, 99, 98 et 95 minutes, puis la preuve. Il a fallu 40 nœuds, c'est-à-dire 40 appels à chercher, dont 25 finissent en impasse ; la même recherche sans plafond, resoudre(ecart=99), en visite 69 281 pour énumérer les 40 320 affectations. Le plafond joue ici le rôle de l'élagage du chapitre 4.

Sur ce problème, la programmation linéaire voit pourtant plus loin : sa relaxation continue vaut 95 minutes d'emblée (chapitre 4), quand la propagation du plafond part de 88. Une somme se borne mieux par un programme linéaire ; une règle logique se dit mieux en contraintes. Les solveurs industriels mêlent les deux.

Ce qui la distingue de la programmation linéaire

• Des contraintes logiques, écrites telles quelles : tous différents, « ces deux ordres ne passent pas sur la machine en même temps », « si Amel est au montage, Hugo est au fraisage ». En programme linéaire, chacune se traduit en variables binaires et en inégalités, parfois au prix de centaines de variables : 424 pour les dix ordres du modèle indexé par le temps du chapitre 13.
• Des variables à domaine fini, que la propagation réduit, et aucune variable réelle.
• Pas d'objectif obligatoire : une question de faisabilité est un problème complet, et sa réponse peut être une preuve d'impossibilité. Un objectif se traite comme un plafond qui descend.
• Une preuve par recherche complète, et non par une borne de relaxation. La propagation borne mal les sommes ; la programmation linéaire dit mal les règles logiques.

Les solveurs industriels poussent chacun de ces traits plus loin. Leur propagation de « tous différents » s'appuie sur le couplage de la figure : elle retire tout poste qu'aucune affectation complète ne peut employer, et voit d'un coup le groupe d'Amel, Dimitri et Farid. CP-SAT, d'OR-Tools, ajoute l'apprentissage sur les impasses des solveurs SAT (le chapitre CDCL) et des relaxations linéaires pour les sommes. Le chapitre 13 écrit l'ordonnancement des dix ordres pour lui, avec des intervalles et une contrainte de non-recouvrement, et le compare au modèle linéaire du même problème.

La programmation non linéaire

La plus grande ventouse

Pendant le perçage de la plaque P-217, une ventouse tient la tôle par-dessous. Elle est ronde, et le foret ne doit jamais la toucher : son disque ne doit contenir aucun des douze trous. Où la poser, et de quel rayon au plus, pour qu'elle tienne le mieux ? Son centre reste dans le rectangle des trous, de 20 à 180 mm en largeur et de 15 à 105 mm en hauteur.

Les variables sont trois : le centre $(x \,;\, y)$ et le rayon $r$. L'objectif est $r$, à rendre le plus grand possible. Chaque trou $(a \,;\, b)$ donne une contrainte :

L'objectif est linéaire ; les douze contraintes ne le sont pas, parce qu'une distance est la racine d'une somme de carrés et non une somme de termes proportionnels aux variables. Dessinée, la contrainte d'un trou n'est pas un demi-plan mais l'extérieur d'un disque, et le domaine où le centre peut aller, pour un rayon donné, est un rectangle percé de douze disques : rien d'un polygone. C'est un programme non linéaire.

Plusieurs départs, plusieurs réponses

scipy.optimize.minimize résout ce genre de problème. Avec la méthode SLSQP, elle part d'un point, suit la pente de l'objectif en tenant compte des contraintes, et s'arrête quand plus aucun petit déplacement n'améliore. Elle minimise : pour agrandir $r$, elle reçoit $-r$. Le programme la lance depuis dix départs tirés au hasard (graine 5), puis, pour comparer, minimise depuis les mêmes départs une fonction d'une autre nature : la somme des distances du centre aux douze trous.

Dix départs, huit réponses différentes, de 18,75 à 45,25 mm. Chacune est un optimum local : un petit déplacement du centre, dans n'importe quelle direction, le rapproche d'un trou. Deux départs seulement, (25 ; 57) et (22 ; 35), trouvent 45,25 mm, avec le centre en (24,75 ; 60), à égale distance de T1, T4 et T9 ; les autres s'arrêtent chacun sur un autre optimum local, à égale distance de deux ou trois trous. Un balayage de tout le rectangle au vingtième de millimètre, calculé à part, ne trouve rien au-dessus de 45,25 mm : c'est l'optimum global, et le programme n'avait aucun moyen de le savoir. La somme des distances, elle, ramène les dix départs au même point, (102,0 ; 58,8).

Local, global, convexe

La somme des distances est convexe : d'où que parte la recherche, elle descend dans la même vallée. Le problème de la ventouse ne l'est pas : le segment qui joint deux bons centres peut traverser le disque d'un trou, et le relief du rayon possible a plusieurs bosses, une par zone libre entre les trous. Le programme linéaire du chapitre 3, lui, est toujours convexe, son domaine est un polygone et son objectif linéaire : c'est pourquoi un sommet dont aucun voisin ne fait mieux y est l'optimum, et c'est ce dont le simplexe profite.

Deux propriétés de la programmation linéaire se perdent donc en non linéaire. Plus de sommet garanti : le meilleur centre, en (24,75 ; 60), n'est le coin de rien, c'est un point où trois distances deviennent égales. Plus de garantie qu'un optimum local soit global, dès que le problème n'est pas convexe. La descente de gradient du parcours Intelligence artificielle fait la même expérience sur une courbe à deux vallées, dans le chapitre la descente de gradient : deux départs, deux minimums. La convexité d'une fonction d'une variable est étudiée dans le chapitre étude d'une fonction, les extremums de deux variables dans le chapitre fonctions de plusieurs variables.

Devant un problème non convexe, trois attitudes sont possibles. Lancer plusieurs départs et garder le meilleur, ce que fait le programme, sans jamais l'annoncer global. Employer un solveur global, qui découpe le domaine en morceaux et borne chacun, comme la séparation et évaluation du chapitre 4 : il prouve l'optimum de petits problèmes, au prix d'un temps qui explose avec le nombre de variables. Ou chercher par une métaheuristique, qui accepte de remonter pour franchir un col : c'est l'idée du recuit simulé, au chapitre 8.

La programmation dynamique, en rappel

Le parcours l'a déjà rencontrée deux fois : au chapitre 2, la méthode de Held et Karp donnait la meilleure tournée de la plaque P-217 ; au chapitre 4, un tableau meilleure[c] donnait la meilleure marge des commandes pour chaque capacité. Le chapitre gloutons et programmation dynamique du parcours Algorithmique en donne la technique. Ce qui compte ici, c'est ce qui la rend possible et ce qui la limite.

Elle repose sur deux conditions.

• Des sous-problèmes qui se recouvrent. Beaucoup de solutions différentes passent par le même état. Dans l'ordonnancement des dix ordres, tous les plans qui commencent par O3 et O7, dans un ordre ou dans l'autre, partagent la même suite possible : le même sous-problème, « placer au mieux les huit autres à partir de l'heure 4 ».
• Le principe d'optimalité. La meilleure solution du tout est faite des meilleures solutions de ses parties : la meilleure façon de finir ne dépend pas de la façon dont on a commencé, seulement de l'état atteint. Pour un ensemble $S$ d'ordres passés en premier, la machine est libre à l'heure $\sum_{j \in S} p_j$, quel que soit leur ordre ; le meilleur plan de $S$ s'obtient donc en choisissant l'ordre de $S$ qui passe en dernier, et en reprenant le meilleur plan des autres.

Le programme suivant applique cette idée aux dix ordres : un sous-problème par ensemble d'ordres, soit $2^{10} = 1\,024$.

Le programme retrouve les 17 heures de retard de l'optimum, avec l'un des ordres qui les atteignent, en résolvant 1 024 sous-problèmes au lieu d'essayer les 3 628 800 ordres de passage. C'est ce qui fait la force de la méthode : elle est exacte, et elle ne refait jamais deux fois le même calcul.

Sa limite est la mémoire : il faut garder un résultat par état. Pour le sac à dos, les états sont les capacités, de 0 à 100 heures, et leur nombre grandit avec la taille des nombres, pas avec le nombre de commandes : c'est pourquoi le chapitre 4 traite mille commandes en une fraction de seconde. Pour l'ordonnancement et pour la tournée, les états sont des ensembles, et leur nombre double à chaque ordre ou à chaque trou de plus.

Vingt ordres tiennent dans un million de résultats ; trente demandent 8,6 gigaoctets, et Held et Karp en demandent près de 258 pour trente trous, les « centaines de gigaoctets » du chapitre 2. À soixante trous, le nombre d'ensembles dépasse $10^{18}$ : aucune mémoire ne le contient. La programmation dynamique déplace la frontière de l'exact, elle ne la supprime pas.

Quel modèle pour quel problème

Le choix d'un modèle ne se fait pas au goût : il se lit sur le problème. Sept questions suffisent presque toujours.

Les problèmes concrets que la recherche opérationnelle résout se rangent alors d'eux-mêmes. Le tableau suivant les reprend, avec leur exemple chez Valdrome quand le parcours en a un.

La table conclut sans ambiguïté pour les grands problèmes difficiles du parcours, ceux dont la taille dépasse ce que l'exact sait traiter dans le temps disponible, ou dont le coût ne s'écrit dans aucun modèle : aucun solveur ne rendra l'optimum à temps, et il faut une méthode qui rende une bonne solution sans preuve, jugée contre une borne. Ce sont les métaheuristiques, qu'ouvre le chapitre suivant.

Les erreurs d'un débutant

Exercices type

La méthode

1. Écrire le problème en mots : les décisions, les règles, le coût, et repérer ce qui n'est pas une inégalité linéaire (une règle logique, un produit, une distance).
2. Choisir la nature des variables : réelles, entières, booléennes, ou une valeur parmi quelques-unes.
3. Passer la table de décision : linéarité, contraintes logiques, sous-problèmes qui se recouvrent, taille, temps disponible, besoin d'une preuve.
4. En programmation par contraintes, poser les domaines et les contraintes, propager, décider pour le plus contraint d'abord, revenir en arrière sur une impasse ; optimiser par un plafond qui descend.
5. En non linéaire, lancer plusieurs départs, garder le meilleur, lire le statut sans le croire, et n'annoncer un optimum global qu'avec un argument : convexité, balayage, borne.
6. En programmation dynamique, nommer l'état, vérifier le principe d'optimalité, et compter les états avant de lancer le calcul.
7. Si aucune méthode exacte ne passe dans la taille et le temps donnés, chercher une bonne solution par une métaheuristique, et la juger contre une borne.

Synthèse

• Un modèle de calcul fixe ce que les variables, les contraintes et l'objectif peuvent être, et le solveur rend en échange une réponse d'une nature donnée : optimum prouvé, solution sans garantie, preuve d'impossibilité.
• La programmation par contraintes pose des variables à domaine fini et des contraintes logiques, sans objectif obligatoire. Elle propage (retirer des domaines ce qu'aucune solution n'emploie), décide pour le plus contraint et revient en arrière sur une impasse. Sur les opérateurs de Valdrome, la propagation seule trouve l'unique affectation à 4 minutes au plus de chacun, celle de 95 minutes, et prouve qu'il n'y en a aucune à 3 minutes.
• Elle optimise en changeant l'objectif en plafond : 40 nœuds pour prouver les 95 minutes, contre 40 320 affectations à énumérer. SAT en est le cas à deux valeurs, traité dans son propre parcours, et CP-SAT (chapitre 13) la version industrielle.
• La programmation non linéaire accepte un objectif ou des contraintes non linéaires, au prix de deux garanties : l'optimum n'est plus à un sommet, et un optimum local n'est plus forcément global. Pour la ventouse de la plaque P-217, dix départs trouvent huit optimums locaux, de 18,75 à 45,25 mm. Seul un problème convexe assure que tout optimum local est global.
• La programmation dynamique demande des sous-problèmes qui se recouvrent et le principe d'optimalité ; elle retrouve les 17 heures des dix ordres en 1 024 sous-problèmes. Sa limite est la mémoire, qui double à chaque élément quand les états sont des ensembles.
• Le modèle se choisit sur le problème : nature des variables, linéarité, contraintes logiques, taille, temps, preuve. Pour les grands problèmes difficiles, aucun ne rend l'optimum à temps : ce sont les métaheuristiques qui prennent le relais.

Et ensuite

Quand un problème est trop grand pour un solveur, ou que son coût ne s'écrit dans aucun de ces modèles, il faut chercher autrement : le chapitre suivant construit une solution par une règle simple, et les chapitres qui le suivent l'améliorent. La règle gloutonne que le chapitre 6 applique aux opérateurs est celle que le solveur par contraintes a trouvée en premier, à 125 minutes. Pour les solveurs industriels, CP-SAT et la bibliothèque de routage d'OR-Tools, le chapitre 13 ; pour ce qui fait tourner un solveur de satisfiabilité, le parcours Logique et solveurs SAT.