Stage F/H - Optimisation combinatoire boîte-grise pour des problèmes pseudo-booléens
Contract type : Internship
Level of qualifications required : Master's or equivalent
Fonction : Internship Research
About the research centre or Inria department
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).
Assignment
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.
Main activities
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
Skills
- 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
Benefits package
- 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.
Remuneration
4.35 € brut horaire
General Information
- Theme/Domain :
Optimization, machine learning and statistical methods
Scientific computing (BAP E) - Town/city : Villeneuve d'Ascq
- Inria Center : Centre Inria de l'Université de Lille
- Starting date : 2025-04-01
- Duration of contract : 4 months
- Deadline to apply : 2025-02-22
Warning : you must enter your e-mail address in order to save your application to Inria. Applications must be submitted online on the Inria website. Processing of applications sent from other channels is not guaranteed.
Instruction to apply
Defence Security :
This position is likely to be situated in a restricted area (ZRR), as defined in Decree No. 2011-1425 relating to the protection of national scientific and technical potential (PPST).Authorisation to enter an area is granted by the director of the unit, following a favourable Ministerial decision, as defined in the decree of 3 July 2012 relating to the PPST. An unfavourable Ministerial decision in respect of a position situated in a ZRR would result in the cancellation of the appointment.
Recruitment Policy :
As part of its diversity policy, all Inria positions are accessible to people with disabilities.
Contacts
- Inria Team : BONUS
-
Recruiter :
Derbel Bilel / Bilel.Derbel@inria.fr
About Inria
Inria is the French national research institute dedicated to digital science and technology. It employs 2,600 people. Its 200 agile project teams, generally run jointly with academic partners, include more than 3,500 scientists and engineers working to meet the challenges of digital technology, often at the interface with other disciplines. The Institute also employs numerous talents in over forty different professions. 900 research support staff contribute to the preparation and development of scientific and entrepreneurial projects that have a worldwide impact.