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

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?

• @AlwynMathew Please stop micro-managing formatting if it does not solve a problem. (Here, it actually made things worse, imho.) – Raphael Oct 26 '16 at 22:09
• @Raphael subscripts are not correctly displayed so I was trying to make that proper. – Alwyn Mathew Oct 27 '16 at 4:01
• @AlwynMathew I see. The pseudo code is very clear, though, even with pseudo subscripts. – Raphael Oct 27 '16 at 9:36

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.