Primal Methods for Very Large-Scale Optimization

Cette thèse de doctorat a été motivée par l’intuition suivante: une approche primale est toujours préférée à une approche duale dans l’optimisation des problèmes à très grande échelle. Les approches primales exactes font référence à toute approche permettant de passer d’une solution réalisable entière à une solution réalisable entière jusqu’à convergence à une solution réalisable optimale. Une approche primale converge ainsi rapidement si nous avons une bonne solution initiale. Il est à noter que la plupart des heuristiques connues basées sur la recherche locale sont primales mais non exactes. Ces heuristiques sont très utilisées en pratique grâce entre autres à cet aspect primal. D’autre part, une approche qui n’est pas primale est dite duale. La décomposition de Benders est un example d’approche duale qui montre un comportement en zigzag rendant la convergence lente, ce qui est problématique en pratique. Basée sur cette intuition primale, cette thèse met en évidence les avantages de l’utilisation d’approches primales pour aborder des problèmes d’optimisation à très grande échelle puisqu’elles profitent efficacement de l’information primale disponible (par exemple, l’historique des solutions). Ceci est le cas dans plusieurs contextes réels, où les organisations sont confrontées à des problèmes de grande taille pour lesquels elles disposent généralement de bonnes solutions primales proches de la solution optimale (en termes du support de solution). L’objectif est d’utiliser ces solutions (information primale) pour atteindre rapidement des solutions (presque) optimales. Tous les travaux de cette thèse peuvent être regroupés sous l’égide de l’optimisation primale à grande échelle de différentes perspectives. Dans le premier essai de cette thèse, nous explorons l’optimisation primale à grande échelle du point de vue solveur. En particulier, nous étudions le problème de configuration des paramètres, qui consiste à trouver une configuration de paramètres qui donne à un algorithme particulier les meilleures performances. Nous introduisons un nouveau tuner multiphase basé sur la métaheuristique de recherche locale itérée (iterated local search). Ce tuner résout le problème de configuration des paramètres pour les solveurs déterministes utilisés pour résoudre des problèmes d’optimisation difficiles à très grande échelle. De plus, le tuner propose une nouvelle stratégie de recherche basée sur trois idées. Premièrement, au lieu d’explorer l’espace exponentiel de configurations induit par l’ensemble de paramètres, le tuner multiphase se concentre sur un petit pool de paramètres enrichi de manière dynamique avec de nouveaux paramètres prometteurs. Deuxièmement, il exploite les connaissances acquises au cours de la recherche en utilisant l’apprentissage statistique pour interdire les combinaisons de paramètres moins prometteuses. Troisièmement, il s’entraîne sur une seule instance fournie par un clustering antérieur des instances considérées. Le tuner est primal car l’heuristique utilisée est primale. Il permet l’obtention de plusieurs solutions (quasi-)optimales en quelques minutes sur plusieurs instances. Ensuite, nous explorons l’optimisation primale à grande échelle d’un point de vue méta-heuristique. Nous étudions un modèle linéaire mixte en nombres entiers qui intègre la plan-ification de la production, la gestion des stocks et l’affectation des navires pour une chaîne d’approvisionnement globale. Étant donné que de tels problèmes à grande échelle sont NP-difficiles et souffrent généralement de la symétrie, nous effectuons une analyse exploratoire pour identifier les sources de complexité. Suite à cela, nous concevons une nouvelle vari-ante de la métaheuristique de recherche par voisinnage pour résoudre le problème efficace-ment. Cette variante profite de l’information primale et converge de manière incrémentale vers des solutions (quasi-)optimales, ce qui est très pratique pour les problèmes de grande taille. En outre, bien que la symétrie soit considérée comme un problème dans la littérature, l’algorithme mis en œuvre fournit un moyen pratique de profiter de la symétrie au lieu de la briser. Sur plusieurs instances réelles du problème considéré, des solutions (quasi-)optimales sont obtenues en moins de 10 minutes. Dans le troisième essai de cette thèse, nous explorons l’optimisation primale à grande échelle d’un point de vue exact. Parmi plusieurs décompositions, la décomposition de Benders a été appliquée de manière significative pour résoudre des problèmes à très grande échelle avec des variables complexes qui, une fois temporairement fixées, donnent lieu à des problèmes faciles à résoudre. Pourtant, dans sa forme standard, la décomposition de Benders ne profite pas de l’information primale et montre un comportement en zigzag, rendant la convergence très lente, ce qui est problématique en pratique. Sur la base d’observations issues de la pratique, nous proposons la primal Benders decomposition (PBD) pour des problèmes peu denses de grande taille, pour lesquels les variables les plus compliquées sont égales à zéro dans la solution optimale. Cette méthode, un changement de paradigme, utilise le problème maître de PBD pour sélectionner les variables compliquantes à insérer dans le sous-problème PBD, qui constitue une restriction du problème d’origine, au lieu de les fixer (source de zigzag). La PBD évite le zigzagging et converge vers l’optimum d’une façon monotone et ainsi améliore la solution primale à chaque itération. C’est un comportement primal très pratique (au lieu d’un comportement dual qui handicapait la méthode Benders depuis sa naissance il y a plus de 50 ans). Les coupes générées sont de meilleure qualité car les solutions obtenues sont de meilleure qualité, ce qui implique la génération de moins de coupes pour converger. Les résultats de la PBD sur des instances du facility location problem et d’autres réelles du problème qui a motivé cette essai démontrent les avantages de la méthode. Dans l’essai suivant, nous explorons l’optimisation primale à grande échelle dans une perspective d’apprentissage. En particulier, nous étudions le rôle de l’apprentissage sur l’information primale pour ré-optimiser après des perturbations. En effet, les perturbations sont uni-verselles pour les problèmes à très grande échelle et leur apparition est devenue plus fréquente ces dernières années en raison des événements globaux. Dans un tel cas, la réoptimisation peut aider les entreprises à atteindre leur résilience en leur permettant de simuler plusieurs scénarios de simulation et de s’adapter aux circonstances et aux défis changeants en temps réel. Nous concevons un cadre de réoptimisation pour la résilience. Nous modélisons les per-turbations, les décisions de réparation et le problème de réoptimisation qui en résulte avec le but de maximiser la résilience. Nous exploitons l’information primale grâce à la correction, au warmstart et à l’apprentissage automatique. Les résultats numériques démontrent que, dans plusieurs cas, l’optimisation locale (sur une partie de la supply chain) est suffisante pour réoptimiser rapidement après des perturbations. Enfin, nous fusionnons, exploitons et implémentons les différents outils heuristiques et ex-acts de recherche opérationnelle ci-dessus dans un seul système, ce qui a permis aux spé-cialistes de la recherche opérationnelle du Groupe OCP, de l’Université Polytechnique Mo-hammed VI et de Polytechnique Montréal d’opérationnaliser un système qui optimise la chaîne d’approvisionnement du Groupe OCP. De plus, inspirée par la pratique, l’équipe a implémenté la hybrid Benders decomposition (HBD), qui consiste à fixer certaines variables compliquées liées aux commandes confirmées (comme dans la décomposition de Benders) et à garder libre les autres liées aux commandes non confirmées dans le sous-problème de Ben-ders (comme dans PBD). La direction d’OCP attribue désormais à l’opérationnalisation du système des avantages opérationnels, contribuant à une augmentation de plus de 240 millions de dollars du chiffre d’affaires annuel, soit l’équivalent de suffisamment d’engrais pour nourrir 30 millions d’êtres humains. Mots-clés. Optimisation à grande échelle, Décomposition de Benders, Méthode en forme de L, Décomposition de Dantzig-Wolfe, Programmation en nombres entiers, Problème de configuration des paramètres, Solveurs MILP, Métaheuristiques, Apprentissage Automatique, Réoptimisation, Résilience, Perturbation, Gestion de la chaîne d’approvisionnement, OR@AFRICA.