TitlePseudo-Tree Search with Soft Constraints
Publication TypeConference Paper
Year of Publication2002
AuthorsLarrosa J, Meseguer P, Sánchez M
Editorvan Harmelen F.
Conference NameProceedings of the 15th European Conference on Artificial Intelligence, ECAI-02
PublisherIOS Press

Pseudo-tree search is a well known algorithm for CSP solving. It exploits the problem structure to delect 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 separtely 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 globla upper bounds. We also show that PT-BB combines nicely with russian doll search (RDS), procucing an interesting algorithm.