The chordal graph polytope for learning decomposable models

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

The chordal graph polytope for learning decomposable models

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

The chordal graph polytope for learning decomposable models

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA16-12010S" target="_blank" >GA16-12010S: Struktury podmíněné nezávislosti: kombinatorické a optimalizační metody</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the Eighth International Conference on Probabilistic Graphical Models

ISBN

—

ISSN

1938-7228

e-ISSN

—

Počet stran výsledku

12

Strana od-do

499-510

Název nakladatele

Microtome Publishing

Místo vydání

Brookline

Místo konání akce

Lugano

Datum konání akce

6. 9. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—