Multi Objective 3-SAT Problems addressed with Message Passing Techniques

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 : Message passing algorithms have been very successful in solving hard combinatorial problems, and have resulted in breakthrough results in the domain of random K-SAT problems. However, only single-objective SAT problems have been adressed by survey-propagation methods, whereas most real-world problems are indeed multi objective. A first approach to multi objective optimization using a message-passing algorithm is introduced, that aims at sampling 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. A first approach is based on a straightforward deformation of the survey-propagation 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 survey propagation algorithm, and is able to sample different regions of the Pareto-front. In a second stage we study in more details the compliance of these deformed equations with basic belief-propagation (BP) properties. This lead us first to an explicit Markov random field of valid warning configuration, for which the survey-propagation equations are basic belief propagation equations. This observation is then generalized by defining a MRF for warnings configurations expected to approximate well the Pareto-front. The survey propagation equations associated to this new MRF are derived, allowing for consistent estimations of the Pareto-set on single problem instances. Numerical experiments on artificial problems up to 100000 variables are presented and discussed.
Complete list of metadatas

https://hal.inria.fr/inria-00528438
Contributor : Cyril Furtlehner <>
Submitted on : Thursday, October 21, 2010 - 5:01:07 PM
Last modification on : Thursday, April 5, 2018 - 12:30:12 PM
Long-term archiving on : Friday, October 26, 2012 - 11:50:24 AM

File

RR-7424.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00528438, version 1

Collections

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⟩

Share

Metrics

Record views

627

Files downloads

755