Distributed Cluster Tree Elimination.
Ismel Brito, Pedro Meseguer · 2008
Abstract. Cluster and mini-cluster tree elimination are well-known solving meth-ods for constrained optimization problems, developed for the centralized case. These methods, based on cost function combination, can be easily reformulated as synchronous algorithms to solve the distributed versions of the above men-tioned problems. During solving they exchange a linear number of messages, but each could be of exponential size. This is their main drawback that often limits their practical application. Filtering is a general technique to decrease the size of cost function combination when using upper and lower bounds. We com-bine filtering with the previous algorithms, producing a significative decrement in message size. As result, the improved algorithm is able to solve larger prob-lems, keeping under control memory consumption. Experimental results show the benefits of this approach. 1