Блог

Я пытаюсь добавить ограничение к модели программирования смешанных целых чисел в R, чтобы каждому человеку была назначена только одна роль.

У меня есть фрейм данных, который выглядит следующим образом:

 ID    Name     Role     PreferenceScore  
 ----- ------- --------- ------------------ 
    1   Abby    Chef                    10  
    1   Abby    Waiter                   8  
    1   Abby    Greeter                  9  
    2   Bob     Chef                     7  
    2   Bob     Waiter                   8  
    2   Bob     Greeter                  3  
    3   Carly   Chef                     5  
    3   Carly   Waiter                   8  
    3   Carly   Greeter                  4  
   ...  ...     ...                      ...
   20   David   Chef                     2  
   20   David   Waiter                   3  
   20   David   Greeter                  8  
  

Я пытаюсь назначить каждому пользователю роль на основе их предпочтений (чем больше число, тем лучше), используя MIPmodel. В каждой роли может быть до 8 человек, а всего 20 человек.

Вот что у меня есть на данный момент:

 library(dplyr)
library(ompr)
library(ompr.roi)
library(ROI)
library(ROI.plugin.glpk)

teamData <- read.csv("filename")
teamData$wait <- if_else(teamData$jobType == "Waiter", 1, 0)
teamData$chef <- if_else(teamData$jobType == "Chef", 1, 0)
teamData$greet <- if_else(teamData$jobType == "Greeter", 1, 0)

p <- nrow(teamData)
v <- as.numeric(teamData$PreferenceScore)
maxTeamSize <- 8
role <- teamData$Role

chef_job <- teamData$chef 
waiter_job <- teamData$wait
greeter_job <- teamData$greet
name <- teamData$Name

# Build the model
model <- MIPModel() %>%
  add_variable(x[i], i=1:p, type = "binary") %>%
  set_objective(sum_expr(x[i] * v[i], i=1:p)) %>%
  add_constraint(sum_expr(chef_job[i], i=1:p) <= 8) %>%
  add_constraint(sum_expr(waiter_job[i], i=1:p) <= 8) %>%
  add_constraint(sum_expr(greeter_job[i], i=1:p) <= 8) # %>%
#   add_constraint(sum_expr(count(name[i])) == 1)

solved <- solve_model(model, with_ROI("glpk"))

result <- solved %>%
  get_solution(x[i]) %>%
  select(i) %>% 
  rowwise() %>% 
  mutate(Pref = v[i], Role = role[i], teamData$Name[i]) %>%
  ungroup

result
  

Моя главная проблема прямо сейчас заключается в том, что я не могу понять, как добавить ограничение, чтобы у каждого человека была только одна роль в решении (т. Е. Каждый человек может быть только шеф-поваром, официантом или встречающим)

Любые указатели были бы весьма признательны.

Это типичная проблема с назначением, когда вы назначаете человека p на работу j . Итак, вам нужно обновить свою формулировку, чтобы иметь переменную решения с двойным индексом, x[p, j] . Тогда все начнет приобретать больше смысла … :).

Затем вы можете суммировать все задания, чтобы гарантировать, что у каждого человека не более одного назначения (в псевдокоде … мой синтаксис R ужасен):

 sum (x[p, j] for j in Jobs) <=1  for p in Persons
  

и вы можете убедиться, что ни одна позиция не переполнена, если у вас есть максимум spots[j] заполнений в каждой роли:

 sum (x[p, j] for p in People) <= spots[j] for j in Jobs
  

и ваша целевая функция встанет на свои места аналогичным образом путем умножения на preference[p, j]