Revisiting the Linear Programming Relaxation Approach to Gibbs Energy Minimization and Weighted Constraint Satisfaction

We present a number of contributions to the LP relaxation
approach to weighted constraint satisfaction (= Gibbs energy
minimization). We link this approach to many works from
constraint programming, which relation has so far been ignored in
machine vision and learning. While the approach has been mostly
considered only for binary constraints, we generalize it to n-ary
constraints in a simple and natural way. This includes a simple
algorithm to minimize the LP-based upper bound, n-ary max-sum
diffusion -- however, we consider using other bound-optimizing
algorithms as well. The diffusion iteration is tractable for a
certain class of high-arity constraints represented as a
black-box, which is analogical to propagators for global
constraints CSP. Diffusion exactly solves permuted n-ary
supermodular problems. A hierarchy of gradually tighter LP
relaxations is obtained simply by adding various zero constraints
and coupling them in various ways to existing constraints. Zero
constraints can be added incrementally, which leads to a cutting
plane algorithm. The separation problem is formulated as finding
an unsatisfiable subproblem of a CSP.