BELIEF PROPAGATION WITH INFORMED INITIALIZATION IN COMBINATORIAL OPTIMIZATION PROBLEMS.
In this work, we study the behavior of the Belief Propagation (BP) algorithm in solving two combinatorial optimization problems: 3-SAT and 3-XORSAT. We examine the performance of BP on planted instances, applying the algorithm with a fraction of the variables fixed from the beginning. The probabilit...
| Publicado en: | Revista Cubana de Física Vol. 43; no. 1; pp. 4 - 13 |
|---|---|
| Autores principales: | , , |
| Formato: | Artículo |
| Publicado: |
Universidad de La Habana
7/15/2026
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=lth&AN=196011055&site=ehost-live header: @attributes: shortDbName: lth uiTerm: 196011055 longDbName: MedicLatina uiTag: AN controlInfo: bkinfo: jinfo: jid: 02539268 UEW jtl: Revista Cubana de Física issn: 02539268 maglogo: N pubinfo: dt: 7/15/2026 vid: 43 iid: 1 pid: 21208 pub: Universidad de La Habana artinfo: ui: 196011055 ppf: 4 ppct: 9 formats: fmt: @attributes: type: P size: 1MB tig: atl: BELIEF PROPAGATION WITH INFORMED INITIALIZATION IN COMBINATORIAL OPTIMIZATION PROBLEMS. aug: au: MACHADO, D. MULET, R. PÉREZ, A. affil: Center for Complex Systems and Department of Theoretical Physics, Faculty of Physics, University of Havana, 10400, Havana, Cuba. Dipartimento di Fisica, Sapienza Università di Roma, P.le Aldo Moro 5, 00185 Rome, Italy. CNR - Nanotec, unità di Roma, P.le Aldo Moro 5, 00185 Rome, Italy. su: Combinatorial optimization Constraint satisfaction Inference (Logic) Monte Carlo method sug: subj: Combinatorial optimization Constraint satisfaction Inference (Logic) Monte Carlo method keyword: belief propagation combinatorial optimization planted model modelo plantado optimización combinatoria propagación de creencias ab: In this work, we study the behavior of the Belief Propagation (BP) algorithm in solving two combinatorial optimization problems: 3-SAT and 3-XORSAT. We examine the performance of BP on planted instances, applying the algorithm with a fraction of the variables fixed from the beginning. The probability of reaching any solution using this informed initialization displays abrupt changes with the number of fixed variables. In both problems, BP requires fixing a smaller fraction of variables than the Monte Carlo algorithm to solve a given instance. We also extended a known analytical description of the Unit Clause Propagation Algorithm to accurately predict BP's behavior with an informed initialization for 3-XORSAT in random regular graphs. En este trabajo estudiamos el comportamiento del algoritmo Belief Propagation (BP) en la resolución de dos problemas de optimización combinatoria: 3-SAT y 3-XORSAT. Aplicamos BP a la versión plantada de estos problemas cuando una fracción de las variables está fija desde el inicio. La probabilidad de resolver una instancia usando esta inicialización informada muestra cambios abruptos con el número de variables fijadas. En ambos problemas estudiados BP requiere menos variables fijadas que el algoritmo de Monte Carlo para converger a una solución. Finalmente, extendemos una conocida descripción analítica del algoritmo Unit Clause Propagation para predecir con precisión el comportamiento de BP aplicado al 3-XORSAT en grafos aleatorios regulares con inicialización informada. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y custom: Copyright of Revista Cubana de Física is the property of Universidad de La Habana and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. item: Revista Cubana de Física holder: Universidad de La Habana dt: @attributes: year: 2026 holdings: @attributes: islocal: N |
|---|