Augmentative Message Passing for Traveling Salesman Problem and Graph
  Partitioning
  The cutting plane method is an augmentative constrained optimization
procedure that is often used with continuous-domain optimization techniques
such as linear and convex programs. We investigate the viability of a similar
idea within message passing -- which produces integral solutions -- in the
context of two combinatorial problems: 1) For Traveling Salesman Problem (TSP),
we propose a factor-graph based on Held-Karp formulation, with an exponential
number of constraint factors, each of which has an exponential but sparse
tabular form. 2) For graph-partitioning (a.k.a., community mining) using
modularity optimization, we introduce a binary variable model with a large
number of constraints that enforce formation of cliques. In both cases we are
able to derive surprisingly simple message updates that lead to competitive
solutions on benchmark instances. In particular for TSP we are able to find
near-optimal solutions in the time that empirically grows with N^3,
demonstrating that augmentation is practical and efficient.
