Exact MAP-inference by confining combinatorial search with LP relaxation

S. Haller, P. Swoboda, B. Savchynskyy, in:, Proceedings of the 32st AAAI Conference on Artificial Intelligence, AAAI, 2018, pp. 6581–6588.

Download
No fulltext has been uploaded. References only!
Conference Paper | Published | English
Author
; ;
Department
Abstract
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.
Publishing Year
Date Published
2018-02-01
Proceedings Title
Proceedings of the 32st AAAI Conference on Artificial Intelligence
Page
6581-6588
Conference
AAAI: Conference on Artificial Intelligence
Conference Location
New Orleans, LU, United States
Conference Date
2018-02-02 – 2018-02-07
IST-REx-ID

Cite this

Haller S, Swoboda P, Savchynskyy B. Exact MAP-inference by confining combinatorial search with LP relaxation. In: Proceedings of the 32st AAAI Conference on Artificial Intelligence. AAAI; 2018:6581-6588.
Haller, S., Swoboda, P., & Savchynskyy, B. (2018). Exact MAP-inference by confining combinatorial search with LP relaxation. In Proceedings of the 32st AAAI Conference on Artificial Intelligence (pp. 6581–6588). New Orleans, LU, United States: AAAI.
Haller, Stefan, Paul Swoboda, and Bogdan Savchynskyy. “Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation.” In Proceedings of the 32st AAAI Conference on Artificial Intelligence, 6581–88. AAAI, 2018.
S. Haller, P. Swoboda, and B. Savchynskyy, “Exact MAP-inference by confining combinatorial search with LP relaxation,” in Proceedings of the 32st AAAI Conference on Artificial Intelligence, 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. Proceedings of the 32st AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence 6581–6588.
Haller, Stefan, et al. “Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation.” Proceedings of the 32st AAAI Conference on Artificial Intelligence, AAAI, 2018, pp. 6581–88.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar