Stage M2 ou étudiant année de césure grande école - Nouvelles heuristiques d'optimisation à voisinage étendu : une approche hybride inspirée de la physique

Retour à la liste des résultats

Présentation INRAE

L’Institut national de recherche pour l’agriculture, l’alimentation et l’environnement (INRAE) est un établissement public de recherche rassemblant une communauté de travail de 12 000 personnes, avec 272 unités de recherche, de service et expérimentales, implantées dans 18 centres sur toute la France. INRAE se positionne parmi les tout premiers leaders mondiaux en sciences agricoles et alimentaires, en sciences du végétal et de l’animal. Ses recherches visent à construire des solutions pour des agricultures multi-performantes, une alimentation de qualité et une gestion durable des ressources et des écosystèmes.

Le stage se déroulera au sein de l'unité MIAT où l'agent pourra avoir une interaction continue et enrichissante avec les membres de notre unité de recherche.

Environnement de travail, missions et activités

Les méthodes de recherche locale, telles que la Large Neighborhood Search (LNS) [8] et la Variable Neighborhood Search (VNS), sont des techniques bien connues dans le domaine des contraintes "valuées" ainsi qu’en recherche opérationnelle. Ces approches visent à optimiser partiellement un problème en sélectionnant différents sous-ensembles de variables selon diverses heuristiques, afin de dépasser les limites des recherches complètes. Elles ont été appliquées dans des domaines variés, notamment le design de protéines, l’allocation de fréquences et la planification de tournées de véhicules.
Sur des problèmes difficiles, elles permettent souvent d’obtenir la meilleure solution possible, ou au moins une solution de meilleure qualité que celles fournies par les méthodes complètes. Des travaux antérieurs ont permis de restaurer la preuve de complétude [7]. Pour des instances difficiles de design de protéines, des heuristiques de sélection de variables, basées sur l’exploitation d’informations relatives à leur position 3D, ont également été implémentées afin d’améliorer la résolution [2]. Cette idée est sans doute généralisable à tout problème combinatoire dont le modèle physique et les fonctions de coût associées reposent en tout ou partie sur des informations euclidiennes.
Le but du stage est d’explorer le lien entre le modèle physique et le modèle topologique du graphe de contraintes [6], afin d’accroître l’efficacité de ces méthodes. Concrètement, il s’agira de concevoir et d’explorer de nouvelles heuristiques de choix de voisinage, inspirées à la fois par la physique du problème [1], [3] et par la topologie du graphe de contraintes qui en résulte. Selon les résultats obtenus, l’exploitation de méthodes d’apprentissage automatique [4] pourra également être envisagée. Après une phase de familiarisation avec les méthodes VNS et LNS ainsi qu’un approfondissement bibliographique récent, l’objectif sera d’implémenter de nouvelles heuristiques dans le solveur ToulBar2. Ces heuristiques seront ensuite évaluées en termes d’efficacité par rapport à l’état de l’art actuel, en intégrant notamment :
l’exploitation de la topologie du graphe, des heuristiques issues de modèles physiques appliqués au repliement de protéines, l’apprentissage pour le choix des voisinages.

REMARQUE: Le solveur ToulBar2, dans lequel seront réalisés les développements, est une plateforme open-source en C++ de référence pour la résolution de problèmes combinatoires modélisés par des réseaux de fonctions de coût. Il s’est distingué à plusieurs reprises dans des compétitions internationales majeures, notamment : Max-CSP 2008 et UAI 2008, 2010, 2014, 2022 (inférence probabiliste et satisfaction), XCSP3 Compétitions 2022, 2023 ,2024 et lauréat 2025 (problèmes de satisfaction de contraintes). Cette reconnaissance internationale garantit un cadre de travail à la pointe de la recherche en optimisation combinatoire.

[1]          David Allouche. Computation Protein Design instances with small tree-width: selection based on coarse approximated 3D average position volume. 2019. arXiv: 1909.01803 [cs.CE]. Url: https://arxiv.org/abs/1909. 01803.

[2]          Antoine Charpentier et al. “Variable neighborhood search with cost func-tion networks to solve large computational protein design problems”. In: Journal of chemical information and modeling 59.1 (2018), pp. 127–136.

[3]          Jean Durup. “On Levinthal paradox and the theory of protein folding”. In: Journal of Molecular Structure: THEOCHEM 424.1 (1998). A Faithful Couple: Qualitative and Quantitative Understanding of Chemistry, pp. 157–169. ISSN: 0166-1280. doi: https://doi.org/10.1016/S0166-1280(97) 00238- 8. Url: https://www.sciencedirect.com/science/article/pii/S0166128097002388.

[4]          Shengyu Feng, Zhiqing Sun, and Yiming Yang. SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs. 2025. arXiv: 2508.16171 [cs.LG].

[5]          Mathieu Fontaine. “Apport de la décomposition arborescente pour les méth-odes de type VNS”. Theses. Université de Caen, July 2013. Url: https: //theses.hal.science/tel-01025435.

[6]          Nicolas Levasseur, Patrice Boizumault, and Samir Loudni. “Heuristiques de choix de voisinage pour les recherches à voisinage variable dans les WCSP”. In: JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes. Ed. by Gilles Trombettoni. LINA - Université de Nantes -École des Mines de Nantes. Nantes, France, June 2008, pp. 247–256. Url: https://inria.hal.science/inria-00292651.

[7]          Abdelkader Ouali et al. “Iterative Decomposition Guided Variable Neigh-borhood Search for Graphical Model Energy Minimization”. In: Conference on Uncertainty in Artificial Intelligence (UAI’17). AUI 2017 Proceedings. Sydney, Australia, Aug. 2017, 10 p. url: https://hal.inrae.fr/hal-02733961.

[8]          David Pisinger and Stefan Ropke. “Large Neighborhood Search”. In: Hand-book of Metaheuristics. Ed. by Michel Gendreau and Jean-Yves Potvin. Cham: Springer International Publishing, 2019, pp. 99–127. isbn: 978-3-319-91086-4. doi: 10.1007/978-3-319-91086-4_4. Url: https://doi. org/10.1007/978-3-319-91086-4_4.

Formations et compétences recherchées

•    Bonne maîtrise du langage C++ pour l’implémentation dans le solveur Toul-Bar2.
•    Connaissances en probabilités et en modélisation stochastique.
•    Intérêt marqué pour les méthodes d’optimisation et la programmation par contraintes.
•    Capacités d’analyse et de comparaison expérimentale (benchmarks, évaluation empirique).
•    Curiosité scientifique et autonomie.
 

Votre qualité de vie à INRAE

En rejoignant INRAE, vous bénéficiez (selon le type de contrat et sa durée) :

-  jusqu'à 30 jours de congés + 15 RTT par an (pour un temps plein)
- d'un soutien à la parentalité : CESU garde d'enfants, prestations pour les loisirs ;
- de dispositifs de développement des compétences : formation, conseil en orientation professionnelle ;
- d'un accompagnement social : conseil et écoute, aides et prêts sociaux ;
- de prestations vacances et loisirs : chèque-vacances, hébergements à tarif préférentiel ;
- d'activités sportives et culturelles ;
- d'une restauration collective.

Modalités pour postuler

J'envoie mon CV et ma lettre de motivation