Exact MAP-Inference by Confining Combinatorial Search With LP Relaxation


  • Stefan Haller University of Heidelberg
  • Paul Swoboda IST Austria
  • Bogdan Savchynskyy University of Heidelberg




MAP-inference, energy minimization, graphical models, relaxation


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.




How to Cite

Haller, S., Swoboda, P., & Savchynskyy, B. (2018). Exact MAP-Inference by Confining Combinatorial Search With LP Relaxation. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.12202



Main Track: Search and Constraint Satisfaction