Large neighborhood search with quality guarantees for distributed constraint optimization problems

Abstract

Copyright © 2015, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). 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.

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