Reasoning and inference for (maximum) satisfiability : new insights

Au cœur de l'informatique et de l'intelligence artificielle, la logique est souvent utilisée comme un langage pour modéliser et résoudre des problèmes complexes issus du milieu académique ou d'applications industrielles. Un formalisme bien connu dans ce contexte est le problème de satisfiabilité (SAT) qui vérifie simplement si une formule propositionnelle donnée sous la forme d'un ensemble de contraintes, appelées clauses, peut être satisfaite. Une extension naturelle de SAT en problème d'optimisation est la satisfiabilité maximum (Max-SAT), qui consiste à déterminer le nombre maximal de contraintes clausales pouvant être satisfaites dans la formule. Dans nos travaux, on s'intéresse à l'étude du pouvoir et des limites de l'inférence et du raisonnement dans le contexte de ces deux paradigmes. Nos premières contributions tournent autour de l'étude de l'inférence dans le cadre des algorithmes de résolution pour SAT et Max-SAT. Tout d'abord, nous étudions l'inférence statistique dans le cadre des solveurs modernes pour SAT qui sont basés sur l'apprentissage de clauses. On introduit un formalisme bandit manchot pour la sélection adaptative d'heuristiques de branchement et on montre qu'un tel mécanisme permet d'améliorer l'efficacité des solveurs modernes. De plus, nous investiguons minutieusement la puissance de l'inférence dans le cadre des algorithmes de type séparation et évaluation pour Max-SAT grâce à la propriété de l'UP-résilience. Nos contributions s'étendent également à la théorie des preuves pour SAT et Max-SAT, l'un de nos objectifs majeurs étant de combler le fossé théorique entre l'inférence SAT et Max-SAT