Оптимизация распределения команд с помощью PuLP - PullRequest
Новая
       75

Оптимизация распределения команд с помощью PuLP

0 голосов
/ 12 января 2020

Справочная информация: Я пытаюсь распределить студентов по группам, где каждый студент будет иметь ряд предпочтений перед другими студентами, находящимися в их командах. У меня есть целевая функция, которую я хочу минимизировать вместе с 3 ограничениями для функции (написано на рисунке ниже). В моей базе данных у меня есть набор учеников вместе с их предпочтениями (например, ученик, я оцениваю ученика j как своего третьего выбора).

Если ученик A оценивает ученика B как свой первый выбор, это предпочтение будет иметь весовой коэффициент. 1, поэтому целевая функция установлена ​​на минимизацию.

Математическая формула:

enter image description here

Вопрос: Я не уверен, правильно ли я написал ограничения и переменные в PuLP, и я не могу найти какие-либо близкие ресурсы, которые выполняют распределение команды с предпочтениями. Я очень плохо знаком с PuLP и пытаюсь выяснить, правильно ли написано то, что я написал, синтетически, спасибо за любую помощь!

Вот код, который я написал в моем файле: 

from pulp import *

model = LpProblem("Team Allocation Problem", LpMinimize)

############ VARIABLES ############

students = [1,...,20]
n = 20
# this will be imported from the database
r = [[...],...,[...]]
team_sizes = [5,5,5,5] 
num_teams = len(z)

# x(ik) = 1 if student i in team k
x_vars = [[LpVariable("x%d%d" % (i,k), cat='Binary') 
        for k in range(num_teams)] 
        for i in range(num_students)]
# y(ijk) = 1 if student i and j are in team k
y_vars = [[[LpVariable("y%d%d%d" % (i,j,k), cat='Binary') 
        for k in range(num_teams)] 
        for j in range(num_students)] 
        for i in range(num_students)]


############ OBJECTIVE FUNCTION ############

for i in range(num_students):
    for j in range(num_students):
        if i!=j:
            for k in range(num_teams):
                model += r[i][j] * y_vars[i][j][k], "Minimize the sum of rank points in the team"

############ CONSTRAINTS ############

# C1: Every student is on exactly one team
for i in range(num_students):
    for k in range(num_teams):
        model += lpSum(x_vars[i][k]) == 1


# C2: Every team has the right size
for k in range(num_teams):
    for i in range(num_students):
        model += lpSum(x_vars[i][k]) == team_sizes[k]

# C3: 
for i in range(num_students):
  for j in range(num_students):
      if i != j:
          for k in range(num_teams):
              model += 1 + y_vars[i][j][k] >= x_vars[i][k] + x_vars[j][k]

# Solve and Print
model.solve()
print("Status:", model.status)

1 Ответ

1 голос
/ 13 января 2020

(1) Убедитесь, что смысл цели правильный. То, как я читаю вашу проблему, вы должны максимизировать.

(2) Правильная линеаризация 

  y(i,j,k) = x(i,k)*x(j,k)

равна 

  y(i,j,k) <= x(i,k)
  y(i,j,k) <= x(j,k)
  y(i,j,k) >= x(i,k)+x(j,k)-1

Иногда мы можем отбросить некоторые из этих ограничения из-за того, как цель работает. Убедитесь, что вы подтвердили, что вы действительно можете сбросить y(i,j,k) <= x(i,k) и y(i,j,k) <= x(j,k).

(3) Это (почти) тот же вопрос, что и Алгоритмы для оптимального размещения студентов .

(4) Я хочу минимизировать цель в этом случае, если кто-то оценит кого-то как свой первый выбор, ему, по сути, будет дан 1 балл, 2 балла за секунду, 3 балла за третий и т.д. c. Вы не можете иметь 0=no points 1=best 2=second best,... в своей формулировке. Предлагаю перекодировать ваши очки: 0=no points, 1=ok, 2=better, 3=best. (Просто предварительная обработка данных). Тогда максимизируйте вместо того, чтобы минимизировать. Вы можете добавить -1,-2,... за неприязнь, если хотите.

...