TY - GEN
T1 - Belief propagation for linear programming
AU - Gelfand, Andrew E.
AU - Shin, Jinwoo
AU - Chertkov, Michael
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84890342270&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84890342270&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2013.6620626
DO - 10.1109/ISIT.2013.6620626
M3 - Conference contribution
AN - SCOPUS:84890342270
SN - 9781479904464
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 2249
EP - 2253
BT - 2013 IEEE International Symposium on Information Theory, ISIT 2013
T2 - 2013 IEEE International Symposium on Information Theory, ISIT 2013
Y2 - 7 July 2013 through 12 July 2013
ER -