The chordal graph polytope for learning decomposable models
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985556%3A_____%2F16%3A00462009" target="_blank" >RIV/67985556:_____/16:00462009 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
The chordal graph polytope for learning decomposable models
Original language description
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 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. 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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA16-12010S" target="_blank" >GA16-12010S: Conditional independence structures: combinatorial and optimization methods</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the Eighth International Conference on Probabilistic Graphical Models
ISBN
—
ISSN
1938-7228
e-ISSN
—
Number of pages
12
Pages from-to
499-510
Publisher name
Microtome Publishing
Place of publication
Brookline
Event location
Lugano
Event date
Sep 6, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—