Multi Objective 3-SAT Problems addressed with Message Passing Techniques

Cyril Furtlehner 1 Marc Schoenauer 1, 2
1 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Résumé : Les algorithmes de passage de messages ont permis de résoudre des problèmes combinatoires difficiles avec pour résultats des progrès notables dans le domaine K-SAT aléatoire. Cependant, les résultats obtenus par survey-propagation sont limités à des problèmes SAT mono-critères alors que la plupart des problèmes réel sont multi objectifs. Une première approche au contexte multi objectif est proposée, dont le but est d'échantillonner le front de Pareto, c.a.d. l'ensemble des solutions non-dominées au sens de Pareto. Plusieurs heuristiques sont proposées et testées, sur un problème 3-SAT bi-objectifs. Une première approche est basée sur une déformation directe des équations survey-propagation afin d'encoder localement un compromis de Pareto. Une heuristique simple est ensuite testée qui combine une procédure d'élimination des clauses avec la décimation habituelle des variables utilisée dans l'algorithm survey-propagation, permettant d'échantilloner différentes régions du front de Pareto. Dans un deuxième temps, nous étudions en détails la compatibilité de ces équations avec les propiétés basique de belief-propagation. Ceci nous conduit d'abord à trouver un Champ Markovien aléatoire explicite sur les configurations de warnings pour lesquelles les équations de survey-propagation coincident avec les equations de belief-propagation. Cette observation est ensuite généralisée en définissant un champ Markovien aléatoire pour les configurations situées dans le voisinage du de l'ensemble de Pareto. Les équations de survey-propagation correspondantes que nous obtenons donne alors la possibilité d'estimer de façon cohérente du front de Pareto sur des exemple de problèmes. Des expériences numériques sur des problèmes artificiels atteignants 100000 variables sont présentées et discutées.
Liste complète des métadonnées

https://hal.inria.fr/inria-00528438
Contributeur : Cyril Furtlehner <>
Soumis le : jeudi 21 octobre 2010 - 17:01:07
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : vendredi 26 octobre 2012 - 11:50:24

Fichier

RR-7424.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00528438, version 1

Citation

Cyril Furtlehner, Marc Schoenauer. Multi Objective 3-SAT Problems addressed with Message Passing Techniques. [Research Report] RR-7424, INRIA. 2010, pp.21. 〈inria-00528438〉

Partager

Métriques

Consultations de la notice

267

Téléchargements de fichiers

729