Weighted constraint satisfaction problems (WCSPs) are one of the most important constraint programming models aiming to find a cost-minimal solution. Tree-based Large Neighborhood Search (T-LNS) is an important local search based incomplete algorithm to solve a WCSP. Currently, when solving unseen problem instances, the parameter of T-LNS (i.e., destroy rate t) is obtained by either trying different values or adapting the value that has been shown to be well-performed in a known problem set. However, the best value of the destroy rate$t$that yields the best performance for T-LNS varies over different problem instances. As a result, tuning the parameter in such a hand-crafted way could either be tedious or hinder the performance of T-LNS. Therefore, to further stabilize and optimize the performance of T-LNS when solving WCSP instances, we propose to build a pretrained algorithm configurator that can recommend a suitable value of$t$for T-LNS based on the problem instance it will solve, via supervised learning. In more detail, in order to achieve instance-specific parameter prediction, we propose to encode the information such as the size and structure of a WCSP instance into a feature vector, and then leverage the fledged machine learning models to build our first pretrained algorithm configurator. Then, in order to encode a WCSP instance more comprehensively, we propose to use directed tripartite graph to represent a WCSP instance, which can represent the high- dimensional cost values in constrain functions. Then, we use Graph Attention Networks (GATs) to learn the embedding of tripartite graph and then build our second pretrained algorithm configurator. Finally, the experimental results show that our proposed algorithm configurators can effectively recommend suitable parameters for T-LNS in a series problem instances, yielding better performance over other competitors on different benchmark problems.

Complete search algorithms are important methods for solving Distributed Constraint Optimization Problems (DCOPs), which generally utilize bounds to prune the search space. However, obtaining high-quality lower bounds is quite expensive since it requires each agent to collect more information aside from its local knowledge, which would cause tremendous traffic overheads. Instead of bothering for bounds, we propose a Bound-Independent Pruning (BIP) technique for existing tree-based complete search algorithms, which can independently reduce the search space only by exploiting local knowledge. Specifically, BIP enables each agent to determine a subspace containing the optimal solution only from its local constraints along with running contexts, which can be further exploited by any search strategies. Furthermore, we present an acceptability testing mechanism to tailor existing tree-based complete search algorithms to search the remaining space returned by BIP when they hold inconsistent contexts. Finally, we prove the correctness of our technique and the experimental results show that BIP can significantly speed up state-of-the-art tree-based complete search algorithms on various standard benchmarks.