The Chordal Graph Polytope for Learning Decomposable Models

Research output: Other contribution


This theoretical paper is inspired by an integer linear programming (ILP) approach to learning thestructure of decomposable models. We intend to represent decomposable models by special zeroonevectors, 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 graphpolytope. We introduce a class of clutter inequalities and show that all of them are valid for (thevectors in) the polytope. In fact, these inequalities are even facet-defining for the polytope and wedare to conjecture that they lead to a complete polyhedral description of the polytope. Finally, wepropose an LP method to solve the separation problem with these inequalities for use in a cuttingplane approach.
Original languageEnglish
Number of pages12
Publication statusPublished - 2016

Bibliographical note

© 2016, The Authors. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details


Dive into the research topics of 'The Chordal Graph Polytope for Learning Decomposable Models'. Together they form a unique fingerprint.

Cite this