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 metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/inria-00533149
Contributor : Cyril Furtlehner <>
Submitted on : Friday, November 5, 2010 - 12:19:23 PM
Last modification on : Thursday, April 5, 2018 - 12:30:12 PM
Long-term archiving on : Friday, October 26, 2012 - 3:00:59 PM

File

wnips2010.pdf
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

445

Files downloads

774