/Exploiting Problem Structure for Distributed Constraint Optimization

Exploiting Problem Structure for Distributed Constraint Optimization

Katia Sycara
Conference Paper, Proceedings of the First International Conference on Multi-Agent Systems, January, 1995

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


Distributed constraint optimization imposes considerable complexity in agents’ coordinated search for an optimal solution. However, in many application domains, problems often exhibit special structures that can be exploited to facilitate more efficient problem solving. One of the most recurrent structures involves disparity among subproblems. We present a coordination mechanism, Anchor&Ascend, for distributed constraint optimization that takes advantage of disparity among subproblems to efficiently guide distributed local search for global optimality. The coordination mechanism assigns different overlapping subproblems to agents who must interact and iteratively converge on a solution. In particular, an anchor agent who conducts local best first search to optimize its subsolution interacts with the rest of the agents who perform distributed constraint satisfaction to enforce problem constraints and constraints imposed by the anchor agent. We focus our study on the well-known NP-complete job shop scheduling problem. We define and study two problem structure measures, disparity ratio and disparity composition ratio. We experimentally evaluated the effectiveness of the Anchor&Ascend mechanism on a suite of job shop scheduling problems over a wide range of values of disparity composition. Our experimental results show that (1) considerable advantage can be obtained by explicitly exploiting disparity (2) disparity composition ratio plays a more important role than disparity ratio in finding high quality solution with little computational cost.

BibTeX Reference
author = {Katia Sycara},
title = {Exploiting Problem Structure for Distributed Constraint Optimization},
booktitle = {Proceedings of the First International Conference on Multi-Agent Systems},
year = {1995},
month = {January},