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

Question

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[0] for job in task_per_line[line]]
            job_ends = [job[1] 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])

                model.AddImplication(x[j1, line].Not(), start_lit.Not())
                model.AddImplication(x[j1, line].Not(), isLast.Not())
                model.Add(job_starts[j1] == 0).OnlyEnforceIf([start_lit])

                # initializing seq lengths
                model.Add(seq_lengths[j1, line] == 1).OnlyEnforceIf(start_lit)
                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))
                    model.AddImplication(lit, x[j1, line])
                    model.AddImplication(lit, x[j2, line])
                    arcs.append([j1 + 1, j2 + 1, lit])
                    model.Add(job_starts[j2] == job_ends[j1] ).OnlyEnforceIf(lit)

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

Answer 1

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

For for all tasks, add the implication (circuit is empty => task is not performed).

for line in all_lines:
            job_starts = [job[0] for job in task_per_line[line]]
            job_ends = [job[1] for job in task_per_line[line]]
            arcs = []
            no_tasks = model.NewBoolVar(f'no_tasks in {line}')
            arcs.append([0, 0, no_tasks])
            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])

                model.AddImplication(x[j1, line].Not(), start_lit.Not())
                model.AddImplication(x[j1, line].Not(), isLast.Not())
                model.Add(job_starts[j1] == 0).OnlyEnforceIf([start_lit])

                # link with no_tasks
                model.AddImplication(no_tasks, x[j1, line].Not())

                # initializing seq lengths
                model.Add(seq_lengths[j1, line] == 1).OnlyEnforceIf(start_lit)
                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))
                    model.AddImplication(lit, x[j1, line])
                    model.AddImplication(lit, x[j2, line])
                    arcs.append([j1 + 1, j2 + 1, lit])
                    model.Add(job_starts[j2] == job_ends[j1] ).OnlyEnforceIf(lit)

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