conference paper
Exact MAP-inference by confining combinatorial search with LP relaxation
published
yes
Stefan
Haller
author
Paul
Swoboda
author 446560C6-F248-11E8-B48F-1D18A9856A87
Bogdan
Savchynskyy
author
VlKo
department
AAAI: Conference on Artificial Intelligence
We consider the MAP-inference problem for graphical models,which is a valued constraint satisfaction problem defined onreal numbers with a natural summation operation. We proposea family of relaxations (different from the famous Sherali-Adams hierarchy), which naturally define lower bounds for itsoptimum. This family always contains a tight relaxation andwe give an algorithm able to find it and therefore, solve theinitial non-relaxed NP-hard problem.The relaxations we consider decompose the original probleminto two non-overlapping parts: an easy LP-tight part and adifficult one. For the latter part a combinatorial solver must beused. As we show in our experiments, in a number of applica-tions the second, difficult part constitutes only a small fractionof the whole problem. This property allows to significantlyreduce the computational time of the combinatorial solver andtherefore solve problems which were out of reach before.
AAAI2018New Orleans, LU, United States
eng
Proceedings of the 32st AAAI Conference on Artificial Intelligence
6581-6588
S. Haller, P. Swoboda, B. Savchynskyy, in:, Proceedings of the 32st AAAI Conference on Artificial Intelligence, AAAI, 2018, pp. 6581–6588.
Haller S, Swoboda P, Savchynskyy B. Exact MAP-inference by confining combinatorial search with LP relaxation. In: <i>Proceedings of the 32st AAAI Conference on Artificial Intelligence</i>. AAAI; 2018:6581-6588.
Haller, Stefan, et al. “Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation.” <i>Proceedings of the 32st AAAI Conference on Artificial Intelligence</i>, AAAI, 2018, pp. 6581–88.
Haller, Stefan, Paul Swoboda, and Bogdan Savchynskyy. “Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation.” In <i>Proceedings of the 32st AAAI Conference on Artificial Intelligence</i>, 6581–88. AAAI, 2018.
Haller S, Swoboda P, Savchynskyy B. 2018. Exact MAP-inference by confining combinatorial search with LP relaxation. Proceedings of the 32st AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence 6581–6588.
S. Haller, P. Swoboda, and B. Savchynskyy, “Exact MAP-inference by confining combinatorial search with LP relaxation,” in <i>Proceedings of the 32st AAAI Conference on Artificial Intelligence</i>, New Orleans, LU, United States, 2018, pp. 6581–6588.
Haller, S., Swoboda, P., & Savchynskyy, B. (2018). Exact MAP-inference by confining combinatorial search with LP relaxation. In <i>Proceedings of the 32st AAAI Conference on Artificial Intelligence</i> (pp. 6581–6588). New Orleans, LU, United States: AAAI.
59782019-02-13T13:32:48Z2019-08-02T12:39:07Z