# How to model two variables to NOT to belong to the same set partition using Constraint Programming

Assume we have two variables $$x,y \in S$$ where $$S=\{1,2, \dots, 1000\}$$. Also, we are given a partition of set $$S$$ as:

$$S_1 = \{1,2, \dots, 249\}$$ $$,S_2 = \{250, \dots, 499\}$$ $$,S_3 = \{500, \dots, 749\}$$ $$,S_4 = \{750, \dots, 1000\}$$

How to model a constraint that prevents variables $$x$$ and $$y$$ both belonging to the same partition. That said, $$x=1$$, $$y = 2$$ is an invalid assignment but $$x=1$$, $$y = 250$$ is allowed.

I am using Google OR-Tools Constraint Programming.

(Please note the intersection of any two of the subsets is empty, and their union is the whole set. Each partition is not necessarily a full range of integers, unlike the example. For instance, $$S_1=\{1,\dots,249,750,\dots,1000\}, \quad S_2=\{250,\dots,749\}$$ is too a valid partition.)

• Yes, the partitions wouldn't necessarily be of the same size. – Mahmoud Oct 11 '20 at 1:42

Here's one way: $$x\not=i \lor y\not=j \text{ for } k\in\{1,2,3,4\}, i\in S_k, j\in S_k$$

Here's another way, using ELEMENT constraints, as suggested by @prubin. The following is SAS code, but maybe OR-Tools has something similar.

proc optmodel;
set S {k in 1..4} =
if      k = 1 then 1..249
else if k = 2 then 250..499
else if k = 3 then 500..749
else               750..1000;
num p {1..1000};
for {k in 1..4, i in S[k]} p[i] = k;

var X >= 1 <= 1000 integer;
var Y >= 1 <= 1000 integer;

var PX >= 1 <= 4 integer;
var PY >= 1 <= 4 integer;

/* PX = p[X] */
con ElementConX:
element(X, p, PX);
/* PY = p[Y] */
con ElementConY:
element(Y, p, PY);

con NotEqual:
PX ne PY;

solve;
print X Y PX PY;
quit;


The first solution found was

(X, Y, PX, PY) = (1, 250, 1, 2)


and specifying the FINDALLSOLNS option yields $$1000^2-249^2-250^2-250^2-251^2=749998$$ solutions, as expected.

I don't use OR-Tools, so I cannot be specific about syntax, but I'm pretty sure it has a table lookup constraint. So you can create a table that associates each value from 1 to 1,000 with its partition index (1 to 4), and then just add a constraint that says the partition value of $$x$$ cannot equal the partition value of $$y$$.

Using intermediate booleans and AddLinearExpressionInDomain you get:

from ortools.sat.python import cp_model

model = cp_model.CpModel()
solver = cp_model.CpSolver()

x = model.NewIntVar(1, 1000, "x")
y = model.NewIntVar(1, 1000, "y")

sx = {i: model.NewBoolVar(f"x in S{i}") for i in range(1, 5)}
sy = {i: model.NewBoolVar(f"y in S{i}") for i in range(1, 5)}
for i in range(4):
si = cp_model.Domain.FromFlatIntervals([250 * i, 250 * (i + 1) - 1])

• Thank you for the code snippet. One assumption I see you made is each domain $S_i$ is a full range of integers. However, the subsets could be from any partition of the full set. For instance, $S_1={1, 4, 7}, /quad S_2={2,3,5,12}$, then the sets are cannot be defined by range(start, end). – Mahmoud Oct 11 '20 at 1:35