PAI Combinatorial Optimization

Face à des choix complexes, nos machines modernes ont besoin de méthodes de calcul performantes. A la croisée des mathématiques, de l'informatique et de l'économie, le projet de recherche PAI "Combinatorial Optimization: Metaheuristics and Exact methods" s'intéresse à l'optimisation combinatoire.

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.

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 la puissance de calcul disponible.

Coordonné par l'ULB (Bernard Fortz, UR Graphes et optimisation mathématique, Faculté des Sciences), ce projet a pour but de combiner les avantages de deux méthodes de calculs (méthodes exactes ou méthodes métaheuristiques), avec des débouchés concernant des secteurs multiples comme ceux des transports, des télécommunications, de l'économie etc.

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 dans le même domaine.

A découvrir dans la vidéo "Images de Sciences".


Nouvelle molécule dans le domaine de la catalyse

Une étroite collaboration entre le Massachusetts Institute of Technology (MIT) et l'ULB a permis le développement d'une nouvelle famille de molécules qui s'avère prometteuse dans le domaine de la catalyse.

Les groupes du Professeur R. R. Schrock (Prix Nobel de Chimie en 2005 et récipiendaire de la Chaire internationale Solvay de Chimie en 2014) et des Professeurs I. Jabin (Laboratoire de Chimie Organique, LCO, ULB) et G. Evano (LCO, ULB) ont préparé et caractérisé une molécule dont la structure tridimensionnelle est inspirée des sites catalytiques de métalloprotéines. Cette molécule, nommée Calix[6]AzaCryptand (CAC, en bleu sur l'image), est capable d'enfouir un ion métallique (en jaune sur l'image) comme le molybdène, le zinc ou le cuivre au sein d'une cavité qui reste cependant ouverte vers le milieu extérieur. L'ion métallique, ainsi protégé, n'est alors accessible qu'aux seules molécules pouvant pénétrer dans la cavité du CAC. Ce design moléculaire original permet d'envisager la mise au point de systèmes catalytiques efficaces dans des domaines où les enjeux sociétaux sont importants (production d'énergie notamment). C'est vers de telles applications que les travaux sont maintenant dirigés au sein des deux équipes.

L'équipe de l'ULB a synthétisé la molécule CAC en utilisant un calixarène, une famille de composés possédant une structure 3D concave et dont l'étude est l'un des axes de recherche principaux du LCO. La capacité du CAC à complexer un ion métallique a ensuite été démontrée par spectroscopie de Résonnance Magnétique Nucléaire (RMN) à l'ULB et par diffraction des rayons X au MIT. Les travaux ont été en grande partie effectués dans le cadre de la thèse de Sara Zahim (doctorante FRIA au LCO) et ont été publiés dans Organic Letters, le meilleur journal de communications en Chimie Organique.

A Calix[6]azacryptand Ligand with a Sterically Protected Tren-based Coordination Site for Metal Ions. S. Zahim, L. A. Wickramasinghe, G. Evano, I. Jabin,* R. R. Schrock,* P. Müller Org. Lett., 2016, 18, 1570-1573.


Mapathon: Succès inédit

Le Mapathon vient d'avoir lieu samedi sur les campus des universités belges et les organisateurs - les départements de géographie de ces universités, soutenus par les volontaires d'OpenStreetMap - affichent un grand sourire: l'opération de cartographie collective a mobilisé plus de 200 volontaires, étudiants, chercheurs, professeurs et citoyens de tous âges et tous horizons.

Les participants se sont concentrés sur la cartographie de deux régions d'Afrique.

D'abord, le Sud-Kivu sur l'île d'Idwji en RDC où sévit actuellement une épidémie de rougeole. Médecins Sans Frontières doit rapidement vacciner la population; mais faute de cartes détaillées de l'île, ils ne pouvaient pas localiser la population avec la précision nécessaire. Samedi matin, les volontaires du Mapathon ont donc cartographié quelque 23.244 bâtiments sur l'île; les cartographes expérimentés ont ensuite validé leur travail. Muni de ces informations, MSF a pu commencer les visites de vaccination dès cette semaine.

Autre pays cartographié ce samedi, notamment à l'ULB: le Swaziland où le Global Health Group de l'Université de Californie soutient le gouvernement dans son programme d'éradication de la malaria. Cette cartographie se poursuit: si vous souhaitez y participer, vous pouvez vous inscrire ici.


Niveau marin : les points d'ancrages comptent !

Le niveau marin a augmenté de +/- 20 cm depuis 1900, augmentation dont un tiers est attribué actuellement aux calottes de glace en Antarctique et au Groenland. En Antarctique, la fragilisation des plateformes de glace flottante, retenant la glace posée sur le continent en amont, accélère la perte de glace.

Ces plateformes sont stabilisées par leur contact avec socle rocheux environnant, notamment par de nombreux petits "points d'ancrage". Dans un article publié dans le Journal of Glaciology, Sophie Berger et ses collègues du laboratoire de Glaciologie (Faculté des Sciences) démontrent que ces petits points d'ancrage ont un effet considérable sur la stabilité des plateformes de glace. L'équipe a étudié une structure similaire située à proximité de la station antarctique Princesse Elisabeth. En associant des données historiques des années 1960 et des observations satellitaires de haute résolution, les chercheurs ont montré que la glace se déplace très lentement sur le point d'ancrage (0,5 m/an), comparé au déplacement de la partie flottante 5 km plus à l'est (>250 m/an). Ils ont ensuite démontré que, lorsque les observations ignorent le point d'ancrage, les propriétés de la glace fournies par modélisationsont erronées.

La petite dimension de ces points d'ancrage les rend particulièrement vulnérables au réchauffement océanique : c'est donc un paramètre dont il faudra tenir compte dans les modèles futurs.

The control of an uncharted pinning point on the flow of an Antarctic ice shelf
Berger, Sophie; Favier, Lionel ; Drews, Reinhard ; Derwael, Jean-Jacques; Pattyn, Frank - Journal of Glaciology


Régulation de la chaleur chez la fourmi argentée

La fourmi argentée Cataglyphis bombycina vit dans les déserts torrides du Sahara et de la péninsule arabique. Les ouvrières quittent le nid à la recherche de nourriture aux heures les plus chaudes de la journée, lorsque la température moyenne de l'air atteint 50°C et celle du sol 70°C. De telles conditions sont hostiles pour toute forme de vie. Une étude réalisée par Quentin Willot et Serge Aron du service Evolution biologique et Ecologie (Faculté des Sciences), en collaboration avec l'Université de Namur, a permis de mettre en évidence certains des mécanismes adaptatifs permettant aux fourmis de résister à de telles contraintes de température.

En combinant des analyses en microscopie électronique, en physique optique et en dynamique de réchauffement, leurs travaux montrent que les fourmis sont couvertes de poils dont la section est de forme triangulaire. Ces poils sont séparés de la cuticule des fourmis par une fine couche d'air. Chaque poil fonctionne alors comme un prisme triangulaire qui renvoie les rayons solaires selon un phénomène optique appelé « réflexion totale interne ». Après être entrée dans un poil, la lumière est réfléchie sur la face basale du poil de sorte que l'énergie du rayonnement solaire n'atteint pas l'insecte. Il s'agit du même phénomène optique que celui piégeant la lumière dans une fibre optique, largement utilisée dans nos télécommunications modernes.

Ce phénomène physique crée un effet miroir, à l'origine de la couleur argentée caractéristique de cette espèce de fourmis. Simultanément, il permet de limiter considérablement la surchauffe des individus exposés aux températures extrêmes de leur milieu. Pour en arriver à ces conclusions, les auteurs ont comparés la lumière réfléchie etla vitesse de réchauffement de fourmis avec poils et de fourmis sans poils (rasées). Les résultats montrent que les individus contrôles (avec poils) renvoient dix fois plus de lumière que les individus glabres. Parallèlement, l'introduction d'une microsonde dans le rectum des fourmis révèle que les individus poilus économisent un gain de température de l'ordre de 2°C lorsqu'ils sont exposés à la lumière émise par le soleil du Sahara.

Il s'agit de la première démonstration d'un processus de réflexion totale interne dans la coloration d'un animal, et d'une protection contre le rayonnement solaire de son habitat naturel. Les résultats de cette étude sont détaillés dans la revue PLOS ONE.

Willot Q, Simonis P, Vigneron J-P, Aron S (2016) Total Internal Reflection Accounts for the Bright Color of the Saharan Silver Ant. PLoS ONE 11 (4): e0152325. doi:10.1371/journal.pone.0152325.

 

Clin d'oeil

A vos agendas !

  • Les activités de l'Expérimentarium de Physique