@inproceedings{5978,
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.},
author = {Haller, Stefan and Swoboda, Paul and Savchynskyy, Bogdan},
booktitle = {Proceedings of the 32st AAAI Conference on Artificial Intelligence},
location = {New Orleans, LU, United States},
pages = {6581--6588},
publisher = {AAAI},
title = {{Exact MAP-inference by confining combinatorial search with LP relaxation}},
year = {2018},
}