Multi-Objective 3-SAT with Survey-Propagation - Archive ouverte HAL Access content directly
Conference Papers Year : 2010

Multi-Objective 3-SAT with Survey-Propagation


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.
Fichier principal
Vignette du fichier
wnips2010.pdf (414.98 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

inria-00533149 , version 1 (05-11-2010)


  • 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⟩
262 View
114 Download


Gmail Facebook Twitter LinkedIn More