Distributed Breakout: Beyond Satisfaction

Abstract

The Distributed Breakout Algorithm (DBA) is a local search algorithm that was originally designed to solve DisCSPs and DisMaxCSPs. Extending it to general-valued DCOPs requires three design choices: manner of modifying base costs (multiplicative weights or additive penalties); definition of constraint violation (non-zero cost, non-minimum cost, and maximum cost); and scope of modifying cost tables during breakout (entry, row, column, or table). We propose Generalized DBA (GDBA) to span the 24 combinations in the three dimensions. In our theoretical analysis we prove that some variants of GDBA are equivalent for certain problems, and prove that other variants may find suboptimal solutions even on tree topologies where DBA is complete. Our extensive empirical evaluation on various benchmarks shows that in practice, GDBA is capable of finding solutions of equal or significantly lower cost than alternative heuristic approaches (including DSA).