Блог

Проблема

Я использую lpSolve для поиска оптимального состава для фэнтезийной бейсбольной команды — задача о рюкзаке, включающая цену SALARY и прогнозируемые очки DK каждого игрока PLAYERID в рамках заданных ограничений соревнования.

Текущий код работает отлично, но у меня есть ограничение, которое я хотел бы добавить, которое я не совсем понимаю. Новое ограничение заключается в том, чтобы в составе не было игроков, играющих с одним из питчеров SP в том же составе.

Что у меня есть до сих пор

Я создал столбец с именем MNBT (не должен быть вместе), который определяет питчера соперника PLAYERID , которого нельзя найти в том же составе, что и у каждого игрока, но я застрял там. Первые 20 строк data.frame slate_players следующие (при необходимости я могу предоставить все 91 строку для этого конкретного конкурса):

    PLAYERID POS TEAM OPP SALARY    DK TEAM_O    MNBT
1     37584  SP  LAD OAK  10000 18.42    0SP   13170
2     11292  SP  TEX HOU   9300 18.41    0SP 1452665
3   1452665  SP  HOU TEX   7400 15.22    0SP   11292
4     11168  SP  BAL BOS   6900  9.06    0SP   13502
5     13170  SP  OAK LAD   6800  6.06    0SP   37584
6     13502  SP  BOS BAL   6700 13.52    0SP   11168
7   2038873  SP  KCR DET   6600 18.45    0SP   34649
8     34649  SP  DET KCR   6500  7.46    0SP 2038873
9     11446   C  KCR DET   5300  7.55    KCR   34649
10  1054004   C  LAD OAK   5000  8.25    LAD   13170
11    15541   C  BOS BAL   4500  7.08    BOS   11168
12  1252110   C  OAK LAD   4100  5.07    OAK   37584
13    22667   C  BAL BOS   3400  7.09    BAL   13502
14    10290   C  TEX HOU   2900  4.08    TEX 1452665
15    13171   C  DET KCR   2800  5.45    DET 2038873
16    17552   C  HOU TEX   2600  4.47    HOU   11292
17    36727  1B  LAD OAK   5800  9.09    LAD   13170
18    17648  1B  LAD OAK   5400  8.57    LAD   13170
19    17887  1B  OAK LAD   4900  7.30    OAK   37584
20    17851  1B  KCR DET   4400  7.24    KCR   34649
[...]
  

Текущий код lpSolve

 # count the unique players and teams on the slate
unique_teams = unique(slate_players$TEAM_O)
unique_players = unique(slate_players$PLAYERID)

# define the objective for the solver
obj = slate_players$DK

# create a constraint matrix for the solver
con = rbind(t(model.matrix(~ POS   0, slate_players)), #Positions
            t(model.matrix(~ PLAYERID   0, slate_players)), #DupPlayers
            t(model.matrix(~ TEAM_O   0, slate_players)), #SameTeam
            rep(1,nrow(slate_players)), #TotPlayers
            slate_players$SALARY) #MaxSalary

# set the direction for each of the constraints
dir = c("==", #1B
        "==", #2B
        "==", #3B
        "==", #C
        "==", #OF
        "==", #SP
        "==", #SS
        rep('<=',length(unique_players)), #DupPlayers
        rep('<=',length(unique_teams)), #SameTeam
        "==", #TotPlayers
        "<=") #MaxSalary

# set the limits for the right-hand side of the constraints
rhs = c(1, #1B
        1, #2B
        1, #3B
        1, #C
        3, #OF
        2, #SP
        1, #SS
        rep(1,length(unique_players)), #DupPlayers
        rep(5,length(unique_teams)), #SameTeam
        10, #TotPlayers
        50000) #MaxSalary

# find the optimal solution using the solver
result = lp("max", obj, con, dir, rhs, all.bin = TRUE)

# create a table for the players that are in optimal solution
solindex = which(result$solution==1)
optsolution = slate_players[solindex,]
  

Вопрос

Как мне закодировать это новое ограничение? Я выполнял подобные настройки вручную, но я был бы очень признателен, если бы было доступно решение для автоматизации этого процесса. Спасибо!

В итоге вместо одного MNBT столбца я создал вспомогательный столбец для каждого отдельного питчера SP , чтобы указать, с какими нападающими он может не появиться в оптимальном решении. В этих столбцах я присвоил значение для питчера 5 и значение 1 для каждого нападающего, с которым он не должен появляться. Затем ограничение стало таким, что сумма каждого из этих столбцов будет равна <= 5 . Логика заключается в том, что максимум 5 нападающих могут быть в одном составе перед любым отдельным питчером, но если бы этот же питчер появился в оптимальном решении, ни один из нападающих, с которыми он столкнулся, не был бы.

Хотя это не создает для вас набор ограничений, этот пример является одним из тех ограничений, которые, как упоминал @AirSquid, могут помочь.

В приведенном выше примере 6-й игрок (13502) не смог сыграть против 13-го игрока (22667).

Добавить к ограничению:

 c(0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0)
  

Добавить в инструкции:

 "<="
  

Добавить в правую часть:

 1
  

Следующий трюк заключается в том, как сгенерировать все эти наборы ограничений в R. Cheerio.