Integer Programming for Bayesian Network Structure Learning

I will present our work on solving the problem of learning the 'optimal' Bayesian network (BN) from complete data by casting it as an integer program (IP). We use the SCIP (Solving Constraint Integer Programming) framework to do this. Although cutting planes (and strong valid inequalities generally) are a key ingredient in our approach, primal heuristics and efficient propagation are also important. I will present very recent work which allows the user to impose arbitrary conditional independence constraints on the BN. To scale up this approach (and also to deal with missing data) I think 'delayed column generation' will be crucial, so I'll conclude with some pointers in that direction.

The slides from the talk are available here: http://www.cs.york.ac.uk/aig/talks/cussens_2013b.pdf.