Soutenance mémoire
Contexte de la thèse
Présentation de LocalSolver
Les problèmes d’optimisation mathématique qui se posent dans les entreprises sont souvent non linéaires, combinatoires, et de très grande taille. Les utilisateurs des outils d’aide à la décision et de recherche opérationnelle souhaitent cependant obtenir des solutions de bonne qualité à ces problèmes, c’est-à-dire respectant les contraintes posées par les utilisateurs (ou modélisateurs), et de qualité supérieure aux solutions qui pourraient éventuellement être construites à la main. De plus, ces solutions doivent être obtenues très rapidement : en quelques minutes, voire quelques secondes. Ce besoin d’obtenir des solutions de qualité en des temps d’exécution très courts a conduit à la création de LocalSolver, solveur de programmation mathématique global de nouvelle génération, développé par la société LocalSolver .
LocalSolver est un « solveur » : il suffit de lui fournir une définition mathématique du problème à résoudre, de façon purement déclarative, sous la forme d’un ensemble de contraintes à respecter et d’objectifs à minimiser ou à maximiser. Une fois cette modélisation faite, l’utilisateur délègue entièrement à LocalSolver la recherche de solutions et de bornes inférieures. Ce fonctionnement de type « model & run » nécessite la mise au point d’algorithmes puissants et génériques au sein du solveur, issus de différentes techniques de la recherche opérationnelle, à la fois exacts et heuristiques. La composante historique de LocalSolver, décrite dans [15] et [43], consiste en une recherche locale à voisinage variable [63, 67] qui lui permet de faire coopérer des transformations locales et rapides de la solution courante avec des modifications plus profondes utilisant des techniques algorithmiques exploitant la structure du problème. Cependant, des composantes exactes sont également intégrées à LocalSolver depuis plusieurs années (programmation linéaire, non linéaire et par contraintes).
Pour modéliser et résoudre des problèmes combinatoires riches, LocalSolver a introduit une modélisation à base d’ensembles et de listes. Ces structures de plus haut niveau que les traditionnelles variables entières et continues de la programmation linéaire mixte, également utilisées dans d’autres solveurs notamment de programmation par contraintes [44, 2, 42], permettent de modéliser de façon naturelle et compacte des problèmes comprenant des notions d’ordre, comme des problèmes de tournées de véhicules, ou des concepts ensemblistes, comme des problèmes de packing. Ces concepts ont permis de conjuguer une grande simplicité de modélisation avec une extrême rapidité de résolution. La généricité des objets introduits (ensembles et listes d’entiers) a permis en outre de ne pas limiter leur usage à des familles de problèmes restreintes. Ainsi, même si les listes sont la structure de choix pour modéliser les problèmes de tournées, elles permettent par exemple aussi de modéliser des problèmes de planification de lignes de production ou d’organisation d’ateliers, ou encore de conception de réseaux.
Introduction aux aspects techniques de LocalSolver
Formalisme de modélisation de LocalSolver
Le formalisme de modélisation de LocalSolver est différent de celui des solveurs de programmation linéaire classiques, et comporte plusieurs caractéristiques propres. Par exemple, il est possible de définir des expressions intermédiaires, qui se distinguent des variables de décision. Ces expressions sont utilisées pour modéliser des quantités pouvant être totalement déduites à partir des valeurs des variables de décision. Elles sont définies de façon directe, sans ajout de contraintes. Leur utilisation facilite ainsi l’écriture du modèle. Afin d’offrir davantage de possibilités de modélisation, ces expressions peuvent de plus être définies au moyen d’opérateurs non linéaires variés (min, max, produit, puissance, racine carrée, modulo, valeur absolue, partie entière, fonctions trigonométriques, condition ternaire, « at » sur un tableau, relations logiques…). LocalSolver peut être utilisé via des API (Python, Java, C++, C#), mais il possède également son propre langage de modélisation, nommé LSP pour LocalSolver Programming language, permettant de définir un modèle d’optimisation de façon purement déclarative. Dans la suite de la thèse, tous les exemples de modélisation seront écrits en LSP.
Variables de décision ensemblistes. Une caractéristique majeure et innovante du formalisme de modélisation de LocalSolver est la possibilité d’écrire des modèles ensemblistes. En effet, en plus des variables de décision numériques classiques (booléens, entiers, réels), LocalSolver offre deux types de variables de décision ensemblistes : les sets et les listes. Une variable de set de domaine n, définie dans le modèle par l’écriture set(n), représente un sous-ensemble (non-ordonné) de {0, …, n − 1} . Dans toute solution, la valeur d’une variable de set est donc un ensemble d’entiers, et non un simple nombre. Les variables de sets sont naturellement utilisées pour modéliser les problèmes dans lesquels on crée des regroupements d’éléments. Par exemple, dans le problème du Bin Packing, chaque conteneur est représenté par une variable de set, dont la valeur est égale à l’ensemble des éléments qu’il contient. Ces variables sont également utilisées dans les problèmes de clustering : chaque set représente alors une catégorie.
De façon similaire, une variable de liste de domaine n, définie dans le modèle par l’écriture list(n), représente une permutation d’un sous-ensemble de {0, …, n − 1}. Les variables de listes sont alors naturellement utilisées pour définir des ordres. Par exemple, les problèmes de tournées de véhicules sont modélisés à partir de variables de listes : chaque liste est associée à un véhicule, et représente l’ordre des points visités par ce véhicule. Les variables de listes jouent également un rôle crucial dans la modélisation des problèmes d’ordonnancement, puisqu’elles peuvent être utilisées pour représenter l’ordre des tâches affectées à une ressource disjonctive. Il existe plusieurs opérateurs spécifiques aux variables de sets et de listes. Les opérateurs « partition », « disjoint » et « cover » servent à définir des contraintes globales sur des familles de variables ensemblistes de même type et de même domaine. Si mySetVariables est un ensemble de variables de sets (ou de listes) de domaine n, l’écriture constraint partition(mySetVariables) (resp. constraint disjoint(mySetVariables), resp. constraint cover(mySetVariables)) indique que chaque élément de {0, …, n − 1} doit être présent exactement une fois (resp. au plus une fois, resp. au moins une fois) dans l’ensemble des variables de mySetVariables. D’autres opérateurs permettent d’obtenir des informations sur le contenu des différents sets et listes : l’opérateur count donne le nombre d’éléments présents dans la variable, contains permet de tester l’appartenance d’un élément à un set ou une liste, indexOf donne la position d’un élément dans une liste, find permet de retrouver la variable de set ou liste contenant un élément donné.
Opérateurs variadiques et lambda-fonctions. LocalSolver offre la possibilité d’appliquer des opérateurs variadiques n-aires (somme, min, max, opérateurs logiques) avec un nombre de termes dynamique. Cela permet par exemple de calculer une somme dont le nombre de termes n’est pas constant, et dépend de la valeur d’autres expressions, comme une variable de set ou de liste. Ces opérateurs variadiques sont typiquement utilisés pour calculer une somme sur les éléments d’une variable ensembliste. Par exemple, dans le problème du Bin Packing, on peut calculer la somme des poids des éléments i contenus dans un bin k modélisé par une variable de set bin[k] de la façon suivante :
binWeight[k] <- sum(bin[k], i => elementWeight[i]);
De même, dans le problème du Voyageur de Commerce, si l’on note n le nombre de villes et order la variable de liste représentant l’ordre dans lequel les différentes villes sont visitées, la distance parcourue peut être calculée à l’aide d’une somme variadique :
totalDistance <- sum(0..n-2, i => distance[order[i]][order[i+1]]) + distance[order[n-1]][0];
Comme on peut le voir sur ces deux exemples, l’expression des termes à sommer est donnée par une lambda-fonction (écrite i => elementWeight[i] ci-dessus pour le problème du Bin Packing par exemple).
Remarque 1.1 (Notations). Comme expliqué à la Section précédente, la modélisation des problèmes d’ordonnancement disjonctif avec LocalSolver est un des enjeux majeurs de cette thèse. Dans les différents Chapitres constituant la thèse, on présentera donc plusieurs exemples en code LSP. On présentera ainsi les modèles LSP complets de certains problèmes, mais aussi des expressions génériques permettant de modéliser certaines contraintes rencontrées dans de nombreux problèmes d’ordonnancement. Pour simplifier les notations et par souci de clarté, on utilisera à la fois une police mathématique pour désigner des objets tels que les tâches et les ressources, et une police monotype pour désigner les variables de décision et constantes intervenant dans le modèle. Par exemple, on pourra s’intéresser à une ressource disjonctive notée r, et à une variable de liste notée order[r] représentant l’ordre des tâches qui lui sont affectées. Une tâche t s’exécutant sur la ressource r sera alors représentée par l’élément t dans la liste order[r]. Autre exemple, on pourra également considérer le temps de transition setup[r][prev][next] à respecter entre la fin d’une tâche tprev et le début de la tâche suivante tnext sur une ressource r.
Structures internes de LocalSolver
On décrit ici les principaux outils algorithmiques et mathématiques utilisés dans les différentes composantes de LocalSolver. On se concentre en particulier sur la composante de recherche locale [43, 15], dans laquelle s’inscrivent les travaux de cette thèse. La recherche locale est une technique d’amélioration itérative d’une solution initiale, mettant en œuvre des opérateurs de voisinage, algorithmes élémentaires et généralement très rapides permettant de trouver la meilleure solution voisine d’une solution selon un voisinage prédéfini (par exemple, la permutation de deux tâches consécutives dans la séquence des tâches affectées à une ressource disjonctive). Selon les types et la variété des voisinages considérés, on trouve différentes méthodes de recherche locale. En particulier, la recherche à voisinage variable (Variable Neighborhood Search ou VNS) [63, 67], sur laquelle est basé LocalSolver, alterne différents types de voisinages dans un but d’intensification de la recherche autour d’une bonne solution, et de diversification de la recherche pour s’extraire des minima locaux. Lorsque le voisinage considéré est de taille exponentielle, on parle de recherche locale à voisinage étendu (Large Neighborhood Search ou LNS). Dans ce cas, la recherche de la meilleure solution dans le voisinage est effectuée au moyen d’un algorithme polynomial, ou du moins très efficace, généralement adapté à la structure du sous-problème définissant le voisinage. Les algorithmes de recherche locale traditionnels sont souvent dédiés à la résolution d’un problème particulier. Les voisinages qu’ils explorent sont alors basés sur la structure métier du problème. Une telle approche ne convenant pas dans un solveur générique, ce principe a été industrialisé dans la composante historique de LocalSolver, aboutissant ainsi à une recherche locale générique, avec des voisinages basés uniquement sur la structure mathématique du modèle, et applicable à des problèmes quelconques.
|
Table des matières
1 Introduction
1.1 Contexte de la thèse
1.2 Introduction aux aspects techniques de LocalSolver
1.3 Revue de littérature en ordonnancement
1.4 Plan de la thèse
2 Modélisation de tâches et ressources disjonctives avec LocalSolver
2.1 Introduction
2.2 Lien entre listes et entiers : simple notion d’ordre
2.3 Utilisation des variables entières et de listes pour modéliser les ressources disjonctives
2.4 Mouvements de recherche locale sur les tâches
2.5 Conclusion
3 Réparation de solutions par propagation de réseaux d’inégalités
3.1 Introduction
3.2 Mécanisme de réparation : définitions et algorithme général
3.3 Réparation de contraintes binaires portant sur des variables booléennes
3.4 Réparation de contraintes binaires portant sur des variables numériques
3.5 Réparation de disjonctions et de chaînes d’inégalités linéaires binaires portant sur des variables numériques
3.6 Réparation d’inégalités linéaires ternaires portant sur des variables numériques
3.7 Résultats numériques
3.8 Conclusion
4 Le problème de l’Assembly Line Balancing
4.1 Introduction et définition du problème
4.2 Algorithme constructif
4.3 Mouvement de packing à base de chaînes d’éjection
4.4 Synthèse des résultats numériques
4.5 Conclusion
5 Conclusion
