International Journal of Approximate Reasoning
88 (2017), pp. 259281.
 Abstract

The motivation for this paper is the integer linear programming (ILP)
approach to learning the structure of a decomposable graphical model.
We have chosen to represent decomposable models by means of special zeroone vectors, named
characteristic imsets. Our approach leads to the study of a special polytope, defined as
the convex hull of all characteristic imsets for chordal graphs, named the chordal graph polytope.
In this theoretical paper, we introduce a class of clutter inequalities (valid for the vectors in the polytope)
and show that all of them are facetdefining for the polytope. We dare to conjecture
that they lead to a complete polyhedral description of the polytope.
Finally, we propose a linear programming method to solve the separation problem
with these inequalities for the use in a cutting plane approach.
 AMS classification 52B12 68T30 90C27
 Keywords
 integer linear programming
 learning decomposable models
 characteristic imset
 chordal graph polytope
 clutter inequalities
 separation problem
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.
 R. Hemmecke, S. Lindner, M. Studeny:
Characteristic imsets for learning Bayesian network structure.
International Journal of Approximate Reasoning
53 (2012), n. 9, pp. 13361349.
 S. L. Lauritzen (1996).
Graphical Models.
Clarendon Press, Oxford.
 S. Lindner (2012)
Discrete optimization in machine learning: learning Bayesian network structures and conditional independence implication.
PhD thesis, TU Munich.
 M. Studeny, D. Haws:
Learning Bayesian network structure: towards the essential graph by integer linear programming tools.
International Journal of Approximate Reasoning
55 (2014), pp. 10431071.
Moreover, the paper is an extended version of the conference proceedings paper:
 A
pdf version (315kB) of a preprint is available.