The LP relaxation approach to weighted constraint satisfaction (Gibbs energy minimization) has been mostly considered only for binary (= pairwise) problems. We present its generalization to n-ary problems which is simple and natural. This includes a simple algorithm to minimize the LP-based upper bound, n-ary max-sum diffusion; however, other bound-optimizing algorithms can be used as well. The diffusion iteration is tractable for a certain class of high-arity constraints represented as a black-box function. 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. We give conditions on when adding a set of cutting planes leads to a better relaxation – in particular, this is so if the sub-CSP induced by it has no solution. Throughout the text, we relate Gibbs energy minimization to many works from constraint programming, which relation has so far been ignored in computer vision and machine learning.