Stage F/H - Optimisation combinatoire boîte-grise pour des problèmes pseudo-booléens

Le centre Inria de l'Université de Lille, créé en 2008, emploie 360 personnes dont 305 scientifiques répartis dans 15 équipes de recherche. Reconnu pour sa forte implication dans le développement socio-économique de la région des Hauts-De-France, le centre Inria de l'Université de Lille entretient des relations étroites avec les grandes entreprises et les PME. En favorisant les synergies entre chercheurs et industriels, Inria participe au transfert de compétences et d'expertise dans le domaine des technologies numériques et donne accès au meilleur de la recherche européenne et internationale au bénéfice de l'innovation et des entreprises, notamment dans la région.

Depuis plus de 10 ans, le centre Inria de l'Université de Lille est situé au cœur de l'écosystème universitaire et scientifique lillois, ainsi qu'au cœur de la Frenchtech, avec un showroom technologique basé avenue de Bretagne à Lille, sur le site d'excellence économique EuraTechnologies dédié aux technologies de l'information et de la communication (TIC).

Ce projet de recherche porte sur la conception d’algorithmes d’optimisation combinatoire de type boîte-grise (« graybox »). L’optimisation boîte-grise fait référence à des techniques qui tirent parti des connaissances disponibles a priori sur le problème d’optimisation. C’est le cas de nombreux problèmes théoriques fondamentaux en optimisation combinatoire, tels que le Problème du Voyageur de Commerce (TSP), les paysages NK, ou le Problème d’Affection Quadratique (QAP). Les informations structurelles sous-jacentes à la formulation de ces problèmes sont extrêmement importantes pour développer des heuristiques stochastiques bas-niveau efficaces, ainsi que des opérateurs de recherche permettant de générer de nouvelles solutions candidates de très bonne qualité. Le succès de ces opérateurs et algorithmes réside dans leur capacité à effectuer une exploration informée, et non aveugle, d’un espace de solutions candidates très grand, de manière efficace.

Cependant, de nombreux défis doivent être relevés lorsqu’il s’agit de résoudre des instances particulières présentant des caractéristiques spécifiques. Dans ce projet, nous cherchons à faire progresser le développement de nouveaux algorithmes d’optimisation combinatoire boîte-grise en nous concentrant sur la classe des problèmes d’optimisation pseudo-booléens, et plus particulièrement sur la classe des fonctions k-bornées, c’est à dire la classe des fonctions qui peuvent être décomposées en une somme linéaire de sous-fonctions, chacune ne dépendant que de k variables binaires. Pour ces types de problèmes combinatoires, nous nous intéressons à deux questions de recherche.

• Étude de la relation entre l’espace de conception des algorithmes heuristiques et le paysage des problèmes pseudo-booléens. Il est bien connu que tout problème d’optimisation pseudo-booléen (non contraint) peut être décomposé (dans l’espace de Hilbert des fonctions pseudo-booléennes) en utilisant la transformée de Walsh-Hadamard, qui peut être vue comme une transformée de Fourier discrète. Ainsi, le « paysage » d’une instance de problème d’optimisation pseudo-booléen peut être exploré sous l’angle de cette transformée. Nous proposons ici d’étudier de manière systématique et approfondie la relation entre le paysage d’une instance donnée de problème pseudo-booléen, la transformée de cette instance, et l’espace de conception des algorithmes, en nous concentrant en particulier sur les derniers opérateurs de recherche boîte-grise proposés dans la littérature. L’objectif principal est d’acquérir une compréhension plus fondamentale de ce qui rend une instance difficile à résoudre pour un algorithme donné, et, à terme, d’améliorer notre capacité à établir une correspondance entre les performances des algorithmes et les caractéristiques de la transformée.
• Généralisation à des problèmes d’optimisation multi-objectifs. Nous proposons d’exploiter les algorithmes et les techniques d’analyse d’optimisation boîte-grise dans le domaine de l’optimisation multi-objectif. Plus précisément, nous envisageons non pas une seule, mais plusieurs fonctions objectifs pseudo-booléennes boîte-grise à optimiser. Bien que chaque fonction objectif puisse être abordée séparément, nous souhaitons ici résoudre les différentes fonctions objectifs simultanément ; ceci afin d’obtenir un ensemble complet de solutions offrant différents compromis. De plus, bien que l’on puisse trouver divers algorithmes multi-objectifs dans la littérature spécialisée, très peu ont pris en compte l’intégration de composants boîte-grise dédiées. À cet égard, nous visons à faire progresser les approches existantes en considérant une combinaison et une intégration intelligente des techniques boîte-grise existantes, et en tirant parti des résultats obtenus grâce aux investigations mentionnées dans le paragraphe précédent.

Ce stage est de nature fondamentale. Sur le plan théorique, il implique des considérations liées à l’optimisation combinatoire, à la transformée discrète de Walsh-Hadamard et à l’analyse de l’espace des instances. Sur le plan empirique, il consiste à analyser des composants algorithmiques avancés à travers des expérimentations approfondies, conduisant éventuellement à la conception de nouveaux algorithmes et méthodologies de recherche heuristique à usage général. Ces deux niveaux seront menés simultanément, suivant le plan de travail esquissé ci-dessous. Il convient de noter que ce plan de travail sera continuellement ajusté de façon agile et en fonction des résultats théoriques et empiriques obtenus tout au long du stage.

• Premier mois :
  • Revue de la littérature sur les aspects théoriques liés aux techniques combinatoires boîte-grise pour les domaines pseudo-booléens
  • Implémentation et expérimentation des techniques les plus récentes existantes
• Deuxième mois :
  • Revue de la littérature sur les aspects théoriques liés à la transformée discrète de Walsh-Hadamard
  • Définition des benchmarks, génération d’instances et analyse empirique
• Troisième mois :
  • Revue de la littérature sur les algorithmes heuristiques multi-objectifs
  • Adaptation des techniques mono-objectifs au cadre multi-objectif et analyse expérimentale
• Quatrième mois :
  • Synthèse et analyse finale
  • Préparation du rapport de stage

• connaissances en informatique et/ou en mathématiques appliquées, notamment
• connaissances en optimization, algorithmie, programmation, analyse expérimentale
• capacités de lecture et d'analyse d'articles scientifiques et de recherche

• Restauration subventionnée
• Transports publics remboursés partiellement
• Congés: le nombre de jours de congés dépend du nombre de jours de présence effective du stagiaire au sein du centre
• Équipements professionnels à disposition (visioconférence, prêts de matériels informatiques, etc.

4.35 € brut horaire