License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2021.41
URN: urn:nbn:de:0030-drops-153324
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15332/
Go to the corresponding LIPIcs Volume Portal

Liu, Xiangshuang ; Chen, Ziyu ; Chen, Dingding ; Gao, Junsong

A Bound-Independent Pruning Technique to Speeding up Tree-Based Complete Search Algorithms for Distributed Constraint Optimization Problems

pdf-format:
LIPIcs-CP-2021-41.pdf (2 MB)

Abstract

Complete search algorithms are important methods for solving Distributed Constraint Optimization Problems (DCOPs), which generally utilize bounds to prune the search space. However, obtaining high-quality lower bounds is quite expensive since it requires each agent to collect more information aside from its local knowledge, which would cause tremendous traffic overheads. Instead of bothering for bounds, we propose a Bound-Independent Pruning (BIP) technique for existing tree-based complete search algorithms, which can independently reduce the search space only by exploiting local knowledge. Specifically, BIP enables each agent to determine a subspace containing the optimal solution only from its local constraints along with running contexts, which can be further exploited by any search strategies. Furthermore, we present an acceptability testing mechanism to tailor existing tree-based complete search algorithms to search the remaining space returned by BIP when they hold inconsistent contexts. Finally, we prove the correctness of our technique and the experimental results show that BIP can significantly speed up state-of-the-art tree-based complete search algorithms on various standard benchmarks.

BibTeX - Entry

@InProceedings{liu_et_al:LIPIcs.CP.2021.41,
  author =	{Liu, Xiangshuang and Chen, Ziyu and Chen, Dingding and Gao, Junsong},
  title =	{{A Bound-Independent Pruning Technique to Speeding up Tree-Based Complete Search Algorithms for Distributed Constraint Optimization Problems}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{41:1--41:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15332},
  URN =		{urn:nbn:de:0030-drops-153324},
  doi =		{10.4230/LIPIcs.CP.2021.41},
  annote =	{Keywords: DCOP, complete algorithms, search}
}

Keywords: DCOP, complete algorithms, search
Collection: 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Issue Date: 2021
Date of publication: 15.10.2021
Supplementary Material: Software (Source Code): https://github.com/czy920/BIP

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI