BIP Revisited: Enabling Efficient Dominance Pruning for Distributed Constraint Optimization

Abstract

Bound-Independent Pruning (BIP) is a powerful technique for accelerating tree-based complete search algorithms for Distributed Constraint Optimization Problems (DCOPs) by pruning dominated regions of the search space using only local information. However, BIP fundamentally relies on constructing a context-dependent dominating space through joint optimization over local constraints, incurring exponential computational and storage complexity that limits its practical scalability. To address this limitation, we propose DR-BIP, a decoupled and sound reformulation of BIP that enables efficient identification of dominated subspaces without explicitly computing the dominating space. By reformulating dominated-subspace detection into pairwise dominance tests and decoupling them across independent constraints, DR-BIP eliminates joint optimization and reduces both computational and storage complexity from exponential to polynomial. The resulting dominance components can be precomputed and reused across context changes, further improving efficiency. We formally prove the correctness of DR-BIP and integrate it into several state-of-the-art tree-based complete DCOP algorithms. Extensive empirical evaluation on standard benchmarks confirms that DR-BIP consistently outperforms BIP, significantly reducing both computation time and communication overhead.