[Python] Constraints: AddNoOverlap with OnlyEnforceIf

I have set of tasks in a constraint satisfaction problem. These tasks are using a centrifuge. So if they overlap, then they must overlap completely (I can't add tasks while the centrifuge is spinning).

So I want to constrain the tasks that if they overlap, then the start times must be equal, otherwise they must not overlap.

If I try:

from ortools.sat.python import cp_model
import collections
model = cp_model.CpModel()

# Named tuple to store information about created variables.
task_type = collections.namedtuple("task_type", "start end interval")

# Create tasks
task1_start = model.NewIntVar(0, 10, 'task1_start')
task1_end = model.NewIntVar(0, 10, 'task1_end')
task1_interval = model.NewIntervalVar(task1_start, 5, task1_end, 'task1_interval')
task1 = task_type(start=task1_start, end=task1_end, interval=task1_interval)


task2_start = model.NewIntVar(0, 10, 'task2_start')
task2_end = model.NewIntVar(0, 10, 'task2_end')
task2_interval = model.NewIntervalVar(task2_start, 5, task2_end, 'task2_interval')
task2 = task_type(start=task2_start, end=task2_end, interval=task2_interval)


# Create centrifuge tasks
centrifuge_tasks = [task1,task2]

# Add overlap constraints
for i, cent_a in enumerate(centrifuge_tasks):
for j, cent_b in enumerate(centrifuge_tasks):
if i < j:
b = model.NewBoolVar(f"centrifuge_overlap_{cent_a.interval.name}_{cent_b.interval.name}")

model.Add(cent_a.start == cent_b.start).OnlyEnforceIf(b)
model.AddNoOverlap([cent_a.interval, cent_b.interval]).OnlyEnforceIf(~b)

# Solve the model
solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.FEASIBLE or status == cp_model.OPTIMAL:
print("Task 1 start:", solver.Value(task1_start))
print("Task 2 start:", solver.Value(task2_start))
else:
print("No solution found")


It returns:

No solution found


I found a way around this by using:

from ortools.sat.python import cp_model
import collections
model = cp_model.CpModel()

# Named tuple to store information about created variables.
task_type = collections.namedtuple("task_type", "start end interval")

# Create tasks
task1_start = model.NewIntVar(0, 10, 'task1_start')
task1_end = model.NewIntVar(0, 10, 'task1_end')
task1_interval = model.NewIntervalVar(task1_start, 5, task1_end, 'task1_interval')
task1 = task_type(start=task1_start, end=task1_end, interval=task1_interval)


task2_start = model.NewIntVar(0, 10, 'task2_start')
task2_end = model.NewIntVar(0, 10, 'task2_end')
task2_interval = model.NewIntervalVar(task2_start, 5, task2_end, 'task2_interval')
task2 = task_type(start=task2_start, end=task2_end, interval=task2_interval)


# Create centrifuge tasks
centrifuge_tasks = [task1,task2]

# Add overlap constraints
for i, cent_a in enumerate(centrifuge_tasks):
for j, cent_b in enumerate(centrifuge_tasks):
if i < j:
b = model.NewBoolVar(f"centrifuge_overlap_{cent_a.interval.name}_{cent_b.interval.name}")
b_order = model.NewBoolVar(f"centrifuge_order_{cent_a.interval.name}_{cent_b.interval.name}")

model.Add(cent_a.start == cent_b.start).OnlyEnforceIf(b)

model.Add(cent_a.end <= cent_b.start).OnlyEnforceIf(~b, b_order)
model.Add(cent_b.end <= cent_a.start).OnlyEnforceIf(~b, ~b_order)

# Solve the model
solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.FEASIBLE or status == cp_model.OPTIMAL:
print("Task 1 start:", solver.Value(task1_start))
print("Task 2 start:", solver.Value(task2_start))
else:
print("No solution found")


Which returns:

Task 1 start: 0
Task 2 start: 0


But my question is why doesn't work with the AddNoOverlap constraint?

Continue reading...