Preprocessing Techniques for Distributed Constraint Optimization (Short Paper)


Syed M. Ali, Sven Koenig, and Milind Tambe. 2004. “Preprocessing Techniques for Distributed Constraint Optimization (Short Paper).” In International Joint Conference on Principles and Practices of Constraint Programming (CP).


Although algorithms for Distributed Constraint Optimization Problems (DCOPs) have emerged as a key technique for distributed reasoning, their application faces significant hurdles in many multiagent domains due to their inefficiency. Preprocessing techniques have been successfully used to speed up algorithms for centralized constraint satisfaction problems. This paper introduces a framework of very different preprocessing techniques that speed up ADOPT, an asynchronous optimal DCOP algorithm that significantly outperforms competing DCOP algorithms by more than one order of magnitude.
See also: 2004