Large Neighborhood Search with Quality Guarantees for Distributed Constraint Optimization Problems
Ferdinando Fioretto, Federico Campeotto, Agostino Dovier, Enrico Pontelli, William Yeoh · Institutional Research Information System (University of Udine) · 2015
This paper proposes Distributed Large Neighborhood Search (D-LNS), 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.