ECAI-2002 Conference Paper

[full paper]

Pseudo-tree Search with Soft Constraints

Javier Larrosa, Pedro Meseguer, Martí Sánchez

Pseudo-tree search is a well known algorithm for CSP solving. It exploits the problem structure to detect and solve independent subproblems. 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 ideas 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. We introduce PT-BB, a branch-and-bound algorithm that performs pseudo-tree search. It features the use of local upper bounds, with which a good performance is obtained. We show that PT-BB combines nicely with russian doll search, yielding an efficient algorithm.

Keywords: constraint satisfaction, search

Citation: Javier Larrosa, Pedro Meseguer, Martí Sánchez: Pseudo-tree Search with Soft Constraints. In F. van Harmelen (ed.): ECAI2002, Proceedings of the 15th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2002, pp.131-135.