# Constraint *NoOverlap*

The one dimensional form of constraint *NoOverlap*, also called *Disjunctive* in the literature ensures that some objects (e.g., tasks), defined by their origins (e.g., starting times) and lengths (e.g., durations), must not overlap.

The k-dimensional form of constraint *NoOverlap*, also called *diffn*, ensures that, given a set of $k$-dimensional boxes; for any pair of such boxes, there exists at least one dimension where one box is after the other, i.e., the boxes do not overlap.

In PyCSP$^3$, we must call the function *NoOverlap()* that requires either two named parameters called *origins* and *lengths* or, equivalently, a named parameter called *tasks*. It is also posible to use an optional parameter called *zero_ignored*.

Below, we give several illustrations corresponding to representative use cases of the constraint *NoOverlap*.

## Case 1: NoOverlap with Fixed Lengths

The first case if about the one dimensional form with lengths given by constants (integers).

The arguments given to *origins* and *lengths* when calling the function *NoOverlap()* are expected to be lists of the same length; *origins* must be given a list of variables whereas * must be given a list of integers.

To see how this constraint works, we need first to import the library PyCSP$^3$:

```
from pycsp3 import *
```

For our illustration, we introduce an array $x$ of 4 variables, each one with {0,1,2,3,4,5,6,7,8,9} as domain. We can imagine that $x$ represents the starting times of 4 tasks.

```
x = VarArray(size=4, dom=range(10))
```

We can display (the structure of) the array as well as the domain of the first variable.

```
print("Array of variable x: ", x)
print("Domain of any variable: ", x[0].dom)
```

```
Array of variable x: [x[0], x[1], x[2], x[3]]
Domain of any variable: 0..9
```

Then, for the durations, we introduce an array $t$.

```
t = [3,5,2,4]
```

We simply post a single constraint *NoOverlap* from $x$ and $t$.

```
satisfy(
NoOverlap(origins=x, lengths=t)
);
```

Interestingly, we can display the internal representation of the posted constraints; we can see that the information is correctly recorded.

```
print(posted())
```

```
noOverlap(origins:[x[0], x[1], x[2], x[3]], lengths:[3, 5, 2, 4])
```

By calling the function *solve()*, we can check that the problem (actually, the single constraint) is satisfiable (SAT). We can also print the values assigned to the variables in the found solution; we can call the function *values()* that collects the values assigned (in the last found solution) to a specified list of variables.

```
if solve() is SAT:
for i in range(4):
print(f"Task {i} starts at {value(x[i])} and lasts {t[i]} unit(s) of time")
```

```
Task 0 starts at 0 and lasts 3 unit(s) of time
Task 1 starts at 9 and lasts 5 unit(s) of time
Task 2 starts at 3 and lasts 2 unit(s) of time
Task 3 starts at 5 and lasts 4 unit(s) of time
```

One can enumerate the 30 solutions as follows:

```
if solve(sols=ALL) is SAT:
for i in range(n_solutions()):
print(f"Solution {i+1}: {values(x, sol=i)}")
```

```
Solution 1: [0, 9, 3, 5]
Solution 2: [0, 9, 7, 3]
Solution 3: [4, 9, 7, 0]
Solution 4: [6, 9, 4, 0]
Solution 5: [6, 9, 0, 2]
Solution 6: [2, 9, 0, 5]
```

An alternative for posting the constraint is to use the named parameter *tasks* as follows. The reader can check it.

```
satisfy(
NoOverlap(tasks=[(x[i],t[i]) for i in range(4)])
);
```

## Case 2: NoOverlap with Variable Lengths

The second case if about the one dimensional form with lengths given by variables.

The arguments given to *origins* and *lengths* when calling the function *NoOverlap()* are expected to be lists of the same length; *origins* and *lengths* must be given a list of variables.

To start, we remove the last posted constraint by calling the function *unpost()*.

```
unpost()
```

We control that there are no more constraints.

```
print(posted())
```

```
[]
```

In addition to the array $x$, we introduce an array $y$ of 4 variables, each one with {3,4,5} as domain; the variables of $x$ will represent the durations of the 4 tasks.

```
y = VarArray(size=4, dom=range(3,6))
```

We post a single constraint *NoOverlap* from $x$ and $y$.

```
satisfy(
NoOverlap(origins=x, lengths=y)
);
```

We can call the solver.

```
if solve() is SAT:
for i in range(4):
print(f"Task {i} starts at {value(x[i])} and lasts {value(y[i])} unit(s) of time")
```

