2
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Yes, the partitions wouldn't necessarily be of the same size. $\endgroup$ – Mahmoud Oct 11 at 1:42
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
2
$\begingroup$

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$.

| improve this answer | |
$\endgroup$
2
$\begingroup$

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])
    model.AddLinearExpressionInDomain(x, si).OnlyEnforceIf(sx[i + 1])
    model.AddLinearExpressionInDomain(y, si).OnlyEnforceIf(sy[i + 1])
    model.AddBoolOr([sx[i + 1].Not(), sy[i + 1].Not()])

model.Add(sum(sx.values()) == 1)
model.Add(sum(sy.values()) == 1)

solver.Solve(model)
print(solver.Value(x))
print(solver.Value(y))
| improve this answer | |
$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Mahmoud Oct 11 at 1:35
  • $\begingroup$ You can use Domain.FromValues in that case $\endgroup$ – Stradivari Oct 11 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.