TY - JOUR
AU - Haller, Stefan
AU - Swoboda, Paul
AU - Savchynskyy, Bogdan
PY - 2018/04/26
Y2 - 2024/08/11
TI - Exact MAP-Inference by Confining Combinatorial Search With LP Relaxation
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 32
IS - 1
SE - Main Track: Search and Constraint Satisfaction
DO - 10.1609/aaai.v32i1.12202
UR - https://ojs.aaai.org/index.php/AAAI/article/view/12202
SP -
AB - <p> We consider the MAP-inference problem for graphical models, which is a valued constraint satisfaction problem defined on real numbers with a natural summation operation. We propose a family of relaxations (different from the famous Sherali-Adams hierarchy), which naturally define lower bounds for its optimum. This family always contains a tight relaxation and we give an algorithm able to find it and therefore, solve the initial non-relaxed NP-hard problem. The relaxations we consider decompose the original problem into two non-overlapping parts: an easy LP-tight part and a difficult one. For the latter part a combinatorial solver must be used. As we show in our experiments, in a number of applications the second, difficult part constitutes only a small fraction of the whole problem. This property allows to significantly reduce the computational time of the combinatorial solver and therefore solve problems which were out of reach before. </p>
ER -