@inproceedings{RantanenHJ:NIPS2017,
title = {Learning Chordal {M}arkov Networks via Branch and Bound},
author = {Kari Rantanen and Antti Hyttinen and Matti J\"arvisalo},
editor = {Isabelle Guyon and Ulrike von Luxburg and Samy Bengio and
          Hanna M. Wallach and Rob Fergus and S. V. N. Vishwanathan
	  and Roman Garnett},
booktitle = {Proceedings of the 30th Annual Conference on
             Neural Information Processing Systems (NIPS 2017)},
pages = {1845--1855},
year = {2017},
}

Abstract:

We present a new algorithmic approach for the task of finding a
chordal Markov network structure that maximizes a given scoring
function. The algorithm is based on branch and bound and integrates
dynamic programming for both domain pruning and for obtaining
strong bounds for search-space pruning. Empirically, we show that
the approach dominates in terms of running times a recent integer
programming approach (and thereby also a recent constraint
optimization approach)  for the problem. Furthermore, our algorithm
scales at times further with respect to the number of variables
than a state-of-the-art dynamic programming algorithm for the
problem, with the potential of reaching 20 variables and at the
same time circumventing the tight exponential lower bounds on
memory consumption of the pure dynamic programming approach.