USC Distributed Constraint Optimization Problem (DCOP) Repository
maintained by Atul Kumar
In a DCOP, cooperative agents, each in control of one or more variables, work together to optimize a set of constraints that exist upon the variables.  This page contains DCOP datasets and variations of the ADOPT and incomplete algorithms for solving DCOP.  ADOPT is a polynomial space algorithm that is guaranteed to find an optimal solution, or a solution within a user-specified distance from the optimal, while allowing agents to execute asynchronously and in parallel.
 
Software
 
Software
References
Download
Original ADOPT
P.J. Modi, W. Shen, M. Tambe, M. Yokoo. “ADOPT: Asynchronous distributed constraint optimization with quality guarantees.” Artificial Intelligence Journal(AIJ). 161:149–180, 2005
P.J. Modi, W. Shen, M. Tambe, M. Yokoo. “ An asynchronous complete method for distributed constraint optimization.” In AAMAS, 2003.
ADOPT with preprocessing and valued constraints (newest version of ADOPT)
R.T. Maheswaran, M. Tambe, E. Bowring, J.P. Pearce, P. Varakantham. “Taking DCOP to the Real World : Efficient Complete Solutions for Distributed Event Scheduling.” In AAMAS, 2004.
Multi-criteria ADOPT (MCA)
E. Bowring, M. Tambe, M. Yokoo. "Multiply Constrained Distributed Constraint Optimization” In AAMAS, 2006.
CSAA (Constraint Satisfaction Ant Algorithm) provided by Koen Mertens
K. Mertens, and T. Holvoet, CSAA: A distributed ant algorithm framework for constraint satisfaction, Proceedings of the 17th International Florida Artificial Intelligence Research Society Conference (Barr, V. and Markov, Z., eds.), pp. 764-769, 2004 pdf © American Association for Artificial Intelligence ( FLAIRS proceedings )
Original MGM2
Implementation of 2-optimal algorithms in R.T. Maheswaran, J.P. Pearce, and M. Tambe, "Distributed Algorithms for DCOP: A Graphical-Game-Based Approach," in Proceedings of the 17th International Conference on Parallel and Distributed Computing Systems (PDCS), San Francisco, CA, September 15-17, 2004, pp. 432-439.
Multi-criteria MGM2 + Original MGM2 (also includes [MC-]MGM1) (Extended by Christopher Portway on top of Zvi Topol's implementation)
Extention of MGM2 (see above) to cover multiply-constrained graphs, specifically resourse and utility constraints. In a paper to appear in Ninth International Workshop on Distributed Constraint Reasoning (DCR) at CP-07.
MGM3 and SCA3 (implemented by Zvi Topol)
New 3-optimal algorithms based on 2-optimal algorithms in R.T. Maheswaran, J.P. Pearce, and M. Tambe, "Distributed Algorithms for DCOP: A Graphical-Game-Based Approach," in Proceedings of the 17th International Conference on Parallel and Distributed Computing Systems (PDCS), San Francisco, CA, September 15-17, 2004, pp. 432-439.
 
Datasets
 
Dataset
References
Download
Graph coloring datasets
P.J. Modi, W. Shen, M. Tambe, M. Yokoo. “ADOPT: Asynchronous distributed constraint optimization with quality guarantees.” Artificial Intelligence Journal(AIJ). 161:149–180, 2005
P.J. Modi, W. Shen, M. Tambe, M. Yokoo. “An asynchronous complete method for distributed constraint optimization.” In AAMAS, 2003.
Sensor net and graph coloring datasets
Meeting scheduling and sensor net datasets
R.T. Maheswaran, M. Tambe, E. Bowring, J.P. Pearce, P. Varakantham, “Taking DCOP to the real world: efficient complete solutions for distributed event scheduling.” In AAMAS, 2004.
Graph coloring, randomized, and high-stakes UAV datasets
R.T. Maheswaran, J.P. Pearce, M. Tambe. “Distributed algorithms for DCOP: a graphical-game-based approach.” In PDCS, 2004.
MC-DCOP Graph Coloring Datasets
 
Other material
 
Document
Download
Adopt presentation slides by Jay Modi
Adopt FAQ by Jay Modi
Results from S. Ali, S. Koenig, M. Tambe. “Preprocessing techniques for accelerating the DCOP algorithm ADOPT.” In AAMAS, 2005.
 
If you publish a paper using datasets obtained from this page, please include an acknowledgement in your paper, so that others can also find the datasets here.
Example:
Yin, Zhengyu (2008). USC DCOP Repository [ http://teamcore.usc.edu/dcop/ . Los Angeles, CA: University of Southern California, Department of Computer Science.
 
Or, for BiBTeX:
@misc{Yin:2008 ,
author = "Zhengyu Yin",
year = "2008",
title = "{USC} DCOP Repository",
institution = "University of Southern California, Department of Computer Science"
}
 
Please contact Atul Kumar ( atulk@usc.edu ) if you have any questions about the contents of this page.