Imagen de Portada
Código QR

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...

Descripción completa

Publicado en:Revista Cubana de Física Vol. 43; no. 1; pp. 4 - 13
Autores principales: MACHADO, D., MULET, R., PÉREZ, A.
Formato: Artículo
Publicado: Universidad de La Habana 7/15/2026
Materias:
Combinatorial optimization
Constraint satisfaction
Inference (Logic)
Monte Carlo method
Acceso en línea:Ver este registro en EBSCOhost
Sumario: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.