LP relaxations and pruning for characteristic imsets

0377918 - ÚTIA 2013 CZ eng V - Výzkumná zpráva
Studený, Milan
LP relaxations and pruning for characteristic imsets.
Praha: ÚTIA AVČR, 2012. 30 s. Research Report, 2323.
Grant CEP: GA ČR GA201/08/0539
Institucionální podpora: RVO:67985556
Klíčová slova: learning Bayesian network structure * quality criterion * integer linear programming
Kód oboru RIV: BA - Obecná matematika
http://library.utia.cas.cz/separaty/2012/MTR/Studeny-LP relaxations and pruning for characteristic imsets.pdf

The geometric approach to learning BN structure is to represent it by a certain vector; a suitable such zero-one vector is the characteristic imset, which allows to reformulate the task of finding global maximum of a score over BN structures as an integer linear programming problem. The main contribution of this report is an LP relaxation of the corresponding polytope, that is, a polyhedral description of the domain of the respective integer linear programming problem.
Trvalý link: http://hdl.handle.net/11104/0209940