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/Entry/PoemConference contribution

19 Scopus citations


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
Number of pages19
ISBN (Print)9783319983332
StatePublished - 2018
Externally publishedYes
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


Conference24th International Conference on the Principles and Practice of Constraint Programming, CP 2018


  • Distributed Constraint Optimization
  • Large Neighborhood Search
  • Multiagent Systems

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this