Exact MAP-Inference by Confining Combinatorial Search With LP Relaxation

Authors

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

Keywords:

MAP-inference, energy minimization, graphical models, relaxation

Abstract

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.

Downloads

Published

2018-04-26

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). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/12202

Issue

Section

Main Track: Search and Constraint Satisfaction