  We present a new approach for learning the structure of a treewidth-bounded
Bayesian Network (BN). The key to our approach is applying an exact method
(based on MaxSAT) locally, to improve the score of a heuristically computed BN.
This approach allows us to scale the power of exact methods -- so far only
applicable to BNs with several dozens of random variables -- to large BNs with
several thousands of random variables. Our experiments show that our method
improves the score of BNs provided by state-of-the-art heuristic methods, often
significantly.
