# Circuit constraint leading to infeasibility if there are 0 jobs producable one a machine

Using the CP-SAT Solver:

My Model turns infeasible whenever there is no job available for a machine. Not every job can be built on every machine. Example Situtations:

• Less jobs than machines
• No jobs buildable on a specific machine

I have tracked down the problem to be in my circuit constraint. When i remove the AddCircuit, it works fine. But I cant tell where exactly the problem is.

seq_length being an NewIntVar (0,max_sequence,name) to handle the max number of similar products in sequence.

Job n is scheduled on machine m if x[n,m]

for line in all_lines:
job_starts = [job for job in task_per_line[line]]
job_ends = [job for job in task_per_line[line]]
arcs = []
for j1 in all_orders:
# Initial arc from the dummy node (0) to a task.
start_lit = model.NewBoolVar('%i is first job on line %i' % (j1, line))
arcs.append([0, j1 + 1, start_lit]

# Final arc from an arc to the dummy node.
isLast = model.NewBoolVar('%i is last job on line %i' % (j1, line))
arcs.append([j1 + 1, 0, isLast])

# initializing seq lengths
for j2 in all_orders:
if j1 == j2:
arcs.append([j1 + 1, j1 + 1, x[j1, line].Not()])
continue
lit = model.NewBoolVar('%i follows %i on line %i' % (j2, j1, line))
arcs.append([j1 + 1, j2 + 1, lit])

# Respecting max sequence
if same_product:
model.Add(seq_lengths[j2, line] == seq_lengths[j1, line] + 1).OnlyEnforceIf(lit)
else:


you need to add a self arc 0 -> 0 with a Boolean variable indicating if the circuit is empty.

for line in all_lines:
job_starts = [job for job in task_per_line[line]]
job_ends = [job for job in task_per_line[line]]
arcs = []
for j1 in all_orders:
# Initial arc from the dummy node (0) to a task.
start_lit = model.NewBoolVar('%i is first job on line %i' % (j1, line))
arcs.append([0, j1 + 1, start_lit]

# Final arc from an arc to the dummy node.
isLast = model.NewBoolVar('%i is last job on line %i' % (j1, line))
arcs.append([j1 + 1, 0, isLast])

# initializing seq lengths
for j2 in all_orders:
if j1 == j2:
arcs.append([j1 + 1, j1 + 1, x[j1, line].Not()])
continue
lit = model.NewBoolVar('%i follows %i on line %i' % (j2, j1, line))
$$$$
`