Branch-and-Bound Heuristics for Incomplete DCOPs

The Incomplete Distributed Constraint Optimization Problem (I-DCOP) extends the distributed constraint optimization problem, where constraint costs are allowed to be unspecified. A distributed variant of the Synchronous Branch-and-Bound (SyncBB) search algorithm has been proposed to solve I-DCOPs, where unspecified constraint costs are elicited during its execution. In this paper, we propose two heuristics that can be used in conjunction with SyncBB to solve I-DCOPs. Our proposed heuristics speed up the algorithm by pruning those parts of the search space whose solution quality is sub-optimal. Thus, our model and heuristics extend the state of the art in distributed constraint reasoning to better model and solve distributed agent-based applications with user preferences.