About circuit constraints in OR - tools

Question

I am trying to implement a scheduling problem to solve with CP-SAT from OR-tools. There, in particular, for every machine I want to add a time transition constraint from every task that is performed on that machine to whatever its successor task is on the machine. For that, I found out I need to use a circuit constraint. This of course makes sense: we can construct a graph whose nodes are the tasks that can be performed on that machine (together with an additional dummy node to separate the start from end) and, once we have a Hamiltonian circuit there, the transition constraints can be defined since we know the successor of every task.

My problem lies on the fact that some of the tasks can be active on that machine or not. In my context, the task is identified by an OptionalInterval object, and thus I want to find the Hamiltonian circuit only over the complete subgraph whose nodes are those associated to tasks with active OptionalInterval. How can I accomplish this?

I checked the example provided here and I even closely followed the implementation but there only one task per job is considered and as soon as I add a task to a job the code breaks. Moreover, I know that I should use the AddCircuit method from cp-sat (python), but is unclear to me exactly what this constraint does. Could you please clarify? In the Python documentation of the function AddCircuit it is mentioned that

Adds Circuit(arcs).

Adds a circuit constraint from a sparse list of arcs that encode the graph.

A circuit is a unique Hamiltonian path in a subgraph of the total
graph. In case a node 'i' is not in the path, then there must be a
loop arc 'i -> i' associated with a true literal. Otherwise
this constraint will fail.

However, with that info it is unclear to me over which subgraph precisely is the circuit being considered. How is this subgraph defined?

I managed to get a minimal working example that turns out to be infeasible but should be feasible according to my understanding of the topic. There, I define a complete graph of 3 nodes, but one of the nodes (node 2) will not be active. I thus want to find a Hamiltonian circuit over the nodes 0 and 1, but apparently it doesn't exist.

model = cp_model.CpModel()

bool_node_active = {
    0: model.NewBoolVar("Is node 0 active"),
    1: model.NewBoolVar("Is node 1 active"),
    2: model.NewBoolVar("Is node 2 active")
}

model.Add(bool_node_active[2] == 0)

bool_arcs = {(i, j): model.NewBoolVar("") for i in range(3) for j in range(3)}

arcs = [
    [i, j, bool_arcs[i, j]] for i in range(3) for j in range(3)
]
for i in range(3):
    for j in range(3):
        model.AddImplication(bool_arcs[i, j], bool_node_active[i])
        model.AddImplication(bool_arcs[i, j], bool_node_active[j])
        

model.AddCircuit(arcs)

# Solve model.
solver = cp_model.CpSolver()

solution_printer = SolutionPrinter()
status = solver.Solve(model, solution_printer)

# Print Solution               
print('Solve status: %s' % solver.StatusName(status))    

Could you please fix the example above?

Answer 1

The graph is defined by the arcs you pass. An arc is (start node, end node, literal)

If the literal is true, the arc is selected.

The constraint enforces that:

• there is only one circuit of size > 1
• every node has 1 incoming arc and 1 outgoing arc

In other words, the constraint is circuit or sub-circuit in the CP literature.

To deal with optional nodes, one must add a self loop on the node. For instance, if node k is optional, and active only if literal lit is true, then the arc (k, k, lit.Not()) must be added to the constraint

Finally, in the scheduling example, one must deal with the case where the resource is empty (no tasks). So the case of the dummy node 0 must me treaded.

• a literal 'empty' must be created: empty = model.NewBoolVar('empty')
• a self loop on 0 must created: arc.append(0, 0, empty)
• if empty is true, all nodes are unperformed: for all node n, model.AddImplication(empty, performed(n).Not())