The Chordal Graph Polytope for Learning Decomposable Models


Milan Studený, James Cussens ;
Proceedings of the Eighth International Conference on Probabilistic Graphical Models, PMLR 52:499-510, 2016.


This theoretical paper is inspired by an \em integer linear programming (ILP) approach to learning the structure of \em decomposable models. We intend to represent decomposable models by special zero-one vectors, named \em 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 \em chordal graph polytope. We introduce a class of \em 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 \em separation problem with these inequalities for use in a cutting plane approach.

Related Material