Large neighborhood search with quality guarantees for distributed constraint optimization problems


Copyright © 2015, International Foundation for Autonomous Agents and Multiagent Systems ( All rights reserved.This paper proposes Distributed Large Neighborhood Search (DLNS), an incomplete DCOP algorithm that builds on the strengths of centralized LNS. D-LNS: (i) is anytime; (ii) provides guarantees on solution quality (upper and lower bounds); and (iii) can learn online the best neighborhood to explore. Experimental results show that D-LNS outperforms other incomplete DCOP algorithms in random and scale-free network instances.

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS