Skip to main content

Research Repository

See what's under the surface

Advanced Search

Solving coarse-grained DisCSPs with Multi-DisPeL and DisBO-wd.

Basharu, Muhammed; Arana, Inés; Ahriz, Hatem


Muhammed Basharu

Inés Arana

Hatem Ahriz


Tsau Young Lin

Jeffrey M. Bradshaw

Matthias Klusch

Chengqi Zhang

Andrei Broder

Howard Ho


We present Multi-DisPel, a penalty-based local search distributed algorithm which is able to solve coarse-grained Distributed Constraint Satisfaction Problems (DisCSPs) efficiently. Multi-DisPeL uses penalties on values in order to escape local optima during problem solving rather than the popular weights on constraints. We also introduce DisBO-wd, a stochastic algorithm based on DisBO (Distributed Breakout) which includes a weight decay mechanism. We compare Multi-DisPeL and DisBO-wd with other algorithms and show, empirically, that they are more efficient and at least as effective as state of the art algorithms in some problem classes.

Start Date Nov 2, 2007
Publication Date Dec 31, 2007
Publisher IEEE Computer Society
Article Number 4407307
Pages 335-341
ISBN 9780769530277
Institution Citation BASHARU, M., ARANA, I. and AHRIZ, A. 2007. Solving coarse-grained DisCSPs with Multi-DisPeL and DisBO-wd. In Lin, T.Y., Bradshaw, J.M., Klusch, M., Zhang, C., Broder, A. and Ho, H. (eds.) Proceedings of the 2007 IEEE/WIC/ACM international conference on intelligent agent technology (IAT 2007), 2-5 November 2007, Silicon Valley, USA. Los Alamitos: IEEE Computer Society [online], article number 4407307, pages 335-341. Available from:
Keywords Multi-DisPeL; DisBO-wd; Algorithms; Distributed constraint satisfaction problems; DisCSPs


You might also like

Downloadable Citations