M. Studeny, J. Cussens: The chordal graph polytope for learning decomposable models. In JMLR Workshops and Conference Proceedings 52 (2016), Proceedings of the Conference on Probabilistic Graphical Models [PGM 2016], (A. Antonucci, G. Corani, C. P. de Campos eds.), pp. 499-510.

The paper is inspired by an integer linear programming approach to learning the structure of decomposable models. We intend to represent decomposable models by special zero-one 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. We introduce a class of clutter inequalities and show that all of them are valid for (the vectors in) the polytope. In fact, these inequalities are even facet-defining for the polytope and we dare to conjecture that they lead to a complete polyhedral description of the polytope. Finally, we propose an LP method to solve the separation problem with these inequalities for use in a cutting plane approach.

AMS classification 52B12 68T30 90C27

integer linear programming
learning decomposable models
characteristic imset
chordal graph polytope
clutter inequalities
separation problem

A pdf version (253kB) is available.

The contribution builds on the following papers: