Flash Info
Dans le contexte exceptionnel lié à l’épidémie de Covid-19, l’ANR adapte le calendrier de ses appels à projets. Lire la suite
Blanc SIMI 2 - Sciences de l'information, de la matière et de l'ingénierie : Sciences de l’information, simulation

Filtrage par cohérences locales fortes pour les réseaux de fonctions de coûts et autres modèles graphiques – FICOLOFO

Programmation par fonctions de coûts

Ce projet étend la programmation par contraintes en direction de l'optimisation en introduisant la programmation par fonctions de coûts. <br />Nous équipons notre outil de résolution de réseaux de fonctions de coûts de nouveaux algorithmes de filtrage plus puissants, permettant le filtrage de fonctions de coûts globales et le rendons plus facile d'accès via une interface Python/NumberJack. Différentes applications (nurse rostering, design de protéines, allocations de cultures) en profite déjà.

Améliorer la facilité de modélisation et de résolution en optimisation combinatoire (non linéaire)

En améliorant les algorithmes, en permettant l'expression et le traitement de fonctions de coûts globales, en permettant leur expression dans un langage plus évolué, le projet essaie d'apporter une réponse à des problèmes d'optimisation combinatoires non-linéaires variés et difficiles. Les réponses apportées dans le projet sur des problèmes d'optimisation difficiles et la comparaison avec des méthodes éprouvées (PLNE/Cplex...) sont déjà convaincantes.

Les méthodes de résolution des réseaux de fonctions de coûts s'appuient sur des algorithmes de filtrage ou cohérence locale proche de ceux de la programmation par contraintes mais manipulant des coûts au travers de transformation de problèmes préservant l'équivalence. Ces outils algorithmiques ont été étendus à plusieurs fonctions de coût globales dans le cadre du projet.

De nouvelles méthodes de filtrage, plus puissantes, plus efficaces. De nouvelles fonctions de coûts globales, capables de représenter des problèmes d'optimisation complexe. Ces résultats ont permis de modéliser et de résoudre des problèmes de gestion d'infirmières (nurse rostering), d'allocation de cultures ou de conception de protéines avec des efficacités qui peuvent parfois largement dépasser l'efficacité d'outils industriel existants (en programmation linéaire en nombres entiers).

Continuer à progresser, à améliorer l'algorithmique des Réseaux de fonction de coût, offrir des fonctions de coûts globales additionnelles et une manière plus simple et plus pratique de modéliser les problèmes que notre format WCSP courant.

1. Mahuna Akplogan, Simon de Givry, Jean-Philippe Métivier, Gauthier Quesnel, Alexandre Joannon and Frédérick Garcia. Solving the Crop Allocation Problem using Hard and Soft Constraints. RAIRO - Operations Research / Volume 47 / Issue 02 / April 2013, pp

De nombreux problèmes d'optimisation combinatoire s'expriment naturellement sous la forme d'un réseau d'interactions entre variables discrètes. Dans les cas les plus simples, ces interactions locales sont des relations de compatibilités/incompatibilités et le réseau est un réseau de contraintes (constraint network). Une propriété fondamentale d'un tel réseau est sa cohérence : est-il possible de trouver une valeur pour chaque variable sans qu'aucune incompatibilité n'apparaisse ? Répondre à cette question définit le "problème de satisfaction de contraintes" (ou CSP, Constraint Satisfaction Problem).

Ce problème a fait l'objet d'intenses recherches dans les 30 dernières années et la communauté française est très active au niveau international. Les algorithmes développés dans ce cadre forment le coeur des outils de programmation par contraintes tels qu'IBM ILOG Solver, Cisco Eclipse... Ces outils offrent une bonne complémentarité avec les techniques de programmation mathématique dans les domaines de l'allocation de ressources, configuration... De nombreux problèmes combinatoires rde taille industrielle ont ainsi été résolus.

La technique de traitement mobilisée de façon universelle dans les outils de résolutions (solvers) est le filtrage par cohérence locale. Il consiste à transformer (en temps polynomial en général) un réseau de contrainte initial en un autre réseau équivalent (même ensemble de solutions) et plus "explicite" (ceci étant caractérisé formellement). La propriété la plus usitée est la "cohérence d'arc" (avec un filtrage local réalisé au niveau d'une contrainte).

Depuis 2000, ces techniques de filtrage ont été étendues aux réseaux de fonctions de coûts (ou Weighted Constraint Network). Ces réseaux, qui généralisent réseaux de contraintes, permettent de capturer des problèmes d'optimisation complexes mixant contraintes et fonctions de coûts arbitraires (non linéaires). Dans les dernières années, les avancées dans ce domaine ont été intégrées dans des algorithmes de type "Branch and Bound" où elles fournissent un minorant non naïf et incrémental. Cette approche a été sophistiquée et a permis de clore des problèmes d'optimsation ouverts depuis plus de 15 ans, de traiter des problèmes de grande taille en bioinformatique (génétique, biologie moléculaire) ou des modèles graphiques stochastiques discrets (réseaux bayésiens...).

Ce projet est une étape essentielle dans le processus d'extension de la Programmation par Contraintes vers l'optimisation de fonctions de coûts. Pour cela, nous nous appuierons sur l'ensemble des résultats accumulés dans le domaine des réseaux de contraintes autour des cohérences de domaine (domain consistencies) et des contraintes globales (contraintes dont la sémantique spécifique permet le développement d'algorithmes de filtrage très efficaces). Cela demandera d'étendre le résultat sur la cohérence d'arc établi en 2000 à des niveaux de cohérence plus élévés et en tenant compte de la sémantique particulière de "fonction de coût globales". Pour guider ces développements, nous nous appuierons ssur l'ensemble des problèmes collectés depuis plusieurs années dans la "Cost Function Library" complétés par différentes application cibles : diagnostic de pedigrees complexes et haplotypage de vraisemblance maximum (en génétique), problème de gestion d'infirmière (Nurse Rostering) et traitement de modèles graphiques stochastiques issus des problèmes en génétique et d'un problème de cartographie d'espèces invasives. Au delà de seuls problèmes d'optimisation, nous essaierons également d'appliquer cces techniques au problème de calcul approximatif avec garantie de la constante de normalisation (Z) dans ces modèles, un problème difficile (#P-complet) mais central dans le traitement de champs markoviens et et de façon générale en raisonnement dans l'incertain.

Coordinateur du projet

Monsieur Thomas Schiex (INRA -CENTRE DE RECHERCHE DE TOULOUSE)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

GREYC UNIVERSITE DE CAEN - BASSE-NORMANDIE
UBIA (INRA) INRA -CENTRE DE RECHERCHE DE TOULOUSE
LIRMM (CNRS) CNRS - DELEGATION REGIONALE LANGUEDOC-ROUSSILLON

Aide de l'ANR 348 330 euros
Début et durée du projet scientifique : - 42 Mois

Liens utiles