When solving large distributed constraint optimization problems (DCOP), belief-propagation and incomplete inference algorithms are candidates of choice. However, these methods perform poorly when the factor graph is very loopy (i.e. cyclic) because of non-convergence and high communication costs. As to improving performances of the Max-Sum inference algorithm when solving loopy constraint optimization problems, we propose to take inspiration from the belief-propagation-guided decimation used to solve sparse random graphs (k-satisfiability). We introduce the DECIMAXSUM method, parameterized in terms of policies to decide when to trigger decimation, which variables to decimate, and which values to assign to decimated variables. Our empirical analysis on a classical BP benchmark indicates that some of these combinations of policies outperform state-of-the-art competitors.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com