Theoretical CSPs where (in)equality constraints can be expressed as a single constraint?

Question

I'm designing puzzles by running a MAX-CSP solver, and it works nicely in practice. For concreteness, my problems have the following form (in a pseudo-modeling language):

# set up vars & their domains
x_1 {1}
x_2 {0,1}
x_3 {0}
x_4 {0,1}
# constraints
(x_1 != x_2)
(x_2 = x_3)
(x_3 = x_4)
(x_1 != x_4)
(x_2 = x_4)

The objective is then to choose values from the domains of each variable so as to maximize the number of constraints satisfied.

More generally, in all of my instances, we have a fixed value of $k$. The domain of each variable is of size at most $k$. Every constraint involves two variables, and is an inequality or an equality constraint.

When CSPs are studied from a theoretical viewpoint, is there a model that captures the above in a straightforward way?

Answer 1

In complexity theory, CSPs are usually specified as a set of allowed predicates. If the (finite) domain is $D$, a predicate of arity $d$ is an arbitrary subset of $D^d$ of allowed values. In particular, equality (or inequality) is a predicate of arity 2.

This is the point of view taken in Schaefer's dichotomy theorem as well as the more recent universal algebra approach (see for example a short survey by Libor Barto). Another example is the celebrated Raghavendra's theorem, which states that assuming the unique games conjecture, every CSP can be approximated optimally using semidefinite programming.