Pseudo-tree search with Soft Constraints

摘要: Pseudo-tree search is a well known algorithm for CSP solving. It exploits the problem structure to detect independent subproblems that are solved separately. Its main advantage its run time complexity bounded by structural parameter. In this paper, we extend idea soft constraint problems. We show same general principles apply domain. However, naive implementation not competitive with state-of-the-art algorithms, because solving problems separately may yield poor algorithmic efficiency due loose upper bounds. introduce PT-BB, branch-and-bound performs efficient pseudo-tree search. feature use of local bounds which can improve over global also PT-BB combines nicely russian doll (RDS), producing an interesting algorithm.