Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Journal article
Title: Efficient semidefinite branch-and-cut for MAP-MRF inference
Author: Wang, P.
Shen, C.
van den Hengel, A.
Torr, P.
Citation: International Journal of Computer Vision, 2016; 117(3):269-289
Publisher: Springer US
Issue Date: 2016
ISSN: 0920-5691
Statement of
Peng Wang, Chunhua Shen, Anton van den Hengel, Philip H. S. Torr
Abstract: 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.
Keywords: MAP inference; Markov random field; semidefinite programming; branch and cut
Description: Published online: 24 October 2015
Rights: © Springer Science+Business Media New York 2015
RMID: 0030038363
DOI: 10.1007/s11263-015-0865-2
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_106855.pdfRestricted Access1.21 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.