TY - GEN
T1 - A large neighboring search schema for multi-agent optimization
AU - Hoang, Khoi D.
AU - Fioretto, Ferdinando
AU - Yeoh, William
AU - Pontelli, Enrico
AU - Zivan, Roie
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2018.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
KW - Distributed Constraint Optimization
KW - Large Neighborhood Search
KW - Multiagent Systems
UR - http://www.scopus.com/inward/record.url?scp=85053111004&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85053111004&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-98334-9_44
DO - 10.1007/978-3-319-98334-9_44
M3 - Conference contribution
AN - SCOPUS:85053111004
SN - 9783319983332
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 688
EP - 706
BT - Principles and Practice of Constraint Programming - 24th International Conference, CP 2018, Proceedings
A2 - Hooker, John
PB - Springer Verlag
T2 - 24th International Conference on the Principles and Practice of Constraint Programming, CP 2018
Y2 - 27 August 2018 through 31 August 2018
ER -