We present a new hybrid algorithm for local search in distributed combinatorial optimization. This method is a mix between classical local search methods in which nodes take decisions based only on local information, and full inference methods that guarantee completeness.

We propose LS-DPOP(k), a hybrid method that combines the advantages of both these approaches. LS-DPOP(k) is a utility propagation algorithm controlled by a parameter k which specifies the maximal allowable amount of inference. The maximal space requirements are exponential in this parameter. In the dense parts of the problem, where the required amount of inference exceeds this limit, the algorithm executes a local search procedure guided by as much inference as allowed by k. LS-DPOP(k) can be seen as a large neighborhood search, where exponential neighborhoods are rigorously determined according to problem structure, and polynomial efforts are spent for their complete exploration at each local search step.

We show the efficiency of this approach with experimental results from the distributed meeting scheduling domain.