Multi-Objective 3-SAT with Survey-Propagation

Cyril Furtlehner 1 Marc Schoenauer 1, 2
1 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : An original approach to multi-objective optimization is introduced, using a message-passing algorithm to sample the Pareto set, i.e. the set of Pareto-non-dominated solutions. Several heuristics are proposed and tested on a simple bi-objective 3-SAT problem. The first one is based on a straightforward deformation of the Survey-Propagation (SP) equation to locally encode a Pareto trade-off. A simple heuristic is then tested, which combines an elimination procedure of clauses with the usual decimation of variables used in the SP algorithm, and is able to sample different regions of the Pareto-front. We study in more details the compliance of these deformed equations with basic Belief-Propagation (BP) properties. This first leads to an explicit Markov Random Field (MRF) of valid warning configuration, for which the SP equations are basic BP equations. This observation is then generalized to the multi-objective context. Numerical experiments on artificial problems up to 100000 variables are presented and discussed.
Type de document :
Communication dans un congrès
NIPS 2010 Workshop on Discrete Optimization in Machine Learning: Structures, Algorithms and Applications (DISCML), Dec 2010, Whisler, Canada. 2010
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00533149
Contributeur : Cyril Furtlehner <>
Soumis le : vendredi 5 novembre 2010 - 12:19:23
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : vendredi 26 octobre 2012 - 15:00:59

Fichier

wnips2010.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00533149, version 1

Collections

Citation

Cyril Furtlehner, Marc Schoenauer. Multi-Objective 3-SAT with Survey-Propagation. NIPS 2010 Workshop on Discrete Optimization in Machine Learning: Structures, Algorithms and Applications (DISCML), Dec 2010, Whisler, Canada. 2010. 〈inria-00533149〉

Partager

Métriques

Consultations de la notice

361

Téléchargements de fichiers

766