Trucs et astuces dans la pratique de la Recherche Opérationnelle (OR)

Blog technique

Auteur
David Gravot

Temps de Lecture
5 minutes

Sommaire

Qu'est-ce que la recherche opérationnelle (RO) et comment fonctionne-t-elle ?

La recherche opérationnelle (RO) est une science aux fondements solides issus des mathématiques (théorie des graphes, optimisation combinatoire, géométrie convexe et non convexe ...), de l'intelligence artificielle (A*, programmation par contraintes), de la recherche locale et d'autres métaheuristiques telles que les méthodes évolutionnaires (Algorithmes Génétiques), le recuit simulé ou encore les méthodes inspirées de la nature comme la fourmilière ou la particule d'essaim.

Aujourd'hui, les praticiens des Recherches Opérationnelles sont répartis dans tout un éventail de secteurs. La plupart d'entre eux sont à la fois analystes et modélisateurs/développeurs. Il n'y a pas de distinction claire entre les modelisaeurs et les développeurs, puisque vous devez écrire votre modèle avec du code ! Cependant, les développeurs OR ne se contentent pas de concevoir le modèle mais les relient également à l'application dorsale, facilitent l'expérience de l'utilisateur grâce à des outils d'analyse de simulation, travaillent en étroite collaboration sur la conception de l'interface utilisateur afin de fournir ce qui facilitera la vie des utilisateurs finaux.

Les praticiens de la Recherche Opérationnelle doivent tenir compte de leur utilisateur final. Il finissent généralement par être planificateurs.

Les praticiens de Recherche Opérationnelle peuvent être en quelque sorte considérés comme des évangélistes de toutes ces techniques avancées, avec un seul objectif : aider les utilisateurs finaux dans leurs opérations. Ces utilisateurs sont la plupart du temps connus sous le nom de "planificateurs" qui sont chargés de créer des "plans". Par exemple, dans le secteur manufacturier, les planificateurs sont chargés d'élaborer différents types de plans : planification de la demande (parfois associée à l'apprentissage machine prédictif), S&OP (planification des ventes et des opérations), RCCP (planification de la capacité de production), planification à moyen terme, planification et ordonnancement à court terme, optimisation des stocks et ordonnancement en temps réel.

Conseil n ° 1

Déléguer le prétraitement et faire gagner du temps aux praticiens du bloc opératoire grâce à ce qu'ils savent le mieux faire (c'est-à-dire modéliser et tester l'optimisation).

Les points forts, une liste non exhaustive des meilleures pratiques en matière de RO.

Conseils et astuces qui peuvent aider le praticien de Recherche Opérationnelle à tirer le meilleur parti de son travail.

Ne charger que les données nécessaires

Habituellement, les modèles de données sont beaucoup plus riches que ce que l'optimisation traite réellement. Pour cela, il y a deux possibilités : soit limiter le modèle de données qui tire les informations des silos de données de l'entreprise, soit prétraiter les données pour créer le scénario à optimiser avec une restriction des données d'entrée disponibles.

Plus de modèles pendant le prototypage

On ne peut faire confiance à un modèle d'optimisation qu'en le testant sur un ensemble de données pertinentes. Lorsque les données arrivent en retard, le risque de créer un modèle mathématique qui pourrait ne pas être à l'échelle est caché. C'est pourquoi nous avons souligné l'urgence d'obtenir des données pertinentes le plus rapidement possible (voir §3.1 Collecte de données). Avec cette hypothèse, le praticien de Recherche Opérationnelle doit arriver rapidement au point où la complexité de son modèle peut être remise en question. Par exemple, si le modèle est continuellement linéaire pour la plupart des contraintes mais un ou deux cas d'utilisation spécifiques qui impliquent une discrétisation, il est absolument essentiel de récupérer ou de construire un ensemble de données qui permettrait de tester cette fonctionnalité.

Conseil n° 2

Utilisez un modeleur pour construire des modèles concurrents pendant la phase de prototypage. Les modeleurs permettent un prototypage beaucoup plus rapide que les langages orientés objet habituels, grâce à un langage et des environnements de test dédiés. Maintenez ces modèles à jour même si le code final est écrit dans une autre langue.

Réutiliser les actifs

Au fil du temps, chez DecisionBrain, nous construisons nos propres bibliothèques qui peuvent être réutilisées lors de la création d'un nouveau produit ou du lancement d'un projet. C'est une bonne pratique qui évite de partir de zéro. Il ajoute aussi progressivement des instances à la bibliothèque commune et améliore sa robustesse, ce qui profite ensuite à tous les autres projets qui l'utilisent.

Plus de tests pendant le prototypage

Utiliser tous les environnements de test disponibles, tels que la ligne de commande CPLEX/CPO . Cela permettra au praticien du bloc opératoire de se concentrer sur le comportement de résolution avec la possibilité de modifier les paramètres sans changer le code, d'analyser le comportement du moteur comme les modèles pré-sollicités du moteur.

CPLEX utilisé pour une application de développement de Recherche Opérationnelle.

Réécrire une partie du modèle

Certains modèles peuvent être mathématiquement équivalents, mais la façon dont certaines contraintes sont mises en œuvre peut faire la différence. Par exemple, dans un problème linéaire, il faut éviter d'obtenir de très longues expressions composées de dizaines de milliers de variables. Parfois, nous pouvons constater des améliorations spectaculaires lorsque nous passons à un modèle "delta". Par exemple, au lieu d'additionner les termes du début à la fin de l'horizon, vous pourriez définir une nouvelle expression qui additionne les termes qui diffèrent d'une période à l'autre.

Analyser les conflits

Les solveurs de haut niveau tels que CPLEX / CPO permettent au praticien de RO de trouver un ensemble minimal de conflits par rapport au modèle original. C'est très utile pour déboguer les modèles mathématiques à un stade précoce et aussi pour détecter les erreurs de données.

Conseil n° 3

Apprenez à extraire un conflit d'un modèle infaisable et à l'analyser pour en comprendre la cause profonde. Utilisez une ligne de commande lorsqu'elle est disponible pour mettre plus rapidement la main sur la détection du conflit.

Documentez vos data et vos modèles mathématiques

Les modèles de données changent et se synchronisent généralement avec le modèle mathématique. Les descriptions des deux modèles doivent être correctement documentées et maintenues tout au long du projet et ensuite pendant sa maintenance. Pensez à d'autres ressources qui pourraient se lancer dans le projet et remplacer l'équipe de développement initiale.

Fournit un mécanisme de rediffusion

Une fois l'application déployée, les travaux d'optimisation sont exécutés chez les clients ou dans le Cloud. Que faire si un emploi échoue ou se termine par des résultats inattendus ? Ce comportement doit être analysé par le développeur OR dans le même contexte que lorsqu'il a été lancé sur l'environnement de production.

Conseil n° 4

Utiliser un environnement de déploiement tel que DOC OS pour récupérer hors ligne un instantané du contexte d'optimisation.

Benchmarking

Construire un module séparé pour les tests d'optimisation de non-régression. Cette référence augmentera son ensemble de données tout au long du cycle de vie du projet. Il mesurera principalement la stabilité (ou l'amélioration) des indicateurs clés de performance de l'optimisation et/ou de l'entreprise. Chaque fois que la qualité du benchmark se dégrade, il est considéré comme un avertissement de haute priorité que quelque chose ne va probablement pas dans le dernier code, y compris les mises à jour des bibliothèques tierces.

Conseil n° 5

Construire un tableau de bord permettant de suivre les principales statistiques de référence (nombre de cas résolus, écart moyen ...).

Solution Injectable

Fournir un outil et une API pour charger une solution externe. Cela nous permet de défier des merveilles naturelles telles que "si j'échange les machines de l'activité 1 et de l'activité 2, je devrais obtenir une meilleure solution". De telles suppositions d'amélioration locale sont tout à fait naturelles à exprimer mais légèrement plus difficiles à mettre en œuvre : elles impliquent probablement la vérification de plusieurs contraintes en cascade. En conséquence, un vérificateur de cette nouvelle solution doit être lancé pour affirmer d'abord la faisabilité de la solution, puis recalculer les indicateurs de qualité de la solution afin de prouver ou de rejeter l'affirmation selon laquelle le déménagement améliore réellement la solution actuelle.
Notez que cette mise en œuvre de contrôle peut être l'un ou l'autre :

Déterministe : nous isolons un ensemble de contraintes à vérifier (capacités, bilan des flux de matières...) et nous recalculons manuellement leur satisfaction/insatisfaction
Grâce au moteur d'optimisation : la solution originale complète plus la modification locale suggérée par le planificateur est injectée dans le modèle du solveur sous forme de contraintes supplémentaires "Variable = valeur". C'est le vérificateur le plus précis puisque le premier peut répondre "vérifier" en laissant certaines contraintes non vérifiées inopérantes

Conseil n° 6

Mélangez le mouvement proposé avec une contrainte qui stipule l'amélioration de la fonction objectif : cela finit par aboutir à un conflit et fournit la preuve que le mouvement n'améliore pas la solution.

Conclusion

Chez DecisionBrain et dans divers endroits du monde, l'industrie utilise de plus en plus les techniques connues sous le nom de Recherche Opérationnelle (RO) pour résoudre efficacement divers problèmes d'organisation dans des conditions de ressources limitées.

Les praticiens de la RO peuvent jouer efficacement un rôle important en mettant des techniques mathématiques très avancées à la disposition des organisations et des planificateurs. Nous espérons que nos divers conseils, trucs et astuces seront précieux pour la réussite de votre prochain projet de Recherche Opérationnelle !

Publié à l'origine septembre 23, 2020, modifié mars 23, 2023

Restez informé grâce à notre blog

A propos de l'auteur
David Gravot est ingénieur expert en optimisation à DecisionBrain. Il a plus de vingt années d’expériences dans l’application des techniques de recherche opérationnelles à de multiples secteurs industriels et de services, notamment dans le domaine manufacturier et la planification de ressources.