Bayesian Network Structure Learning with Integer Programming: Polytopes,
  Facets, and Complexity
  The challenging task of learning structures of probabilistic graphical models
is an important problem within modern AI research. Recent years have witnessed
several major algorithmic advances in structure learning for Bayesian
networks---arguably the most central class of graphical models---especially in
what is known as the score-based setting. 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. Understanding
fundamental aspects of cutting planes and the related separation problem( is
important not only from a purely theoretical perspective, but also since it
holds out the promise of further improving the efficiency of state-of-the-art
approaches to solving BNSL exactly. In this paper, we make several theoretical
contributions towards these goals: (i) we study the computational complexity of
the separation problem, proving that the problem is NP-hard; (ii) we formalise
and analyse the relationship between three key polytopes underlying the
IP-based approach to BNSL; (iii) we study the facets of the three polytopes
both from the theoretical and practical perspective, providing, via exhaustive
computation, a complete enumeration of facets for low-dimensional
family-variable polytopes; and, furthermore, (iv) we establish a tight
connection of the BNSL problem to the acyclic subgraph problem.
