I'm a bit stuck here, and couldn't find any similar examples or obvious methods to use...
For a volunteer scheduling script (in Python), there's cases where some volunteers may have to do 2+ roles on the same day. Certain combinations (pairs) of roles are more difficult than others to do simultaneously, so I've assigned integer (0-10) penalty weights for each pair in the input data. Rather than Minimize (optimization), I've decided to Add (constraint) to forbid any sum of sum of weights greater than const conflict_level.
Below is the constraint code that currently am trying. The args for days, roles and volunteers are range lists (i.e., [0-n]).
For any person on any day, I would like to take the list of their roles (x, an array of CpModel BoolVars) use the bit pairs to address and sum the pair weights.
To help visualize the approach I'm trying, here is code tested in the Python CLI:
>>> x = [True,False,True,True,False,False,False]
>>> [i for i,n in enumerate(x) if n]
[0, 2, 3]
>>> [role_objs[a]['conflicts'][role_names[b]] for a,b in list(combinations([i for i, n in enumerate(x) if n], 2))]
[6, 8, 2]
Which would sum to 16 in this example.
But if the boolean list is replaced by a BoolVar list, I get an error.
def constraint_role_conflicts(model, jobs, data, days, roles, volunteers):
role_objs = data['roles']
role_names = [n['name'] for n in data['roles']]
for d in days:
for v in volunteers:
x = [jobs[(d,r,v)] for r in roles]
model.Add(sum([role_objs[a]['conflicts'][role_names[b]] for a,b in list(combinations([i for i, n in enumerate(x) if n], 2))]) > conflict_level)
At the 2nd instance of 'n' in the Add method call, I am getting:
NotImplementedError: Evaluating a LinearExpr instance as a Boolean is not implemented.
What am I doing wrong?
UPDATE - Adding as requested a complete minimal reproducible example.
from ortools.sat.python import cp_model
from itertools import combinations
# role conflict pain threshold setting
pain_threshold = 8
# role pair pain factors
conflicts = [
[0, 10,6, 8, 8, 7, 8 ],
[10,0, 9, 3, 2, 3, 3 ],
[6, 9, 0, 2, 1, 2, 6 ],
[8, 3, 2, 0, 1, 5, 10],
[8, 2, 1, 1, 0, 7, 7 ],
[7, 3, 2, 5, 7, 0, 4 ],
[8, 3, 6, 10,7, 4, 0 ]
]
ndays = 25
nroles = 7
nvols = 10
days = list(range(ndays))
roles = list(range(nroles))
vols = list(range(nvols))
model = cp_model.CpModel()
jobs = {}
for d in days:
for r in roles:
for v in vols:
jobs[(d,r,v)] = model.NewBoolVar(f"d{d}r{r}v{v}")
# one volunteer per each day, each role
for d in days:
for r in roles:
# The boolvar array True values are summed and must equal 1,
# meaning exactly 1 volunteer for each day-role job assignment.
model.AddExactlyOne(jobs[(d,r,v)] for v in vols)
# don't allow role conflicts over a certain pain threshold
for d in days:
for v in vols:
x = [jobs[(d,r,v)] for r in roles] # e.g. [True, False, True, False, ...]
# xids = [i for i in range(len(x)) if x[i]] # e.g. [0, 2, 4]
# role_pairs = list(combinations(xids, 2)) # e.g. [(0,2), (0,4), (2,4)]
# pain = sum([conflicts[a][b] for a,b in role_pairs])
# model.Add(pain > pain_threshold)
model.Add(sum([conflicts[a][b] for a,b in list(combinations([i for i in range(len(x)) if x[i]], 2))]) > pain_threshold)
solver = cp_model.CpSolver()
solver.parameters.enumerate_all_solutions = False
solver.parameters.num_search_workers = 16
solver.parameters.max_time_in_seconds = 300 # 5 minutes
print("Running Solver...")
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
for d in days:
print(f"Day {d}")
for r in roles:
for v in vols:
# solver tests the True value of the boolvar.
if solver.Value(jobs[(d,r,v)]):
print(f" d{d}_v{v}_r{r} Role: {r} = Volunteer {v}")
else:
print("No solution found.")
Please post a complete minimal reproducible example.
And be aware that a boolvar does not have a value per se. You cannot use it an if, a comparison, a python test.
Doing so will create a CP-SAT expression or bounded linear expression.
As this object is not None, it will silently be evaluated to True. For instance, using sort or max and an array of variables used to silently create garbage.
For this reason, we protect the cast to bool as this should never happen.
A useful read is: https://github.com/google/or-tools/blob/stable/ortools/sat/docs/channeling.md