Stage (F/H) - Optimisation Combinatoire Boîte-grise Pour Des Problèmes Pseudo-booléens

**Type de contrat**: Stage

**Niveau de diplôme exigé**: Bac + 4 ou équivalent

**Fonction**: Stagiaire de la recherche

**A propos du centre ou de la direction fonctionnelle**:
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).

**Mission confiée**:
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.

**Principales activités**:
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 po