The Chordal Graph Polytope for Learning Decomposable Models

Milan Studeny´, James Cussens

Research output: Chapter in Book/Report/Conference proceedingConference contribution


This theoretical paper is inspired by an integer linear programming (ILP) approach to learning the
structure of decomposable models. We intend to represent decomposable models by 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. 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.
Original languageEnglish
Title of host publicationProceedings of the Eighth International Conference on Probabilistic Graphical Models
EditorsAlessandro Antonucci, Giorgio Corani, Cassio Polpo de Campos
Number of pages12
Publication statusPublished - 2016

Publication series

NameJournal of Machine Learning Research: Workshop and Conference Proceedings
ISSN (Electronic)1938-7228

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

Cite this