Local Optimal Solutions for DCOP: New Criteria, Bound, and Algorithm

Distributed constraint optimization (DCOP) is a popular formal-ism for modeling cooperative multi-agent systems. In large-scale networks, finding a global optimum using complete algorithms is often impractical, which leads to the study on incomplete algo-rithms. Traditionally incomplete algorithms can only find locally optimal solution with no quality guarantees. Recent work on k-size-optimality has established bounds on solution quality, but size is not the only criteria for forming local optimization groups. In addition, there is only one algorithm for computing solutions for arbitrary k and it is quite inefficient. We introduce t-distance-optimality, which offers an alternative way to specify optimization groups. We establish bounds for this criteria that are often tighter than those for k-optimality. We then introduce an asynchronous lo-cal search algorithm for t-distance-optimality. We implement and evaluate the algorithm for both t and k optimality that offer signifi-cant improvements over KOPT – the only existing algorithm for k-size-optimality. Our experiment shows t-distance-optimality con-verges more quickly and to better solutions than k-size-optimality in scale-free graphs, but k-size-optimality has advantages for ran-dom graphs. 1