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.

Abstract

My Ph.D. research was motivated by the following intuition: a primal approach is always preferred to a dual approach in very large-scale optimization problems.Exact primal approaches refer to any approach that allows moving from a feasible integer solution to a feasible integer one until reaching the optimal solution. Thus, a primal ap-proach quickly converges if we have a good initial solution. It is worth mentioning that most known heuristics based on local search are primal but not exact. These heuristics are widely used in practice thanks, among other things, to this primal aspect. On the other hand, an approach that is not primal is called dual. Benders decomposition is an example of a dual approach that shows zigzag behavior making convergence slow, which is problematic in practice. Based on this primal intuition, this thesis highlights the benefits of using primal approaches to tackle very large-scale optimization problems since they effectively profit from the available primal information (e.g., history of solutions). This is the case in real-life con-texts, where organizations face very large-scale problems for which they usually have good primal solutions close to the optimal solution (in terms of solution support). The goal is to use these solutions (primal information) to reach (near-)optimal solution(s) quickly. All the essays in this dissertation can be put under the umbrella of primal large-scale optimization from different perspectives.In the first essay of this dissertation, I explore the primal large-scale optimization from a solver perspective. In particular, I study the parameter configuration problem, which consists of finding a parameter configuration that gives a particular algorithm the best performance. I introduce a new multi-phase tuner based on the iterated local search (ILS) meta-heuristic: the multi-phase iterated local search (MPILS) tuner. This tuner addresses the parameter configuration problem for deterministic mixed-integer linear programming (MILP) solvers that are used to solve challenging very large-scale optimization problems. Further, the pro-posed tuner offers a new search strategy based on three ideas. First, instead of tuning in the entire configuration space induced by the parameter set, the multi-phase tuner focuses on a small parameter pool that is dynamically enriched with new promising parameters. Second, it leverages the gathered knowledge during the search using statistical learning to forbid less promising parameter combinations. Third, it tunes on a single instance provided by earlier clustering of MILP instances. The MPILS tuner is primal since the ILS metaheuristic is pri-mal. The tuner obtains near-optimal solutions in a few minutes on several NP-hard realistic instances provided by the industrial partner. Next, I explore the primal large-scale optimization from a metaheuristic perspective. I study a multiobjective, MILP model that integrates production scheduling, inventory management, and vessel assignment for a global supply chain. Given that such large-scale problems are NP-hard and usually suffer from symmetry, I conduct an exploratory analysis to identify complexity sources. Following this, I design a novel variant of the large neighborhood search metaheuristic to tackle the problem efficiently. This variant takes advantage of primal infor-mation and converges incrementally towards (quasi-)optimal solutions, which is very practical for large-scale optimization problems. Furthermore, while symmetry is considered an issue in the literature, the implemented algorithm provides a practical way of profiting from sym-metry instead of breaking it. On several real instances (which typically take several hours) of the problem considered, (quasi-)optimal solutions are obtained in less than 10 minutes.In the third essay of this dissertation, I explore the primal large-scale optimization from an exact perspective. Among several decompositions, the Benders decomposition has been significantly applied to tackle very large-scale problems with complicating variables, which, when temporarily fixed, yield problems easy to solve. Still, in its standard form, the Benders decomposition does not profit from the primal information and shows a zigzagging behavior, making convergence very slow, which is problematic in practice. Driven by observations from the practice, I propose the primal Benders decomposition (PBD) for sparse very large-scale problems, for which most complicating variables are equal to zero in the optimal solution. This method, a paradigm shift, uses the PBD master problem to select the complicating variables to insert in the PBD subproblem, which is a restriction of the original problem, instead of fixing them (source of zigzag). The PBD avoids zigzagging and converges towards the optimum in a monotonous way and thus improves the primal solution at each iteration. It is a very practical primal behavior (instead of a dual behavior which has handicapped the Benders decomposition since its birth more than 50 years). The generated cuts are of better quality because the solutions obtained are of better quality, which implies the generation of fewer cuts to converge. The results of the PBD on instances of the facility location problem and others from the problem that motivated this research demonstrate the method’s potential.After perturbation, the re-optimized solution remains close to the perturbed solution and is therefore rich in primal information. For this reason, a primal approach would be most efficient. In the next essay, I explore the primal large-scale optimization from an learn-ing perspective. In particular, I explore the role of learning from the available history in re-optimizing after perturbations. Indeed, perturbations are universal in large-scale opti-mization, and their appearance has become more frequent in the past few years due to global events. In such a case, re-optimization can support companies in achieving resilience by enabling them to simulate several what-if scenarios and adapt to changing circumstances and challenges in real-time. I design a generic and scalable resilience re-optimization frame-work. I model perturbations, recovery decisions, and the resulting re-optimization problem, which maximizes resilience. I leverage the primal information through fixing, warm-start, and machine learning. Finally, I merge, leverage, and implement the various heuristic and exact operations research tools above in one system, which allowed operations research specialists at the OCP Group, the Mohammed VI Polytechnic University, and the Polytechnique Montreal to operationalize a system that optimizes the OCP downstream supply chain operations. Furthermore, inspired by the practice, the team implemented a novel hybrid variant of Benders decomposition, which consists of fixing some complicating variables related to confirmed orders and freeing others related to unconfirmed orders in the Benders subproblem. OCP management now credits the system operationalization with providing operational benefits, contributing to over a $240 million increase in annual turnover, or equivalently enough fertilizers to feed 30 million humans.Keywords. Large-Scale Optimization, Benders Decomposition, L-shaped Method, Dantzig-Wolfe Decomposi-tion, Mixed-Integer Programming, Parameter Configuration Problem, MILP Solvers, Metaheuristics, Machine Learning, Re-optimization, Resilience, Perturbation, Supply Chain Management, OR@AFRICA.