2025 : 1er prix à la compétition XCSP3 Mini COP Track

Dans la prolongation des travaux de thèse de Pierre Montalbano (ANITI / INRAE) pour mieux pré-traiter les contraintes linéaires au sein du solveur toulbar2 (article publié cette année à ICTAI-2025), ce solveur a participé à une compétition internationale dans le domaine de la programmation par contraintes. Il a remporté le premier prix dans la catégorie des problèmes d’optimisation sous contraintes limités à un sous-ensemble de type de contraintes (représentation des contraintes en extension, en intension, sous forme linéaire, ou comme un problème d’affectation).

Contexte en enjeux

La programmation par contraintes et la recherche opérationnelle sont au cœur de beaucoup de problèmes d’intérêt pour INRAE, notamment pour la biologie des systèmes [Néron et al., 2022 ; Paulevé et al., 2024], la biochimie [Varet et al., 2022] et la génomique [Andonov et al., 2019], pour l’agriculture de précision [Leroux&Vismara, 2021], l’agroécologie [Brulard et al, 2019 ; Vismara et al, 2023] et l’écologie [Justeau-Allaire et al., 2021]. Des compétitions de solvers sont régulièrement organisées dans ces communautés pour évaluer les avancées méthodologiques, le passage à l’échelle des méthodes et leur robustesse sur des jeux de problèmes d’optimisation combinatoire très variés issus du monde académique et industriel. En programmation par contraintes, la compétition XCSP est organisée depuis 2004, avec une ampleur renouvelée en 2017 suite à l’introduction d’un nouveau langage XCSP3 pour décrire les instances à résoudre.

L’axe Optimisation pour les sciences du vivant a développé des compétences sur le sujet de l’optimisation combinatoire dans les modèles graphiques et particulièrement sur un type particulier de modèle graphique, les réseaux de fonctions de coûts [Cooper et al., 2020]. Elle a obtenu d’excellents résultats dans plusieurs projets en collaboration avec des partenaires en biologie et agronomie, en particulier sur le design de protéines [Defresne et al., 2023, Ruffini et al., 2021] (avec TBI/TWB), sur l’inférence de réseaux de régulation de gènes [Pomies et al., 2022 ; Vignes et al., 2010] (avec le LIPME), en génétique [Sanchez et al., 2008 ; Favier et al., 2010] (avec GenPhySE), en génomique [Klopp et al., 2025] (avec Sigenae) et en agroécologie [Akplogan et al., 2013 ; Maqrot et al., 2017] (avec l’unité Écodéveloppement, département ACT Action Transitions et Territoires). Pour chacun de ces projets, des besoins spécifiques ont été soulevés pouvant conduire au développement de nouvelles méthodes. En particulier, en agroécologie, il est nécessaire de pouvoir exprimer des contraintes de capacité sur l’utilisation des ressources. Celles-ci peuvent s’exprimer sous forme de contraintes linéaires qui étaient jusqu’alors mal traitées dans les réseaux de fonctions de coûts. Le travail de thèse de Pierre Montalbano (financement ANITI de 2020 à 2023) a permis de mieux les traiter. Cela a aussi fortement étendu le pouvoir d’expression de ces réseaux, autorisant à modéliser des problèmes très variés comme ceux décrits par le langage XCSP3. Les travaux autour des réseaux de fonctions de coûts sont capitalisés dans le solver C++ toulbar2 développé à INRAE MIAT.

Résultats

Le solver toulbar2 a participé aux compétitions XCSP obtenant plusieurs fois des prix (en 2006, 2008 et depuis 2022). Cette année, il a emporté le premier prix parmi cinq concurrents dans la catégorie « Mini COP » des problèmes d’optimisation sous contraintes limités à un sous-ensemble de type de contraintes dont les contraintes linéaires. En 2025, un article a été présenté à une conférence en intelligence artificielle (ICTAI 2025), finalisant nos dernières avancées méthodologiques sur le traitement des contraintes linéaires.

Perspectives

Des travaux sont en cours pour continuer à augmenter le pouvoir d’expression et les performances du solver toulbar2. En particulier, une thèse a démarré en septembre 2025 (Guidio Sewa, financement ANITI) sur une meilleure prise en compte des contraintes de cardinalité et d’autres contraintes rencontrées dans les problèmes d’ordonnancement et de planification, avec de potentielles applications en agroécologie. Cela devrait aussi améliorer les résultats de toulbar2 dans la catégorie principale « COP ».

Valorisation

Le solver toulbar2 est open-source en licence MIT. Il est utilisé par la start-up Amineo pour le design de protéines.

Références

• https://xcsp.org/competitions
• http://miat.inrae.fr/toulbar2
• https://doi.org/10.48550/arXiv.2509.17706
• Akplogan et al., 2013 : https://doi.org/10.1051/ro/2013032 (RAIRO)
• Andonov et al., 2019 : https://doi.org/10.1142/S0219720019500148 (JBCB)
• Brulard et al., 2019 : https://doi.org/10.1080/00207543.2018.1498985 (IJPR)
• Cooper et al., 2020 : https://doi.org/10.4230/LIPIcs.STACS.2020.4 (STACS 2020)
• Defresne et al., 2023 : https://doi.org/10.24963/ijcai.2023/402 (IJCAI 2023)
• Favier et al., 2010 : https://6login.easychair.org/publications/download/SpJ (WCB 2010)
• Justeau-Allaire et al., 2021 : https://besjournals.onlinelibrary.wiley.com/doi/10.1111/1365-2664.13803 (Applied Ecology)
• Klopp et al., 2025 : https://doi.org/10.1101/2025.04.01.646355 (bioRxiv)
• Leroux et Vismara, 2021 : https://www.wageningenacademic.com/doi/abs/10.3920/978-90-8686-916-9_79 (Precision Agriculture 2021)
• Maqrot et al., 2017 : https://doi.org/10.1007/978-3-319-60045-1_26 (IEA/AIE 2017)
• Néron et al., 2022 : https://doi.org/10.1016/j.cor.2021.105584 (COR)
• Paulevé et al., 2024 : https://zenodo.org/records/10361533 (AAAI 2024)
• Pomies et al., 2022 : https://doi.org/10.1093/bioinformatics/btac445 (Bioinformatics)
• Ruffini et al., 2021 : https://doi.org/10.3390/a14060168 (Algorithms)
• Sanchez et al., 2008 : https://doi.org/10.1007/s10601-007-9029-5 (Constraints)
• Varet et al., 2022 : https://doi.org/10.1021/acs.jcim.2c00353 (JCIM)
• Vismara et al., 2023 : https://hal.umontpellier.fr/hal-04208954/document (IJCAI 2023)