Pseudo-Tree Search with Soft Constraints

Abstract

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 is that its run time complexity is bounded by a problem structural parameter. In this paper, we extend this idea to soft constraint problems. We show that the same general principles apply to this domain. However, a naive implementation is not competitive with state-of-the-art algorithms, because solving independent problems separately may yield a poor algorithmic efficiency due to loose upper bounds. We introduce PT-BB, a branch-and-bound algorithm that performs efficient pseudo-tree search. Its main feature is the use of local upper bounds which can improve over loose global upper bounds. We also show that PT-BB combines nicely with russian doll search (RDS), producing an interesting algorithm.