Dans le cas de certains problèmes industriels, les méthodes classiques de programmation linéaire en nombres entiers (modélisation MIP frontale ou méthodes de décomposition et de relaxation) se révèlent inefficaces. Deux contextes sont présentés, l'un dans le domaine de replanification en temps réel, l'autre dans la conception de produits 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, 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.