Link Search Menu Expand Document
PyCSP3
Models & Data GitHub XCSP3 About

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]
]