  A popular class of algorithms to optimize the dual LP relaxation of the
discrete energy minimization problem (a.k.a.\ MAP inference in graphical models
or valued constraint satisfaction) are convergent message-passing algorithms,
such as max-sum diffusion, TRW-S, MPLP and SRMP. These algorithms are
successful in practice, despite the fact that they are a version of coordinate
minimization applied to a convex piecewise-affine function, which is not
guaranteed to converge to a global minimizer. These algorithms converge only to
a local minimizer, characterized by local consistency known from constraint
programming. We generalize max-sum diffusion to a version of coordinate
minimization applicable to an arbitrary convex piecewise-affine function, which
converges to a local consistency condition. This condition can be seen as the
sign relaxation of the global optimality condition.
