@inproceedings{CussensJKB:IJCAI2017,
author = {James Cussens and Matti J\"arvisalo and Janne H. Korhonen and Mark Bartlett},
title = {Bayesian Network Structure Learning with Integer Programming:
         Polytopes, Facets and Complexity (Extended Abstract)},
booktitle = {Proceedings of the 26th International Joint Conference
             on Artificial Intelligence (IJCAI 2017)},
editor = {Carles Sierra},
pages = {4990--4994},
publisher = {IJCAI},
year = {2017},
}

Abstract:

Developing accurate algorithms for learning structures of probabilistic
graphical models is an important problem within modern AI research. Here
we focus on score-based structure learning for Bayesian networks as
arguably the most central class of graphical models. A successful generic
approach to optimal Bayesian network structure learning (BNSL), based on
integer programming (IP), is implemented in the GOBNILP system. Despite
the recent algorithmic advances, current understanding of foundational
aspects underlying the IP based approach to BNSL is still somewhat
lacking. In this paper, we provide theoretical contributions towards
understanding fundamental aspects of cutting planes and the related
separation problem in this context, ranging from NP-hardness results to
analysis of polytopes and the related facets in connection to BNSL.