Skip to Main content Skip to Navigation
Conference papers

Multi-Objective 3-SAT with Survey-Propagation

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
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.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Cyril Furtlehner Connect in order to contact the contributor
Submitted on : Friday, November 5, 2010 - 12:19:23 PM
Last modification on : Thursday, July 8, 2021 - 3:48:13 AM
Long-term archiving on: : Friday, October 26, 2012 - 3:00:59 PM


Files produced by the author(s)


  • HAL Id : inria-00533149, version 1



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. ⟨inria-00533149⟩



Les métriques sont temporairement indisponibles