PAI "Combinatorial Optimization: Metaheuristics and Exact methods"

A la croisée des mathématiques, de l'informatique et de l'économie, l'optimisation combinatoire a pour objectif de formaliser de manière mathématique et de résoudre des problèmes en choisissant une solution parmi une multitude d'options. Pour corser le tout, en général, le nombre d'options est trop grand permettre de les examiner une à une. Les applications sont nombreuses: dans le transport - quel est l'itinéraire optimal d'une tournée de camions en prenant en compte la charge, les livraisons, le trajet, le trafic… -; les télécommunications - où placer les câbles pour que le coût soit le plus petit et que le réseau soit fiable ? - ; etc.

Il existe deux manières de résoudre ces problèmes complexes: les méthodes exactes ou les méthodes métaheuristiques. Comme son nom l'indique, une méthode exacte vise à donner la meilleure solution, prouvée par algorithme mathématique. Mais cette approche a une limite: elle demande d'immenses capacités de calcul, donc du temps et s'avère finalement peu adaptée aux besoins industriels. La seconde approche, métaheuristique, en revanche est plus rapide, donc plus adaptée à l'entreprise mais si elle apporte une bonne solution, rien ne dit que c'est la meilleure solution.

L'objectif de ce PAI est de développer ces deux approches et surtout réussir à les croiser pour garder le meilleur de chacune et arriver à terme à trouver rapidement la meilleure solution à un problème complexe, à multivariables. Pour assurer cette « fertilisation croisée », les chercheurs vont travailler sur des problèmes identiques et comparer leurs résultats et approches. Le PAI permettra aussi de faciliter les échanges via notamment des workshops, des co-tutelles de thèses ou une université d 'été pour doctorants.

Coordinateur du PAI, l'ULB possède des compétences à la fois en méthodes exactes - avec le service Graphs and Mathematical Optimization, Bernard Fortz (coordinateur du pôle), Faculté des Sciences - et métaheuristiques - avec IRIDIA, Thomas Stützle, Ecole polytechnique de Bruxelles -.

Le réseau est composé d'équipes de l'ULB; de l'ULg; de la KULeuven; de l'UHasselt; de l'Université d'Anvers; de l'UCLouvain; de l'University of Maastricht (NL); de l'Université de Montréal (CA).

Site web

Bernard FORTZ

Faculté des Sciences

tel 02 650 3095, fax 02 650 5609,

Campus de la Plaine

ULB CP210/01, boulevard du Triomphe, 1050 Bruxelles