  In the context of solving large distributed constraint optimization problems
(DCOP), belief-propagation and approximate inference algorithms are candidates
of choice. However, in general, when the factor graph is very loopy (i.e.
cyclic), these solution methods suffer from bad performance, due to
non-convergence and many exchanged messages. As to improve performances of the
Max-Sum inference algorithm when solving loopy constraint optimization
problems, we propose here to take inspiration from the
belief-propagation-guided dec-imation used to solve sparse random graphs
(k-satisfiability). We propose the novel DeciMaxSum method, which is
parameterized in terms of policies to decide when to trigger decimation, which
variables to decimate, and which values to assign to decimated variables. Based
on an empirical evaluation on a classical BP benchmark (the Ising model), some
of these combinations of policies exhibit better performance than
state-of-the-art competitors.

Multiagent Systems;Artificial Intelligence