Efficient Semidefinite Branch-and-Cut for MAP-MRF Inference
This addresses inference in Markov Random Fields for applications like computer vision, but it is incremental as it builds on existing Branch-and-Cut and SDP techniques.
The paper tackles the problem of MAP-MRF inference by proposing a Branch-and-Cut method with an efficient bounding procedure, achieving better approximation than state-of-the-art methods on challenging non-submodular problems within various time budgets.
We propose a Branch-and-Cut (B&C) method for solving general MAP-MRF inference problems. The core of our method is a very efficient bounding procedure, which combines scalable semidefinite programming (SDP) and a cutting-plane method for seeking violated constraints. In order to further speed up the computation, several strategies have been exploited, including model reduction, warm start and removal of inactive constraints. We analyze the performance of the proposed method under different settings, and demonstrate that our method either outperforms or performs on par with state-of-the-art approaches. Especially when the connectivities are dense or when the relative magnitudes of the unary costs are low, we achieve the best reported results. Experiments show that the proposed algorithm achieves better approximation than the state-of-the-art methods within a variety of time budgets on challenging non-submodular MAP-MRF inference problems.