M. Studeny:
How matroids occur in the context of learning Bayesian network structure.
In Uncertainty in Artificial Intelligence.
Proceedings of the 31th Conference
(M. Meila, T. Heskes eds.), AUAI Press, Corvallis 2015, pp. 832841.
 Abstract

It is shown that any connected matroid having
a nontrivial cluster of BN variables as its ground set
induces a facetdefining inequality for the polytope(s)
used in the ILP approach to globally optimal BN structure learning.
The result applies to wellknown kcluster inequalities,
which play a crucial role in the ILP approach.
 AMS classification 68T30 52B40 68T05
 Keywords
 learning Bayesian network structure
 integer linear programming
 imset
 matroid
 extreme supermodular function
 A
pdf version (144kB) is available.
The contribution builds on the following papers:
 M. Bartlett, J. Cussens:
Advances in Bayesian network learning using integer programming.
In Uncertainty in Artificial Intelligence. Proceedings of the
29th Conference (A. Nicholson, P. Smyth eds.),
AUAI Press, Corvallis 2013, pp. 182191.
 H. Q. Nguyen:
Semimodular functions and combinatorial geometries.
Transaction of the American Mathematical Society
238 (1978), pp. 355383.
 J. Cussens, M. Studeny, D. Haws:
Polyhedral aspects of score equivalence in Bayesian network structure learning.
To appear in Mathematical Programming A (November 2016).