By the same authors

From the same journal

Towards using the chordal graph polytope in learning decomposable models

Research output: Contribution to journalArticle

Full text download(s)

Author(s)

Department/unit(s)

Publication details

JournalInternational Journal of Approximate Reasoning
DateAccepted/In press - 1 Jun 2017
DateE-pub ahead of print - 8 Jun 2017
DatePublished (current) - Sep 2017
Volume88
Number of pages23
Pages (from-to)259-281
Early online date8/06/17
Original languageEnglish

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.

Bibliographical note

©2017 Elsevier Inc. All rights reserved. This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy.

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations