Skip to main content

Belief propagation for linear programming

Publication ,  Conference
Gelfand, AE; Shin, J; Chertkov, M
Published in: IEEE International Symposium on Information Theory - Proceedings
December 19, 2013

Belief Propagation (BP) is a popular, distributed heuristic for performing MAP computations in Graphical Models. BP can be interpreted, from a variational perspective, as minimizing the Bethe Free Energy (BFE). BP can also be used to solve a special class of Linear Programming (LP) problems. For this class of problems, MAP inference can be stated as an integer LP with an LP relaxation that coincides with minimization of the BFE at 'zero temperature'. We generalize these prior results and establish a tight characterization of the LP problems that can be formulated as an equivalent LP relaxation of MAP inference. Moreover, we suggest an efficient, iterative annealing BP algorithm for solving this broader class of LP problems. We demonstrate the algorithm's performance on a set of weighted matching problems by using it as a cutting plane method to solve a sequence of LPs tightened by adding 'blossom' inequalities. © 2013 IEEE.

Duke Scholars

Published In

IEEE International Symposium on Information Theory - Proceedings

DOI

ISSN

2157-8095

ISBN

9781479904464

Publication Date

December 19, 2013

Start / End Page

2249 / 2253
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Gelfand, A. E., Shin, J., & Chertkov, M. (2013). Belief propagation for linear programming. In IEEE International Symposium on Information Theory - Proceedings (pp. 2249–2253). https://doi.org/10.1109/ISIT.2013.6620626
Gelfand, A. E., J. Shin, and M. Chertkov. “Belief propagation for linear programming.” In IEEE International Symposium on Information Theory - Proceedings, 2249–53, 2013. https://doi.org/10.1109/ISIT.2013.6620626.
Gelfand AE, Shin J, Chertkov M. Belief propagation for linear programming. In: IEEE International Symposium on Information Theory - Proceedings. 2013. p. 2249–53.
Gelfand, A. E., et al. “Belief propagation for linear programming.” IEEE International Symposium on Information Theory - Proceedings, 2013, pp. 2249–53. Scopus, doi:10.1109/ISIT.2013.6620626.
Gelfand AE, Shin J, Chertkov M. Belief propagation for linear programming. IEEE International Symposium on Information Theory - Proceedings. 2013. p. 2249–2253.

Published In

IEEE International Symposium on Information Theory - Proceedings

DOI

ISSN

2157-8095

ISBN

9781479904464

Publication Date

December 19, 2013

Start / End Page

2249 / 2253