Multi-Objective 3-SAT with Survey-Propagation
作者： Marc Schoenauer , Cyril Furtlehner
DOI:
关键词:
摘要: An original approach to multi-objective optimization is introduced, using a message-passing algorithm sample the Pareto set, i.e. set of Pareto-non-dominated solutions. Several heuristics are proposed and tested on simple bi-objective 3-SAT problem. The first one based straightforward deformation Survey-Propagation (SP) equation locally encode trade-off. A heuristic then tested, which combines an elimination procedure clauses with usual decimation variables used in SP algorithm, able different regions Pareto-front. We study more details compliance these deformed equations basic Belief-Propagation (BP) properties. This leads explicit Markov Random Field (MRF) valid warning configuration, for BP equations. observation generalized context. Numerical experiments artificial problems up 100000 presented discussed.
参考文章(10)
Marc Mézard, Riccardo Zecchina, Random K -satisfiability problem: From an analytic solution to an efficient algorithm Physical Review E. ,vol. 66, pp. 056126- ,(2002) , 10.1103/PHYSREVE.66.056126
Alfredo Braunstein, Riccardo Zecchina, Survey propagation as local equilibrium equations Journal of Statistical Mechanics: Theory and Experiment. ,vol. 2004, pp. 06007- ,(2004) , 10.1088/1742-5468/2004/06/P06007
Federico Ricci-Tersenghi, Giorgio Parisi, Andrea Montanari, Instability of one-step replica-symmetry-broken phase in satisfiability problems Journal of Physics A. ,vol. 37, pp. 2073- 2091 ,(2004) , 10.1088/0305-4470/37/6/008
Demian Battaglia, Michal Kolář, Riccardo Zecchina, Minimizing energy below the glass thresholds Physical Review E. ,vol. 70, pp. 036107- 036107 ,(2004) , 10.1103/PHYSREVE.70.036107
Riccardo Zecchina, Marc Mézard, Stephan Mertens, Threshold values of random K-SAT from the cavity method Random Structures and Algorithms. ,vol. 28, pp. 340- 373 ,(2006) , 10.1002/RSA.V28:3
F.R. Kschischang, B.J. Frey, H.-A. Loeliger, Factor graphs and the sum-product algorithm IEEE Transactions on Information Theory. ,vol. 47, pp. 498- 519 ,(2001) , 10.1109/18.910572
F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, L. Zdeborova, Gibbs states and the set of solutions of random constraint satisfaction problems Proceedings of the National Academy of Sciences of the United States of America. ,vol. 104, pp. 10318- 10323 ,(2007) , 10.1073/PNAS.0703685104
Elitza Maneva, Elchanan Mossel, Martin J. Wainwright, A new look at survey propagation and its generalizations Journal of the ACM. ,vol. 54, pp. 17- ,(2007) , 10.1145/1255443.1255445
R. Zecchina, M. Mezard, A. Braunstein, Survey propagation: an algorithm for satisfiability arXiv: Computational Complexity. ,(2002)
BraunsteinA., MézardM., ZecchinaR., Survey propagation: An algorithm for satisfiability Random Structures and Algorithms. ,(2005) , 10.5555/1077450.1077456