How to model a set of integer variables getting assigned different values than another set of integer variables

Question

Assume we have variables $x_1, x_2, x_3, x_4$ that each can belong to $\{1,2,...,10\}$. How can we model a constraint that variables $x_1, x_2$ get assigned different values than $x_3, x_4$?

Because of scaling issue, it is not efficient to enumerate all assignment combinations as $\\x_1 \neq x_3, \quad x_1 \neq x_4, \quad x_2 \neq x_3, \quad x_2 \neq x_4$.

I am using OR-Tools CP-SAT.

Answer 1

If you mean $(x_1,x_2)\not=(x_3,x_4)$, you can enforce this with: $$10(x_1-1) + (x_2-1) \not= 10(x_3-1)+(x_4-1)$$ Equivalently: $$10x_1 + x_2 \not= 10x_3+x_4 \tag1$$

---

If instead you meant the four disequalities you listed, you can impose $$(x_1 - x_3)(x_1 - x_4)(x_2 - x_3)(x_2 - x_4)\not=0$$ Alternatively, you might consider generating your four disequalities dynamically only if they are violated. In this case, $(1)$ is still valid but is only a relaxation.

---

Here's a MILP formulation. Let binary variable $y_{i,j}$ indicate whether $x_i=j$, and let binary variable $z_{g,j}$ indicate whether any variable in group $g$ is assigned value $j$. Then your constraints are \begin{align} \sum_j y_{i,j} &= 1 &&\text{for $i\in\{1,\dots,1000\}$} \\ \sum_j j y_{i,j} &= x_i &&\text{for $i\in\{1,\dots,1000\}$} \\ y_{i,j} &\le z_{g,j} &&\text{for $g\in\{1,2\}$, $i$ in group $g$, and $j\in\{1,\dots,10\}$} \\ \sum_g z_{g,j} &\le 1 &&\text{for $j\in\{1,\dots,10\}$} \end{align}