---
title: "Applying Max-Sum to Asymmetric Distributed Constraint Optimization"
authors:
  - "Roie Zivan"
  - "Tomer Parash"
  - "Yarden Naveh"
doi: ""
url: "https://ijcai.org/proceedings/2015/67"
pdf: "https://ijcai.org/proceedings/2015/0067.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "432-438"
track: "Main Track"
keywords:
---

# Applying Max-Sum to Asymmetric Distributed Constraint Optimization

Roie Zivan, Tomer Parash, Yarden Naveh

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 432-438.

## Abstract

We study the adjustment and use of the Max-sumalgorithm for solving Asymmetric Distributed ConstraintOptimization Problems (ADCOPs). First, we formalize asymmetric factor-graphs and apply the different versions of Max-sum to them. Apparently, in contrast to local search algorithms, most Max-sum versions perform similarly when solving symmetric and asymmetric problems and some even perform better on asymmetric problems. Second, we prove that the convergence properties of Max-sum ADVP (an algorithm that was previously found to outperform other Max-sum versions) and the quality of the solutions it produces are dependent on the order between nodes involved in each constraint, i.e., the inner constraint order (ICO). A standard ICO allows to reproduce the properties achieved for symmetric problems, and outperform previously proposed local search ADCOP algorithms. Third, we demonstrate that a non-standard ICO can be used to balance exploration and exploitation, resulting in the best performing Max-sum version on both symmetric and asymmetric standard benchmarks.