In my problem, I have students who each need to be assigned to one class. Each student and each class has a schedule, and if a student is assigned to a class, the schedules cannot conflict.
As a toy example, say there are five time blocks. If a student's schedule is filled on the third time block, but free on all others, their schedule will look like [0,0,1,0,0]. Similarly, if a class takes place on the first and second time chunks, its schedule will look like [1,1,0,0,0]. Because this student's schedule does not conflict with this class' schedule, the student can be assigned to this class. However, if the student's schedule was [1,0,0,0,0], they could not be assigned to the class.
Using google's ortools, the constraints then seem pretty simple: only one class per student, and if we have 2 students schedules S and 3 class schedules C:
S = {0:[0,0,1,0,0],1:[0,1,0,1,0]}
C = {0:[1,1,0,0,0],1:[0,0,1,0,1],2:[1,0,0,0,0]}
Then student [i] can be assigned to class [j] only if np.dot(np.asarray(S[s]),np.asarray(C[c]))==0, i.e. the dot product of the schedules is zero.
Implementing the latter constraint hasn't worked for me. I've tried the following:
num_students = 2
num_classes = 3
all_students = range(num_students)
all_classes = range(num_classes)
S = {0:[0,0,1,0,0],1:[0,1,0,1,0]}
C = {0:[1,1,0,0,0],1:[0,0,1,0,1],2:[1,0,0,0,0]}
# Creates the model.
model = cp_model.CpModel()
# Creates scheduling variables.
# shifts[(c, s)]: student c is assigned to class s.
# 1 if true, 0 if not
sched = {}
for s in all_students:
for c in all_classes:
sched[(c,s)] = model.NewBoolVar('shift_c%is%i' % (c, s))
# Each class is assigned to exactly one student in the schedule period.
for s in all_students:
model.Add(sum(sched[(c, s)] for c in all_classes) == 1)
# The schedules cannot conflict
for c in all_classes:
for s in all_students:
model.AddBoolOr([(sched[(c,s)] and np.dot(np.asarray(S[s]),np.asarray(C[c]))==0),
sched[(c,s)].Not()])
However, when I run this, I get the following error:
<ipython-input-41-9aad6f1c8113> in main()
55 for s in all_students:
56 model.AddBoolOr([(sched[(c,s)] and np.dot(np.asarray(S[s]),np.asarray(C[c]))==0),
---> 57 sched[(c,s)].Not()])
58
59
/anaconda3/lib/python3.6/site-packages/ortools/sat/python/cp_model.py in AddBoolOr(self, literals)
1162 model_ct = self.__model.constraints[ct.Index()]
1163 model_ct.bool_or.literals.extend(
-> 1164 [self.GetOrMakeBooleanIndex(x) for x in literals])
1165 return ct
1166
/anaconda3/lib/python3.6/site-packages/ortools/sat/python/cp_model.py in <listcomp>(.0)
1162 model_ct = self.__model.constraints[ct.Index()]
1163 model_ct.bool_or.literals.extend(
-> 1164 [self.GetOrMakeBooleanIndex(x) for x in literals])
1165 return ct
1166
/anaconda3/lib/python3.6/site-packages/ortools/sat/python/cp_model.py in GetOrMakeBooleanIndex(self, arg)
1408 else:
1409 raise TypeError('NotSupported: model.GetOrMakeBooleanIndex(' +
-> 1410 str(arg) + ')')
1411
1412 def GetIntervalIndex(self, arg):
TypeError: NotSupported: model.GetOrMakeBooleanIndex(True)
Is this just a matter of reformatting the AddBoolOr statement, or am I missing something bigger?
Any help appreciated!
min, max, or, and with variables created by ortools.With your problem, you can do one of the following:
if np.dot(np.asarray(S[s]),np.asarray(C[c])) != 0:
model.Add(sched[(c,s)] == 0)