Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Lifted linear programming

: Mladenov, M.; Ahmadi, B.; Kersting, K.

Volltext ()

Lawrence, N. ; Journal of Machine Learning Research -JMLR-:
Fifteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2012. Online proceedings : April 21-23, 2012 La Palma, Canary Islands
JMLR, 2012 (JMLR workshop and conference proceedings 22)
International Conference on Artificial Intelligence and Statistics (AISTATS) <15, 2012, La Palma>
Konferenzbeitrag, Zeitschriftenaufsatz, Elektronische Publikation
Fraunhofer IAIS ()

Lifted inference approaches have rendered large, previously intractable probabilistic inference problems quickly solvable by handling whole sets of indistinguishable objects together. Triggered by this success, we show that another important AI technique is liftable, too, namely linear programming. Intuitively, given a linear program (LP), we employ a lifted variant of Gaussian belief propagation (GaBP) to solve the systems of linear equations arising when running an interiorpoint method to solve the LP. However, this naïve solution cannot make use of standard solvers for linear equations and is doomed to construct lifted networks in each iteration of the interior-point method again, an operation that can itself be quite costly. To address both issues, we show how to read off an equivalent LP from the lifted GaBP computations that can be solved using any off-the-shelf LP solver. We prove the correctness of this compilation approac and experimentally demonstrate that it can greatly reduce the cost of solving LPs.