Modéliser une décision

Une décision de la semaine

Décider quand les choix sont nombreux et les ressources limitées est le métier de la recherche opérationnelle (operations research en anglais). Quand les choix sont des objets qu'on peut énumérer (des sélections, des ordres, des affectations), on parle d'optimisation combinatoire : c'est le cadre de ce parcours.

Valdrome Mécanique est une entreprise d'usinage et d'assemblage d'une centaine de personnes : un atelier de machines-outils, une perceuse à commande numérique, un poste de découpe de barres et de tôles, des postes d'assemblage. Ses problèmes reviendront tout au long de ce parcours, toujours avec les mêmes données, pour que deux méthodes puissent se comparer sur le même cas.

Le premier est celui du lundi. Dix commandes attendent. Chacune consomme des heures de machine et rapporte une marge, et il y a cent heures de machine disponibles cette semaine.

La commande n'est pas divisible : on lance C4 en entier ou pas du tout. La question est simple à poser. Quelles commandes lancer, pour que la marge soit la plus grande possible sans dépasser les cent heures ? C'est un problème de sac à dos (knapsack en anglais) : des objets qui ont chacun un poids et une valeur, un sac dont la capacité ne se dépasse pas.

Avant de modéliser quoi que ce soit, essayer à la main. La figure suivante dessine la semaine de machine comme un conteneur gradué en heures, et chaque commande comme une caisse dont la hauteur est proportionnelle à ses heures. Le but est de charger la sélection la plus rentable qui tienne dans les cent heures. La figure ne dit pas où se trouve la meilleure : elle ne répond qu'à une proposition, une fois celle-ci soumise.

Pour répondre « c'est l'optimum », la figure a en coulisse énuméré toutes les sélections possibles, 1 024, ce qu'un atelier ne peut pas toujours faire. Elle propose ensuite de rejouer deux règles de bon sens, celles qu'on essaie d'instinct : les commandes les plus rentables d'abord, ou celles qui rapportent le plus par heure de machine. Une règle aussi naturelle atteint-elle l'optimum ? La figure répond, règle par règle, en la rejouant.

Le vocabulaire

Le même petit nombre de mots sert à décrire n'importe quelle décision d'atelier. Ils ont un sens précis, et bien des erreurs de modélisation viennent de les employer l'un pour l'autre.

Le tableau met ces mots en face des deux décisions du chapitre.

Une remarque sur le sens de l'optimisation. Maximiser une marge et minimiser une longueur sont le même problème vu de deux côtés : maximiser une grandeur revient à minimiser son opposé. Dans la suite, on parlera de coût sans se soucier du sens, et le texte dira chaque fois si l'on cherche le plus petit ou le plus grand.

Optimum et bonne solution ne sont pas synonymes. Il n'existe pas toujours d'algorithme qui trouve l'optimum en un temps raisonnable, et presque tout le parcours cherche une bonne solution, dont il mesure la distance à ce qu'on peut espérer : la dire « optimale » sans preuve est une erreur.

Évaluer une solution

Avant de chercher une bonne solution, il faut savoir en juger une. C'est la première chose qu'un programme d'optimisation doit savoir faire, et c'est étonnamment facile : évaluer une solution ne demande que de l'additionner.

Trois solutions, trois lignes de résultat, et déjà une surprise : la troisième rapporte le plus, et elle est irréalisable. Une fonction de coût seule, qui ne regarderait que la marge, la préférerait aux deux autres. Un coût sans contrainte recommande l'impossible. Toute la partie « pénalité » plus bas tourne autour de cette phrase.

La première ligne du résultat, « les plus rentables », est justement la règle de bon sens de la figure : on prend la commande la plus rentable, puis la suivante qui tient encore, jusqu'à ne plus pouvoir. Elle donne ici 13 200 euros pour 97 heures. Est-ce le mieux possible ? Une règle de bon sens donne des solutions plausibles, proches les unes des autres, et sans tout essayer rien ne dit s'il en existe une meilleure. Cette incertitude est le sujet du parcours : une décision se juge par rapport à ce qu'on aurait pu faire, et pour cela il faut d'abord la mettre en forme.

Évaluer n'est pas chercher pour autant. Évaluer une solution prend un temps proportionnel à sa taille ; trouver la meilleure parmi des millions est une autre affaire. La fonction de coût n'est pas la solution du problème : elle n'en est que la règle du jeu.

