Max-Product Belief Propagation for Linear Programming: Applications to
  Combinatorial Optimization
  The max-product {belief propagation} (BP) is a popular message-passing
heuristic for approximating a maximum-a-posteriori (MAP) assignment in a joint
distribution represented by a graphical model (GM). In the past years, it has
been shown that BP can solve a few classes of linear programming (LP)
formulations to combinatorial optimization problems including maximum weight
matching, shortest path and network flow, i.e., BP can be used as a
message-passing solver for certain combinatorial optimizations. However, those
LPs and corresponding BP analysis are very sensitive to underlying problem
setups, and it has been not clear what extent these results can be generalized
to. In this paper, we obtain a generic criteria that BP converges to the
optimal solution of given LP, and show that it is satisfied in LP formulations
associated to many classical combinatorial optimization problems including
maximum weight perfect matching, shortest path, traveling salesman, cycle
packing, vertex/edge cover and network flow.
