Abstract
The motivation for this paper is the integer linear programming 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.
Original language | English |
---|---|
Pages (from-to) | 259-281 |
Number of pages | 23 |
Journal | International Journal of Approximate Reasoning |
Volume | 88 |
Early online date | 8 Jun 2017 |
Publication status | Published - Sept 2017 |