Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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.
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}
