2014/04/20 by Peng Wang, Wang, Peng, Chunhua Shen +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Neural Network Applications #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #FOS: Mathematics #Genomics and Chromatin Dynamics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Numerical Analysis (math.NA)
paper · pdf · doi:10.48550/arxiv.1404.5009
openalex publication_date 2014/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.