An Iterative Refined Max-sum_AD Algorithm via Single-side Value Propagation and Local Search

Max-sum ADVP is a message-passing algorithm for solving Distributed Constraint Optimization Problems (DCOPs) able to obtain a convergent solution in a cyclic factor graph. Nevertheless, the solution quality is closely related to the timing for starting value propagation in Max-sum ADVP. In other words, low-quality initial assignments will lead to a poor result. In this paper, we illustrate that value propagation can eliminate the inconsistent contexts in Max-sum AD and break ties among utilities, but it also restricts the exploration brought by Max-sum. For balancing between the exploration and the accuracy, we propose a new iterative refined Max-sum AD algorithm with single-side value propagation, called Max-sum ADSSVP. It performs two phases in every two convergences, one phase which enables the exploration to find high-quality initial assignments and the other phase which enables value propagation to guarantee solution quality. Max-sum ADSSVP tackles the timing selection problem by iteratively refining initial assignments in every exploration phase. Besides, local search is introduced after the value propagation phase to speed up the convergence process. Our empirical evaluation indicates that our methods are independent of initial assignments and less likely to get stuck in local optima.