Google OR-Tools - find best group assignments

Viewed 400

I'm using ortools (in Python) to assign students to groups. Each student has a level in three different skills. Working from the example programs, I can create groups and ensure that in each group, there is at least one student with a certain level in each skill:

for p in all_people:
    for g in all_groups:
        allocation[(p,g)] = model.NewBoolVar('shift_p%ig%i' % (p,g))


# Setup Constraints

# Each person is assigned to exactly one group.
for p in all_people:
    model.Add(sum(allocation[(p,g)] for g in all_groups) == 1)

# Each group has at enough people but not too many.
for g in all_groups:
    model.Add(sum(allocation[(p,g)] for p in all_people) >= min_size)
    model.Add(sum(allocation[(p,g)] for p in all_people) <= max_size)


# Each group has at least one person with good skills
for g in all_groups:
    for s in all_skills:
        model.Add(sum(skills_enough[p][s] *  allocation[(p,g)] for p in all_people  ) > 0)

This works fine as a constraint satisfaction problem.

What I'd now like to do is add in an optimisation constraint that tries to make the levels of skills in each group as even as possible. I've tried a few different configurations, but can't come up with something functional:

  • I can't figure out a way for ORTools to work with the minimum value in a generator, i.e. doing min(student_info[p][s] * allocation[(p,g)] for p in all_people) to get the lowest value in group g, as there is no min() equivalent of sum()
  • I also can't set it up to e.g. minimise the sum of squares, as adding the multiplicative term results in a TypeError: Not an integer linear expression:. And fair enough, it's not linear any more. Example code:
model.Minimize(
sum(
    sum(
        (
            sum(student_info[p][s] * allocation[(p,g)] for p in all_people) *
            sum(student_info[p][s] * allocation[(p,g)] for p in all_people)
         ) for s in all_skills
    ) for g in all_groups
) )

A way to optimise groups that fits with the linear solver model would be as helpful as a way to set up the existing problem.

1 Answers

for min() and max(), you need to use AddMinEquality and AddMaxEquality.

Please note that these take an array of variables, so you need to create intermediate variables in your case.

See this doc.

Related