Linear constraint and conflict-free learning for graphical models

Les Modèles Graphiques (GM) utilisent des graphes pour encoder les relations complexes entre les variables de décision : les noeuds représentent des variables et les (hyper)arêtes représentent des dépendances ou des corrélations entre les variables. Les GM offre un cadre flexible pour modéliser différents systèmes. Par exemple, les Réseaux de Fonction de Coût (CFN) sont des modèles graphiques non orientés impliquant des fonctions de coût locales. La tâche visant à trouver l'affectation minimisant la somme de toutes les fonctions de coût locales est connue sous le nom de Problème de Satisfaction de Contraintes Pondérées (WCSP). Ce problème se pose dans divers domaines tels que l'analyse d'images ou la bioinformatique.,La résolution de WCSP repose sur une recherche arborescente et la propagation de contraintes., Dans cette présentation, je montrerai une manière d'intégrer les contraintes linéaires dans un CFN, c'est à dire, d'une part comment les représenter sans introduire un nombre exponentiel d'éléments et d'autre part comment les propager. Ce travail a permis d'élargir le champ des problèmes modélisables et résolubles par un solveur WCSP.,Ensuite, guidés par le succès des méthodes d'apprentissage basées sur les conflits dans plusieurs domaines (comme SAT, l'optimisation pseudo-booléenne ou ILP), je parlerai d'un mécanisme d'apprentissage sans conflit. Il vise à mémoriser à travers une contrainte linéaire les bornes inférieures des sous-problèmes rencontrés, si ce sous-problème apparaît une deuxième fois dans la recherche, alors propager la contrainte précédemment apprise aidera à obtenir une bonne borne inférieure. Ce mécanisme est basé sur 3 éléments: la reparametrisation du problème,  la génération de contraintes linéaire à partir d'une solution duale, et une règle appelée "Memo Resolution"  permettant de fusionner les contraintes linéaires. Nous verrons comment intégrer cela dans des solveurs MILP classiques ou des solveurs WCSP.