A large neighboring search schema for multi-agent optimization

Khoi D. Hoang, Ferdinando Fioretto, William Yeoh, Enrico Pontelli, Roie Zivan

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

3 Scopus citations

Abstract

The Distributed Constraint Optimization Problem (DCOP) is an elegant paradigm for modeling and solving multi-agent problems which are distributed in nature, and where agents cooperate to optimize a global objective within the confines of localized communication. Since solving DCOPs optimally is NP-hard, recent effort in the development of DCOP algorithms has focused on incomplete methods. Unfortunately, many of such proposals do not provide quality guarantees or provide a loose quality assessment. Thus, this paper proposes the Distributed Large Neighborhood Search (DLNS), a novel iterative local search framework to solve DCOPs, which provides guarantees on solution quality refining lower and upper bounds in an iterative process. Our experimental analysis of DCOP benchmarks on several important classes of graphs illustrates the effectiveness of DLNS in finding good solutions and tight upper bounds in both problems with and without hard constraints.

Original languageEnglish (US)
Title of host publicationPrinciples and Practice of Constraint Programming - 24th International Conference, CP 2018, Proceedings
EditorsJohn Hooker
PublisherSpringer Verlag
Pages688-706
Number of pages19
ISBN (Print)9783319983332
DOIs
StatePublished - 2018
Event24th International Conference on the Principles and Practice of Constraint Programming, CP 2018 - Lille, France
Duration: Aug 27 2018Aug 31 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11008 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th International Conference on the Principles and Practice of Constraint Programming, CP 2018
CountryFrance
CityLille
Period8/27/188/31/18

Keywords

  • Distributed Constraint Optimization
  • Large Neighborhood Search
  • Multiagent Systems

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A large neighboring search schema for multi-agent optimization'. Together they form a unique fingerprint.

  • Cite this

    Hoang, K. D., Fioretto, F., Yeoh, W., Pontelli, E., & Zivan, R. (2018). A large neighboring search schema for multi-agent optimization. In J. Hooker (Ed.), Principles and Practice of Constraint Programming - 24th International Conference, CP 2018, Proceedings (pp. 688-706). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11008 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-98334-9_44