Projet de recherche P7/36 (Action de recherche P7)
Domaine du projet
Les problèmes d’optimisation combinatoire peuvent être définis par la recherche au sein d’un ensemble fini de solutions, de la meilleure d’entre elles. Ces problèmes apparaissent partout dans notre monde moderne et globalisé. Le GPS de notre voiture résout un problème d’optimisation combinatoire lorsqu’il calcule le plus court chemin jusqu’à la destination. Un système de planification de la production détermine la séquence optimale dans laquelle fabriquer les produits et assigne les lots de productions aux différentes machines. Les compagnies de transport utilisent l’optimisation combinatoire pour déterminer quel camion visite quelle client et dans quel ordre tout respectant les délais et en minimisant la consommation de fioul. Les horaires de bus et de train, les tournées de récolte des ordures et distribution de courrier sont développés en utilisant l’optimisation combinatoire, de même que les réseaux de télécommunication et de distribution pour le gaz naturel, l’eau et l’électricité. La production, la distribution, les télécommunications, la gouvernance, la gestion du trafic, la gestion environnementale, les soins de santé, la finance, il est difficile de trouver un aspect de notre économie moderne dont le design, la gestion et le contrôle ne font pas appel pour une part critique à la solution d’un ou plusieurs problèmes d’optimisation combinatoire.
Compte tenu de l’ubiquité des problèmes d’optimisation combinatoire, l’importance du développement de méthodes de résolution efficaces pour ceux-ci ne peut être surestimée. Il existe un spectre assez large de méthodes de résolution de ces problèmes qui vont des algorithmes exacts à une variété d’approches heuristiques. Les méthodes exactes garantissent de terminer avec la solution finale en un temps fini, mais cette garantie a souvent un coût prohibitif en temps calcul. Les méthodes exactes sont donc généralement utilisées pour des problèmes dont la taille est relativement limitée, ou pour obtenir une caractérisation de la structure mathématique d’un problème d’optimisation. A l’autre bout du spectre, les méthodes heuristiques ne garantissent pas de trouver la solution optimale en un temps fini, mais ont plutôt comme but de trouver une bonne solution en un temps relativement court. En d’autres termes, les heuristiques sacrifient la garantie d’optimalité dans le but d’obtenir une bonne solution dans le temps limité imparti.
De nombreux problèmes d’optimisation combinatoire sont encore résolus de manière insatisfaisante à l’heure actuelle et constituent un défi pour les méthodes de résolution actuelle. La puissance de calcul énorme dont nous disposons actuellement rend potentiellement possible la résolution de problèmes impossibles à traiter dans le passé, mais cette puissance seule est rarement suffisante pour compenser la complexité et la taille de beaucoup de problèmes pratiques. Au contraire, la complexité et la taille des problèmes d’optimisation posés par les nouvelles données disponibles requièrent le développement de nouvelles méthodes qui peuvent exploiter efficacement la puissance de calcul disponible. En conséquence, l’étude des problèmes d’optimisation combinatoire et le développement d’algorithmes efficaces pour les résoudre est l'un des domaines de recherche les plus actifs en recherche opérationnelle. Actuellement, seules des instances de taille moyenne peuvent être traitées par des méthodes exactes. Cependant, de nombreux problèmes pratiques sont de très grande taille par nature et se distinguent par des aspects comme des objectifs multiples, des données dynamiques ou stochastiques, qui rendent leur résolution encore plus difficile. Bien que certaines classes d’heuristique sont capables de traiter des problèmes de très grande taille, elles requièrent un temps de développement trop long, et elles produisent des solutions loin d’être optimales.
L’importance stratégique de la recherche opérationnelle et de l’optimisation est illustrée en particulier par la récente «LANCS initiative» qui alloue un fonds de plus de 12 millions de livres, de 2008 à 2013, afin de renforcer ces domaines au sein de quatre universités de Grande-Bretagne.
Objectifs du projet
Les objectifs principaux du projet sont :
₋ Rassembler l’expertise en optimisation combinatoire disponible en Belgique, entre les différents groupes de recherche, et créer un réseau et une masse suffisante pour attirer des scientifiques débutants et expérimentés en Belgique, et par effet levier obtenir plus des financements internationaux.
₋ Former de jeunes chercheurs dans le domaine de l’optimisation combinatoire. Ces profils sont en demande constante, tant dans le milieu universitaire que privé et au niveau mondial.
₋ Développer de nouveaux modèles, techniques algorithmiques et implémentations capables de résoudre des problèmes d’optimisation combinatoire de taille industrielle.
₋ Développer de nouvelles collaborations internationales avec d’autres équipes de grande taille dans le même domaine. Un réseau actif et reconnu en Belgique faciliterait ces collaborations internationales, en particulier dans le cadre de projets internationaux de grande envergure.
Réaliser ces objectifs mènera à (i) un nombre important de contributions majeures en recherche fondamentale dans le domaine, (ii) un impact significatif sur les différents secteurs où l’optimisation combinatoire joue un rôle important et (iii) une valeur ajoutée considérable pour l’économie belge.
Les équipes du projet
Le développement de méthodes efficaces pour la résolution de problèmes d’optimisation combinatoire est un domaine très actif de recherche au niveau mondial. Toutes les équipes participant à ce projet sont très bien positionnées : elles ont une excellent réputation internationale, un excellent historique de publication et sont actives au niveau international, que ce soit au niveau de sociétés (Mathematical Programming Society, EURO – the Association of European Operational Research Societies), ou de l’organisation de conférences internationales. Les partenaires se connaissent bien et sont en contact régulier, par exemple à la conférence annuelle organisée par ORBEL. De plus, les partenaires de la partie francophone du pays collaborent déjà au travers d’un projet subsidié par le FNRS, et organisent une conférence annuelle où les doctorants et les chercheurs post-doc ont l’opportunité de présenter leurs travaux de recherche et de développer leur réseau.
Les équipes participantes suivent une approche commune dans la résolution de problèmes d’optimisation : construire d’abord un modèle mathématique du problème pratique sous-jacent, puis développer un algorithme qui s’applique à toute la classe d’instances décrite par ce modèle. En d’autres mots, ils partagent de manière fondamentale la manière d’aborder ce type de problèmes difficiles, et la collaboration peut dès lors s’effectuer de manière naturelle. Les équipes de recherche sont fortement complémentaires en ce qui concerne leur expertise. Les différentes équipes se distinguent par le type de modèles qu’elles étudient (linéaire ou non-linéaire, continu ou discret, déterministe ou stochastique, objectif unique ou multiple, etc…), par le type de méthodes algorithmiques qu’elles mettent en œuvre pour la résolution de ces problèmes (méthodes exactes ou heuristiques) et par les domaines d’applications de ces modèles (chaîne d’approvisionnement, télécommunications, transport, bio-informatique, etc …)
Directions principales de recherche
Les directions principales de recherche du projet sont les suivantes :
a) Etude et la modélisation de problèmes. Les progrès en optimisation combinatoire se basent sur une modélisation appropriée des problèmes et de l’étude de la structure combinatoire de ces problèmes. La plupart des problèmes en optimisation combinatoire peuvent être modélisés comme des problèmes d’optimisation linéaires en nombres entiers. La formulation peut être améliorée par l’addition de nouvelles inégalités valides, spécifiques au problème. Le choix de l’espace des variables est également important pour obtenir de bonnes formulations. Dans ce contexte, un objectif du projet est de développer de nouvelles classes d’inégalités fortes, et de nouvelles et meilleures formulations étendues pour les applications étudiées.
b) Développement de nouvelles techniques algorithmiques. Des contributions novatrices sont attendues dans la conception d’algorithmes exacts et heuristiques, et en particulier dans la combinaison des ces techniques. En réalité, l’opinion que les avancées substantielles dans le domaine de l’optimisation combinatoire viendront probablement de l’intégration de ces deux approches pour exploiter leurs complémentarités est largement partagée. Une autre direction de recherche prometteuse de recherche est la combinaison de techniques d’intelligence artificielle et d’heuristiques, par exemple l’utilisation d’apprentissage par machine et de règles de décision à l’intérieur d’heuristiques ou d’exploitation de données pour mettre à jour certaines caractéristiques qui influencent le comportement des algorithmes. Les synergies entre les partenaires seront décisives pour ces objectifs. D’autres progrès relatifs à la mise en œuvre des algorithmes exacts seront aussi poursuivis, par exemple, en implémentant de nouvelles approches de décomposition, et des algorithmes heuristiques, par exemple, en développant une méthode générique pour leur design.
c) Implémentation de méthodes de résolution pour des problèmes de très grande taille venant directement d’applications de terrain. Ce sont les applications qui justifient et guident la recherche, et elles nécessitent la résolution de problèmes toujours plus grands et complexes. Inclure plus d’aspects dans un modèle nécessite l’augmentation du nombre de variables et de contraintes et donc de la complexité du problème d’optimisation sous-jacent. Cette complexité est d’autant plus grande s’il y a plusieurs objectifs, si les données du problème changent au cours du temps, ou sont de nature stochastique. Nous visons le l’implémentation des méthodes développées au sein du projet dans des programmes informatiques performants, dans les différents domaines d’application considérés : production, distribution, télécommunications, etc…
Remarque Finale
Pour conclure, COMEX permettra d’améliorer et d’intensifier la collaboration entre les différentes équipes, générera un nombre supplémentaire important de contributions scientifiques novatrices, et permettra de créer le plus grand pôle d’excellence en optimisation combinatoire en Belgique. Il sera également clé pour permettre le développement de nouvelles collaborations internationales et augmenter la visibilité des différentes équipes.
