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

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 151-172.
1. D. Allouche, C. Bessiere , P. Boizumault , S. de Givry , P. Gutierrez , S. Loudni, JP. Metivier, T. Schiex. Filtering Decomposable Global Cost Functions. Proc. AAAI, 2012.
2. D. Allouche, A. Favier, S. de Givry, T. Schiex, M. Zytnicki, M. Fontaine, JP. Métivier, M. Sanchez, KL Leung. Combining exact WCSP techniques and VNS serach for solving MPE. Presentation invitee à UAI’2012, Los Angeles, USA (presentation du “PIC challenge).
1. M.C. Cooper and S. Zivny, Tractable Triangles and Cross-Free in Discrete Optimisation, JAIR, 2012. Volume 44, pages 445-490.
2. Traoré, Seydou ; Allouche, David ; André, Isabelle ; de Givry, Simon ; Katsirelos, George; Schiex, Thomas et Barbe, Sophie. A New Framework for Computational Protein Design through Cost Function Network Optimization. Bioinformatics, 2013.
3. Mathieu Fontaine, Samir Loudni et Patrice Boizumault. Exploiting Tree Decomposition for Guiding Neighborhoods Exploration for VNS. RAIRO - Operations Research / Volume 47 / Issue 02 / April 2013.
5. Mining (Soft-) Skypatterns using Constraint Programming
W. Ugarte, P. Boizumault, S. Loudni, B. Crémilleux, A. Lepailleur
Soumis à Advances in Knowledge Discovery and Management Vol. 5 (AKDM-5).
3. David Allouche, Seydou Traoré, Isabelle André, Simon de Givry, George Katsirelos, Sophie Barbe, T Schiex.
Computational Protein Design as a Cost Function Network Optimization Problem. Proc. of CP2012, Quebec city, Canada.

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.