Solving Coarse-grained DisCSPs with Multi-DisPeL and DisBO-wd

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.