Deux fonctions, pas une. Un problème d'optimisation se modélise avec deux outils distincts : une fonction de coût, qui note une solution, et un test de réalisabilité, qui dit si elle a le droit d'exister. Les mélanger dans une seule formule est possible (c'est la pénalité) mais c'est un choix à faire en connaissance de cause, pas un raccourci.

Représenter une solution

Pour manipuler une solution dans un programme, il faut la ranger dans une structure : une liste, un tableau de zéros et de uns, un dictionnaire. Ce choix s'appelle la représentation, et c'est de loin la décision de modélisation qui pèse le plus sur la suite. Un voisinage, un croisement, une mutation, des notions que les chapitres suivants poseront, se définissent sur la représentation et pas sur la solution abstraite.

Pour les commandes

Trois façons de ranger une sélection de commandes, et le tableau dit ce que chacune laisse passer.

La liste de numéros paraît naturelle, et elle est la pire : elle a les trois défauts du tableau. Les zéros et les uns n'ont aucun de ces défauts. Ils ont pourtant une limite : ils ne garantissent pas la capacité. Une liste de dix zéros et uns est toujours une sélection, mais pas toujours une sélection réalisable, et la contrainte des cent heures reste à tester séparément.

La troisième représentation est plus subtile : elle règle ce problème en faisant de la contrainte une partie de la lecture. Un programme qui décode l'ordre en lançant chaque commande tant qu'elle tient ne produit jamais une sélection irréalisable. Le prix est un décodage à faire et beaucoup d'ordres qui ne changent rien. C'est un compromis, et le parcours en rencontrera d'autres.

Il se chiffre. Les 3 628 800 ordres possibles des dix commandes (10 × 9 × … × 1) n'écrivent que 79 des 1 024 sélections : celles où plus aucune commande ne tient. Une sélection d'une ou deux commandes n'en fait jamais partie, puisque, quel que soit l'ordre, au moins trois commandes se lancent. L'optimum en fait partie, et ce n'est pas un hasard : tant que chaque marge est positive, une sélection à laquelle on peut ajouter une commande est battue par la sélection agrandie. La représentation oublie donc des sélections, mais aucune qui puisse être la meilleure.

Pour la plaque

Même exercice pour l'ordre de perçage.

La dernière est la plus trompeuse, parce qu'elle a l'air de respecter la règle : chaque trou a un suivant et un seul, chaque trou est le suivant d'un seul autre. Et pourtant.

Le test le plus naturel répond « valide », et la représentation décrit deux boucles distinctes de trois trous : l'outil ne peut pas suivre deux boucles à la fois. Un test de validité incomplet est pire qu'aucun test, parce qu'il donne une confiance qu'il ne mérite pas. Un algorithme qui cherche la tournée la plus courte trouverait, dans un espace qui contient des doubles boucles, des « tournées » sensiblement plus courtes que les vraies, et les annoncerait comme des tournées. Le remède est de choisir la permutation, qui ne laisse rien passer, plutôt que de compliquer le test. Devant toute représentation qui vient à l'esprit, la question est la même : quels objets cette structure peut-elle contenir qui ne sont pas des solutions ? La réponse est rarement « aucun ».

Le coût : la trajectoire de la perceuse

Vient la deuxième décision. La perceuse à commande numérique perce, sur une plaque de bride, douze trous dont les positions sont fixées par le plan. L'outil part de l'origine de la plaque, perce les douze trous, et revient à l'origine pour le changement de pièce. Il se déplace à vide à 30 mm par seconde. Ce qui est libre, c'est l'ordre. C'est le problème du voyageur de commerce (travelling salesman problem, TSP en anglais) : visiter chaque point une fois, revenir au départ, et parcourir le moins possible.

La fonction de coût est la longueur de la trajectoire, d'où l'on tire le temps de déplacement en divisant par la vitesse. Les contraintes sont dans la représentation : un ordre est une permutation, donc chaque trou est percé une fois, et le retour au départ fait partie de la mesure.

Dans la figure suivante, on construit soi-même un ordre de perçage en cliquant les trous l'un après l'autre. Le tracé, la longueur et le temps se mettent à jour à chaque trou. La figure ne juge pas l'ordre avant la fin, et l'ordre dans lequel le plan écrit les trous, celui que le programme suit sans réfléchir, peut se superposer à tout moment.

L'ordre du plan mesure environ 1 080 mm, soit 36 secondes de déplacement. Une fois la tournée complète, la figure donne aussi la meilleure tournée connue, obtenue par un calcul exact mené une fois pour toutes : c'est elle qui sert de référence dans le calcul qui suit.

Environ soixante-quatorze minutes de machine par semaine, sans acheter quoi que ce soit ni changer une seule pièce : c'est le rendement d'une bonne modélisation suivie d'une bonne recherche, et c'est pourquoi l'entreprise s'y intéresse.

Et l'on ne peut pas se contenter d'essayer tous les ordres : 479 millions pour douze trous, treize fois plus au trou suivant. Le chapitre suivant en fait le sujet.

Encore faut-il compter juste ce qu'il y aurait à essayer, une fois écartés les doublons de la permutation.

Contrainte dure ou pénalité

La capacité de cent heures est une contrainte dure : une solution qui la viole est irréalisable, et elle est écartée. C'est le cas le plus simple, mais ce n'est pas le seul choix possible. Une autre manière de traiter la capacité est d'autoriser les solutions qui la dépassent, et de les punir : on retranche à la marge un montant proportionnel au dépassement.

Les deux choix ont chacun leur intérêt. La contrainte dure ne recommande jamais l'impossible, mais elle interdit à une recherche de traverser une zone irréalisable pour atteindre une bonne solution de l'autre côté. La pénalité laisse passer, et tout dépend alors de $\lambda$. Trop faible, la recherche préfère violer la capacité, parce que cela rapporte. Trop forte, elle a peur d'en approcher et se comporte comme une contrainte dure. Le bon $\lambda$ se règle en mesurant.

Lire la colonne des heures. Sans pénalité, la meilleure sélection retient les dix commandes, soit 223 heures. Avec un poids modeste, elle dépasse encore la capacité, et à 190 € par heure c'est encore le cas : C1, C6, C8 et C9 (105 heures, 14 300 €) valent 13 350, plus que la meilleure sélection réalisable, 13 300, parce que les cinq heures de trop rapportent 1 000 € et n'en coûtent que 950. Le seuil se lit dans ce rapport, 1 000 € pour cinq heures : au-dessus de 200 € par heure, la recherche revient à la meilleure sélection réalisable.

Au fil du parcours, les deux approches reviendront : la contrainte dure, quand une solution fabriquée est vérifiée puis rejetée ou réparée ; la pénalité, quand une recherche doit pouvoir traverser une zone interdite, comme dans le recuit simulé, une méthode que le parcours présentera plus loin.

Ranger un problème d'optimisation

Une fois la décision, les contraintes et le coût écrits, quatre questions rangent le problème dans une famille. La réponse dit à quoi s'attendre : quelles méthodes s'appliquent, et ce que coûtera la recherche.

Continu, discret ou mixte

Une solution se décrit par des variables de décision, les grandeurs qu'elle fixe. Une variable est réelle quand elle peut prendre toute valeur d'un intervalle (une quantité, une durée, une fraction), entière quand elle compte (un nombre de lots, une heure de début), binaire quand elle ne vaut que 0 ou 1, cas particulier de l'entière. Le problème est continu si toutes ses variables sont réelles, discret si toutes sont entières ou binaires, mixte s'il mêle les deux.

Les deux problèmes de ce chapitre sont discrets : dix variables binaires pour les commandes, chacune valant 1 si la commande est lancée, et un ordre des douze trous pour la plaque. Autoriser une fraction de commande, une moitié, un tiers, rendrait le premier continu. Décider à la fois quelles commandes lancer et combien d'heures supplémentaires payer, une quantité réelle de zéro à dix, en ferait un problème mixte.

Le discret est en général le plus difficile. Dans un problème continu, une solution se déplace d'aussi peu qu'on veut, et la pente de l'objectif dit de quel côté aller ; un problème linéaire à variables réelles se résout pour des milliers de variables. Dans un problème discret, on saute d'une solution à une autre sans intermédiaire, et le nombre de solutions explose avec la taille : c'est le sujet du chapitre 2. La version continue garde pourtant un rôle. Elle admet plus de solutions, donc un optimum au moins aussi bon, qui sert de borne au problème discret : c'est le point de départ du chapitre 4.

Avec ou sans contraintes

Un problème est sans contraintes quand toute solution qu'on peut écrire est réalisable, avec contraintes quand il reste à le vérifier. La frontière dépend en partie de la représentation. Écrite en permutation, la tournée n'a plus rien à vérifier : chaque trou percé une fois, retour au départ, tout est dans la structure. Écrites en zéros et uns, les commandes gardent la capacité, qu'une liste peut dépasser. La pénalité de la section précédente fait d'un problème avec contraintes un problème sans contraintes : la capacité cesse de trier les solutions et entre dans le coût. La différence se voit pendant la recherche. Sans contraintes, toute retouche d'une solution donne une solution ; avec, une retouche peut sortir du réalisable, et il faut la rejeter, la réparer ou la pénaliser.

Un objectif ou plusieurs

Un problème a souvent plusieurs objectifs, et ils se contredisent. Les dix ordres de fabrication que le chapitre 6 ordonnancera en donnent un exemple. Les ordres qui minimisent la somme des retards, à 17 heures, laissent tous un ordre en retard de 14 heures. Le plus grand retard peut descendre à 11 heures, pas moins, mais le meilleur ordre qui y parvient cumule 23 heures de retard. Aucun ordre ne fait les deux. Une solution est dite non dominée, ou optimale au sens de Pareto, quand aucune autre ne fait au moins aussi bien sur tous les objectifs et mieux sur l'un d'eux. Les solutions non dominées n'offrent ici que deux compromis, 17 heures au total et 14 au plus, ou 23 et 11, et choisir entre eux est une décision que le calcul seul ne tranche pas. Deux façons courantes ramènent le problème à un seul objectif, et chacune a sa limite.

• Pondérer les objectifs. Minimiser la somme des retards plus $w$ fois le plus grand retard, où le poids $w$ dit combien d'heures de retard cumulé vaut une heure de plus grand retard. Avec un poids inférieur à 2, le plan à 17 heures l'emporte ; au-delà, celui à 23 heures. La pénalité de la section précédente est une pondération de ce genre, entre la marge et le dépassement. La limite : le poids est un prix qu'il faut savoir justifier, la réponse saute d'un plan à l'autre quand il franchit un seuil, et, sur d'autres problèmes, certains compromis ne sortent pour aucun poids.
• Passer un objectif en contrainte. Minimiser la somme des retards, sous la condition qu'aucun ordre ne finisse plus de 13 heures après son échéance. La capacité traitée en contrainte dure est de ce type : le dépassement, que la pénalité pesait contre la marge, ne peut plus valoir que zéro. La limite : le seuil est une décision lui aussi, et il agit en tout ou rien. Avec un seuil de 13 heures, la réponse est le plan à 23 heures ; avec 14, celui à 17. Une heure de seuil vaut ici six heures de retard cumulé, ce que le modèle ne montre que s'il est relancé pour plusieurs seuils. Et sous 11 heures, plus aucun ordre ne respecte la condition.

Déterministe ou stochastique

Un problème est déterministe quand ses données sont connues au moment de décider, stochastique quand certaines sont incertaines : une demande future, un temps de trajet, la durée réelle d'un ordre. Les heures et les marges des dix commandes sont connues lundi matin ; celles des commandes de la semaine suivante ne le sont pas encore. Quand une donnée est incertaine, l'incertitude entre dans le modèle : on la décrit par des scénarios ou par une loi de probabilité, le coût d'une solution devient une répartition de valeurs plutôt qu'un nombre, et il faut dire ce qu'on optimise, la moyenne, une mauvaise semaine ou le pire cas. Le chapitre 13 le fait pour les durées des ordres : l'ordre optimal sur les temps standards, à 17 heures de retard, en compte 48,1 en moyenne quand les durées réelles s'en écartent.

Le hasard d'une méthode ne rend pas un problème stochastique. Les recherches des chapitres 7 à 11 tirent leurs essais au hasard, sur des données parfaitement connues : le hasard est dans la méthode, pas dans le problème.

Presque tout le parcours traite des problèmes discrets, à un objectif, aux données connues. Le chapitre 13 sort deux fois de ce cadre : des durées incertaines, et un second objectif, la stabilité du plan d'un jour à l'autre, pondéré avec les retards.

Les erreurs de modélisation d'un débutant

Le fil du parcours

Valdrome revient avec cinq problèmes, toujours les mêmes données, consignées dans un fichier de référence.

Le chapitre suivant montre ce qui rend un problème difficile, et pourquoi on ne peut pas tout essayer. Viennent la programmation linéaire, les bornes et les méthodes exactes, d'autres modèles de calcul, des règles de construction, la recherche locale et quatre méthodes qui échappent à ses pièges, la comparaison des méthodes, et enfin leur confrontation à un solveur et à la vie de l'atelier. L'ordonnancement de ce parcours n'a ni précédences entre ordres ni conflits à colorer ; si l'on en ajoutait, les chapitres graphes orientés et coloration du parcours Graphes serviraient. Sur la notion de difficulté, on renvoie à ce que le chapitre complexité pose déjà.

Mettre en pratique