Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation

arXiv2004.06370MaRDI QIDQ6338654

Author name not available (Why is that?)

Publication date: 14 April 2020

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.

Has companion code repository: https://github.com/fgrsnau/combilp

This page was built for publication: Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6338654)