Haller, Stefan
Stefan
Haller
Swoboda, Paul
Paul
Swoboda
Savchynskyy, Bogdan
Bogdan
Savchynskyy
Exact MAP-inference by confining combinatorial search with LP relaxation
AAAI
2018
2019-02-13T13:32:48Z
2019-08-02T12:39:07Z
conference
https://research-explorer.app.ist.ac.at/record/5978
https://research-explorer.app.ist.ac.at/record/5978.json
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.