L’un des grands challenge que rencontre EURODECISION lors de l’accompagnement de clients sur des problématiques mêlant métier de pointe et mathématiques n’est pas forcément celui que l’on croit. En effet lorsque l’on place des experts en régulation aérienne et des experts en recherche opérationnelle autour d’une table il est possible qu’une discussion dans laquelle chacun parle une langue différente se produise. Tout l’enjeu d’un projet mené à bien réside à ce moment-là dans la communication. On pourrait alors citer Bernard Werber « […] il y a dix possibilités qu’on ait des difficultés à communiquer. Mais essayons quand même… ». La compréhension de la problématique se précise et évolue, pouvant compromettre les modélisations classiques initialement envisagées. De plus les besoins et donc les problèmes industriels eux-mêmes évoluent avec le temps. Ainsi, concevoir un modèle souple et évolutif constitue un vrai atout dans le temps.
EURODECISION résout beaucoup de problèmes industriels à l’aide de méthodes classiques de programmation linéaire en nombres entiers (modélisation MIP frontale ou méthodes de décomposition et de relaxation), qui s’appuient sur des méthodes exactes garantissant des solutions optimales, ce qui tend à les privilégier lorsque le problème posé se prête à les utiliser. Néanmoins, elles se révèlent parfois inefficaces, soit parce que la combinatoire ne permet pas des temps de calcul compatibles avec la réalité des industriels, soit parce que certaines contraintes ne sont pas linéarisables ou difficilement.
Les heuristiques ne sont pas des méthodes exactes et il n’est pas toujours facile d’approcher l’optimalité. En revanche elles sont malléables et n’imposent pas de modélisation linéaire des problèmes. En réduisant la complexité du problème, elles permettent de contrôler efficacement le temps de résolution.
Ainsi, combiner des méthodes basées sur la programmation linéaire et des heuristiques peut se révéler très bénéfique, les inconvénients des unes étant compensées par les avantages des autres. On parle de méthodes hybrides.
Nous illustrons ce propos avec deux contextes différents : l’un dans le domaine de replanification en temps réel, l’autre dans la conception de produits, bâtiments ou de procédés industriels.
Dans le premier cas, l’enjeu est de fournir une bonne solution « métier » dans un temps de calcul contraint, ce qui n’est pas garanti avec les algorithmes de Branch & Bound des solveurs de programmation linéaire en nombres entiers. C’est pourquoi nous avons mis en œuvre une hybridation consistant à :
- Implémenter des heuristiques, basées sur des algorithmes de graphes et sur des règles recueillies auprès d’experts « métier », afin de piloter la sélection des variables entières et des booléens et l’affectation de valeurs à ces variables ;
- Une fois les variables entières et booléennes fixées, résoudre un programme linéaire avec uniquement des variables réelles.
Dans le second cas, l’enjeu est de prendre en compte des contraintes complexes d’un point de vue métier et difficiles à modéliser en programmation linéaire ; par exemple des contraintes portant sur des incompatibilités géométriques dans un espace, sur la logique “métier” d’un procédé, ou le respect de normes pour un système. En effet, cela nécessite de modéliser de nombreuses contraintes à base de variables booléennes et de BigM, ce qui entraine rapidement une explosion combinatoire et une impossibilité de résoudre des problèmes réels. C’est pourquoi nous avons mis en œuvre une hybridation consistant à :
- Implémenter des heuristiques, basées sur des algorithmes de graphes et sur des règles recueillies auprès d’experts « métier », servant à générer et à évaluer des solutions candidates ;
- Sélectionner la meilleure ou les meilleures solutions candidates à l’aide d’un programme linéaire.
Dans le premier cas, on peut parler de MIP heuristique. Dans le second cas, on peut parler de génération de colonnes heuristique. Dans les deux cas, nous décomposons le problème puis nous appliquons la programmation linéaire, des algorithmes de graphes ou des heuristiques à un sous-problème pour lequel chaque technique est la plus adaptée et la plus pertinente, que ce soit pour l’expressivité des contraintes « métier » ou la performance en temps de calcul.
De plus, dans les deux ces approches de résolution se révèlent particulièrement adaptables aux évolutions de la vie d’un produit ou d’un procédé industriel.
De manière générale les principaux objectifs comblés par l’utilisation d’approches hybrides sont :
- Tirer le meilleur de chaque méthode : programmation linéaire, programmation par contrainte, heuristiques, algorithmes de graphe, règles métiers
- Minimiser les risques liés aux évolutions de la problématique industrielle
- Obtenir des résultats en un temps acceptable
- Obtenir des résultats explicables
Les méthodes hybrides répondent à ces objectifs grâce à :
- Leurs modélisations souples et évolutives car non contraint par un modèle linéaire
- Les heuristiques permettent de contenir la combinatoire et donc réduire les temps de calcul
- Les heuristiques « métiers » permettent de reproduire et étendre les règles « métier » facilement explicables.
Ce sujet a été présenté par EURODECISION lors du dernier congrès ROADEF, en février 2022 : « Hybridation « Programmation Linéaire et Heuristiques » pour des problèmes industriels », Aziz JEGHAM, Armelle LE GALL, Gérald PETITJEAN, Matthis PICHON, Simon PIERRE.