  Linear Programming (LP) relaxations have become powerful tools for finding
the most probable (MAP) configuration in graphical models. These relaxations
can be solved efficiently using message-passing algorithms such as belief
propagation and, when the relaxation is tight, provably find the MAP
configuration. The standard LP relaxation is not tight enough in many
real-world problems, however, and this has lead to the use of higher order
cluster-based LP relaxations. The computational cost increases exponentially
with the size of the clusters and limits the number and type of clusters we can
use. We propose to solve the cluster selection problem monotonically in the
dual LP, iteratively selecting clusters with guaranteed improvement, and
quickly re-solving with the added clusters by reusing the existing solution.
Our dual message-passing algorithm finds the MAP configuration in protein
sidechain placement, protein design, and stereo problems, in cases where the
standard LP relaxation fails.
