2 Departamento de Informática

Abstract. A credal network associates convex sets of probability distributions with graph-based models. Inference with credal networks aims at determining intervals on probability measures. Here we describe how a branch-and-bound based approach can be applied to accomplish approximated inference in polytrees iteratively. Our strategy explores a breadth-first version of branch-and-bound to compute outer approximations for the probability intervals. The basic idea is to refine the outer bounds calculated by the A/R+ algorithm until they are sufficiently precise or time/memory constraints have been exceeded...