1
$\begingroup$

I am very new to optimization and OR-Tools. I am trying to solve a very simple question.

Let's assume that we have $n$ students. Each student needs to be assigned to only one teacher as a supervisor. There are several constraints that are not very critical for now. However, there are two types of supervisors. But at the same time, I am trying to keep the balance of the workload of the teachers as much as possible.

I am trying to write the objective but for some reason, it does not work correctly. I believe that I am missing something important.

model = cp_model.CpModel()

# Declare the variables.
x = []
for i in range(num_of_students):
    t = []
    for j in range(num_of_teacher):
        t.append(model.NewIntVar(0, 2, "x[%i,%i]" % (i, j))) #0 not supervisor, 1 1st type, 2nd type
    x.append(t)

workload =[]
for j in range(num_of_teacher):
    workload.append(sum([x[i][j] for i in range(num_of_students)]))

# Constraints
# Each student is assigned to EXACTLY one teacher.
[model.Add(sum(x[i][j] for j in range(num_of_teacher)) == 1)
for i in range(num_of_students)]

#objective
model.Maximize( min(workload))

solver = cp_model.CpSolver()
status = solver.Solve(model)
print (solver.ObjectiveValue())

When I run the code, each student (I have 11 students and 3 teachers) is assigned to only one teacher. But all of them are the same teacher. When I look at the workloads, it is [0, 0, 11].

However, system displays 11 as the ObjectiveValue. But min([0,0,11] is 0, right?.

I also tried to write the objective as model.Minimize( max(workload)) but all of the students assigned to only one teacher again.

Please help me!

$\endgroup$
4
$\begingroup$

min, max, functions do not work in OR-Tools, you should use AddMinEquality instead:

...
workload = []
for j in range(num_of_teacher):
    tmp = model.NewIntVar(0, num_of_students, "")
    model.Add(tmp == sum([x[i][j] for i in range(num_of_students)]))
    workload.append(tmp)

...
obj = model.NewIntVar(0, num_of_students, "")
model.AddMinEquality(obj, workload)
model.Maximize(obj)

Related links:

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for very quick answer. Now it works :) I am not still trying to learn OR-tools but I think obj = model.NewIntVar(0, num_of_students, "") should be obj = model.NewIntVar(0, num_of_teacher, "") right? $\endgroup$ – neverletgo Jul 24 at 6:48
  • $\begingroup$ hmm, isn't workload related to num_of_students? obj is just the min of that $\endgroup$ – Stradivari Jul 24 at 12:09
  • $\begingroup$ I really do not wan to take your time but can you briefly explain the logic? $\endgroup$ – neverletgo Jul 27 at 8:44
  • $\begingroup$ I think I understand, thank you for explaining.... Do you know any tutorial like "OR tools for dummies" :) Because I will face with lots of problem like it.. For example I want to ignore the type of supervision when counting the workload.. So in ideal conditions: model.Add(tmp == sum([ x[i][j] for i in range(num_of_items_in_orders)])) should be model.Add(tmp == sum([ (x[i][j] > 0) for i in range(num_of_items_in_orders)])) but it says: TypeError: unsupported operand type(s) for +: 'int' and 'BoundedLinearExpression' Do you have any suggestion for it? $\endgroup$ – neverletgo Jul 27 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.