Large neighborhood search with quality guarantees for distributed constraint optimization problems

Ferdinando Fioretto, Federico Campeotto, Agostino Dovier, Enrico Pontelli, William Yeoh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationAAMAS 2015 - Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems
EditorsRafael H. Bordini, Pinar Yolum, Edith Elkind, Gerhard Weiss
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1835-1836
Number of pages2
ISBN (Electronic)9781450337717
StatePublished - Jan 1 2015
Externally publishedYes
Event14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015 - Istanbul, Turkey
Duration: May 4 2015May 8 2015

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume3
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference14th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2015
CountryTurkey
CityIstanbul
Period5/4/155/8/15

Keywords

  • DCOP
  • Distributed Q-learning
  • LNS
  • Local search

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Large neighborhood search with quality guarantees for distributed constraint optimization problems'. Together they form a unique fingerprint.

  • Cite this

    Fioretto, F., Campeotto, F., Dovier, A., Pontelli, E., & Yeoh, W. (2015). Large neighborhood search with quality guarantees for distributed constraint optimization problems. In R. H. Bordini, P. Yolum, E. Elkind, & G. Weiss (Eds.), AAMAS 2015 - Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (pp. 1835-1836). (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS; Vol. 3). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).