# 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, 2016 at 22:09
• @Raphael subscripts are not correctly displayed so I was trying to make that proper. Oct 27, 2016 at 4:01
• @AlwynMathew I see. The pseudo code is very clear, though, even with pseudo subscripts.
– Raphael
Oct 27, 2016 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.