ORTools CP-SAT Solver. Constraint to require two lists of variables to be drawn from the same set of integers

Question

I have two lists of variables M and T. I would like to create a constraint where the set of unique values between M and T are identical.

From the solution variables I would like:

set(T) == set(M) -> True

So far, I have tried creating a matrix of the differences between each element of M and T

diffs = M[:, None] - T

Then building a constraint that the product of each element in individual row and every individual column of diffs is 0. This should ensure that each element of M has an element in T that it is equal to and vice versa.

for m in range(num_groups):
    model.AddMultiplicationEquality(0, diffs[m, :])
for t in range(num_groups):
    model.AddMultiplicationEquality(0, diffs[:, t])

Upon solving this model with no objective or other constraints I receive an invalid status. I am new to ORTools.

Full Program

ortools==9.3.10497

from ortools.sat.python import cp_model
import numpy as np

model = cp_model.CpModel()
num_groups = 4
STATUS  = ['UNKNOWN', 'MODEL_INVALID', 'FEASIBLE', 'INFEASIBLE', 'OPTIMAL']
M = []
for m in range(num_groups):
    M.append(model.NewIntVar(lb=0, ub=num_groups, name=f'M_{m}'))
T = []
for t in range(num_groups):
    T.append(model.NewIntVar(lb=0, ub=num_groups, name=f'T_{t}'))
M = np.array(M)
T = np.array(T)


diffs = M[:, None] - T
for m in range(num_groups):
    model.AddMultiplicationEquality(0, diffs[m, :])
for tt in range(num_groups):
    model.AddMultiplicationEquality(0, diffs[:, tt])

solver = cp_model.CpSolver()
status = solver.Solve(model)
print(STATUS[status])

Answer 1

This is catastrophic. Multiplications are very slow.

just create one Boolean variable per value, one Boolean variable per value and per variable.

Now, you want to link everything together.

for a variable x in either set and a value v:

    assign = {}
    assign[x, v] = model.NewBoolVar(f'assign_{x}_{v}')
    model.Add(x == v).OnlyEnforceIf(assign[x, v])
    model.Add(x != v).OnlyEnforceIf(assign[x, v].Not())

for a value v:

    appears = {}
    appears[v] = model.NewBoolVar(f'appears_{v}')

    # If v does not appear, no variable can be assigned its value.
    for x in T U M:
        model.AddImplication(appears[v].Not(), assign[x, v].Not())

    # If v appears, at least one variable in both T and M must be assigned to v.
    model.AddBoolOr(assign[x, v] for x in T).OnlyEnforceIf(appears[v])
    model.AddBoolOr(assign[x, v] for x in M).OnlyEnforceIf(appears[v])