```
Task 0 starts at 0 and lasts 3 unit(s) of time
Task 1 starts at 3 and lasts 3 unit(s) of time
Task 2 starts at 6 and lasts 3 unit(s) of time
Task 3 starts at 9 and lasts 3 unit(s) of time
```

We can enumerate the 20 first solutions.

```
if solve(sols=20) is SAT:
for i in range(n_solutions()):
print(f"Solution {i+1}: {values(x, sol=i)} {values(y, sol=i)}")
```

```
Solution 1: [0, 3, 6, 9] [3, 3, 3, 3]
Solution 2: [0, 3, 6, 9] [3, 3, 3, 4]
Solution 3: [0, 3, 6, 9] [3, 3, 3, 5]
Solution 4: [0, 3, 9, 6] [3, 3, 3, 3]
Solution 5: [0, 3, 9, 6] [3, 3, 4, 3]
Solution 6: [0, 3, 9, 6] [3, 3, 5, 3]
Solution 7: [0, 9, 3, 6] [3, 3, 3, 3]
Solution 8: [0, 9, 3, 6] [3, 4, 3, 3]
Solution 9: [0, 9, 3, 6] [3, 5, 3, 3]
Solution 10: [0, 9, 6, 3] [3, 5, 3, 3]
Solution 11: [0, 9, 6, 3] [3, 3, 3, 3]
Solution 12: [0, 9, 6, 3] [3, 4, 3, 3]
Solution 13: [0, 6, 9, 3] [3, 3, 3, 3]
Solution 14: [0, 6, 9, 3] [3, 3, 4, 3]
Solution 15: [0, 6, 9, 3] [3, 3, 5, 3]
Solution 16: [0, 6, 3, 9] [3, 3, 3, 3]
Solution 17: [0, 6, 3, 9] [3, 3, 3, 4]
Solution 18: [0, 6, 3, 9] [3, 3, 3, 5]
Solution 19: [6, 0, 3, 9] [3, 3, 3, 5]
Solution 20: [6, 0, 3, 9] [3, 3, 3, 3]
```

## Case 3: Multi-dimensional NoOverlap with Fixed Lengths

The third case if about the two-dimensional form with lengths given by constants (integers).

The arguments given to *origins* and *lengths* when calling the function *NoOverlap()* are expected to be two-dimensional lists of the same length; *origins* and *lengths* must be given a list of pairs (i.e., lists or tuples of length 2) of variables.

First of all, we need to remove everything that has been introduced so far.

```
clear() # to clear previously posted variables and constraints
```

We introduce a two-dimensional array $t$ of $4 \times 2$ variables, each one with {0,1,2,3,4,5} as domain. For each task of index $i$, $t[i][0]$ and $t[i][1]$ can represent the origin (starting place) along two axes (of indexes 0 and 1).

```
t = VarArray(size=[4,2], dom=range(5))
```

We can display the structure of the array $t$.

```
print(t)
```

```
[
[t[0][0], t[0][1]]
[t[1][0], t[1][1]]
[t[2][0], t[2][1]]
[t[3][0], t[3][1]]
]
```

We introduce a two-dimensional array $d$ of $4 \times 2$ integers.

```
d = [[5,4], [2,3], [3,2], [3,4]]
```

We simply post a single two-dimensional constraint *NoOverlap* from $t$ and $d$.

```
satisfy(
NoOverlap(origins=t, lengths=d)
);
```

We can run the solver. The interested reader can check that there is no overlapping between the boxes (rectangles).

```
if solve() is SAT:
print(values(t))
```

```
[
[2, 4]
[0, 2]
[0, 0]
[3, 0]
]
```

One can compute the number of solutions (supports) for that constraint.

```
if solve(sols=ALL) is SAT:
print(n_solutions())
```

```
1024
```

## Case 4: Multi-dimensional NoOverlap with Variable Lengths

The fourth case if about the two-dimensional form with lengths given by variables.

To start, we remove the last posted constraint by calling the function *unpost()*.

```
unpost()
```

In addition to the array $t$, we introduce an array $y$ of $4 \times 2$ variables, each one with {3,4,5} as domain; the variables of $y$ will represent the durations over the two dimensions of the 4 tasks.

```
y = VarArray(size=[4,2], dom=range(3,6))
```

We post the constraint:

```
satisfy(
NoOverlap(origins=t, lengths=y)
);
```

We display the first found solution (support):

```
if solve() is SAT:
print(values(t), values(y))
```

```
[
[0, 0]
[0, 3]
[3, 0]
[3, 3]
] [
[3, 3]
[3, 3]
[3, 3]
[3, 3]
]
```