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é les 1 024 sélections possibles, 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, une fois rejouée : c'est en la regardant charger le conteneur qu'on le constate, pas en croyant ce texte.

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 la moitié des erreurs de modélisation vient 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.

É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. Ce n'est pas un détail. 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. Or aucune des deux règles n'atteint l'optimum, comme la figure le montre en les rejouant, une fois l'optimum trouvé : il existe, dans les deux cas, une sélection réalisable qui rapporte davantage. Une règle de bon sens donne des solutions plausibles, proches les unes des autres, et sans tout essayer on ne sait pas 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.

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 n'interdit ni le doublon ni le numéro inexistant, et chaque sélection s'y écrit de plusieurs façons. Les zéros et les uns n'ont aucun de ces défauts. Notons ce qu'ils ne font pas : 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 n'écrivent que 79 des 1 024 sélections : celles où plus aucune commande ne tient. C7 seule n'en fait pas partie, puisque, quel que soit l'ordre, au moins deux 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 avec fierté. Le remède est de choisir la permutation, qui ne laisse rien passer, plutôt que de compliquer le test.

Le coût : la trajectoire de la perceuse

Passons à 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 le pire est qu'on ne peut pas se contenter d'essayer tous les ordres : 479 millions pour douze trous, et ce nombre se multiplie par treize au trou suivant. Le chapitre suivant en fait le sujet.

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é : en imposant de rester dedans, on la coince. La pénalité laisse passer, et tout dépend alors de $\lambda$. Trop faible, la recherche préfère violer la capacité, parce que ça 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.

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 pourquoi on ne peut pas tout essayer. Viennent ensuite des bornes, qui disent ce qu'on peut espérer, puis des règles simples de construction, la recherche locale, le recuit simulé, la recherche tabou, les algorithmes génétiques, les fourmis, et enfin la comparaison des méthodes entre elles et avec un solveur. 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à.

Exercices type

La méthode

1. Écrire la décision en une phrase, avec ce qu'on choisit et ce qu'on ne choisit pas.
2. Lister toutes les contraintes, y compris celles qui « vont de soi ».
3. Écrire la fonction de coût, et dire si l'on minimise ou maximise.
4. Choisir la représentation en se demandant quels objets elle laisse passer qui ne sont pas des solutions.
5. Décider de chaque contrainte : dure, ou pénalité, en se demandant ce qui se passe réellement quand elle est violée.
6. Évaluer à la main quelques solutions, dont une irréalisable, avant de programmer la moindre recherche.
7. Fixer l'instance, pour que deux méthodes se comparent sur les mêmes données.

Synthèse

• Une décision se modélise par une instance, une solution, des contraintes et une fonction de coût.
• Une solution est réalisable si elle respecte toutes les contraintes ; l'optimum est la meilleure solution réalisable ; l'espace des solutions contient aussi les irréalisables.
• Évaluer une solution est facile, en temps proportionnel à sa taille ; trouver la meilleure ne l'est pas.
• Un coût sans contrainte recommande l'impossible : il faut deux outils, le coût et le test de réalisabilité.
• La représentation décide de tout ce qui suit. Une bonne représentation n'admet aucun objet impossible, oublie aucune solution utile, en écrit peu de doublons.
• Une représentation qui laisse passer l'impossible oblige à tester à chaque étape, et un test incomplet est pire que pas de test.
• Une contrainte dure écarte toute solution qui la viole ; une contrainte souple passe par une pénalité, qui l'intègre au coût, avec un poids λ à régler en mesurant.
• Le coût est un modèle : la longueur n'est pas le temps. Une bonne solution d'un mauvais modèle est une mauvaise solution.
• Les cinq problèmes de Valdrome reviennent dans tout le parcours avec les mêmes données.