M. Studeny, J. Cussens: Towards using the chordal graph polytope in learning decomposable models. International Journal of Approximate Reasoning 88 (2017), pp. 259-281.

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 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. 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 facet-defining 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

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

A pdf version of the published paper (557kB) is already open-access available.

The contribution builds on the following papers:

Moreover, the paper is an extended version of the conference proceedings paper: