Пакет R OMPR - ограничение количества выбранных уникальных переменных компонентов

Я использую пакет ompr для создания и решения задачи целочисленного программирования. Для простоты я буду использовать в качестве примера футболистов НФЛ в жанре фэнтези.

Я хочу максимизировать количество очков, набранных в двух играх, при этом играя только по 1 игроку на каждой позиции за игру. (Для простоты предположим, что любой игрок может играть на любой позиции.)

У меня проблемы с тем, что из 25 возможных игроков я хочу ограничить общее количество игроков, выбранных в двух играх, до 15. Компонент i добавленной переменной ompr представляет собой индексы игроков, но я не уверен, как добавить ограничение, ограничивающее общее количество выбранных уникальных i.

Любая помощь будет принята с благодарностью!

n_players = 25
n_positions = 11
n_games = 2

# Points each player will score at each position per game
points_game1 = matrix(runif(25*11), nrow = 25, ncol = 11)
points_game2 = matrix(runif(25*11), nrow = 25, ncol = 11)
points_array <- array(c(points_game1, points_game2), dim = c(n_players, n_positions, 2))

mip <- ompr::MIPModel() %>% 
  
  # Initialize player/position set of binary options
  ompr::add_variable(x[i, j, k], i = 1:n_players, j = 1:n_positions, k = 1:n_games, type = 'binary') %>%
  
  # Every player/game can only be 0 or 1 across all positions
  ompr::add_constraint(sum_expr(x[i, j, k], j = 1:n_positions) <= 1, i = 1:n_players, k = 1:n_games) %>% 
  
  # Every position/game has to be exactly 1 across all players
  ompr::add_constraint(sum_expr(x[i, j, k], i = 1:n_players) == 1, j = 1:n_positions, k = 1:2) %>%
  
  # ****** Limit to 15 players total ??? ****
  
  # Objective is to maximize points
  ompr::set_objective(sum_expr(x[i, j, k] * points_array[i, j, k], i = 1:n_players, j = 1:n_positions, k = 1:n_players), 'max') %>% 

  # Solve model
  ompr::solve_model(with_ROI(solver = 'symphony', verbosity = -2))

r optimization mixed-integer-programming linear-programming ompr
person Sam    schedule 17.12.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы можете добавить набор двоичных переменных, индексированных по игрокам, которые отслеживают, используется ли игрок в каком-либо посте в любой игре. Затем вы можете ограничить сумму этих переменных до своего предела (15). Это позволяет вам считать игрока только один раз, даже если он используется в обеих играх. Затем вы можете добавить большое ограничение M, которое заставляет новые двоичные переменные равняться 1, если игрок используется в любой позиции в любой игре, но позволяет переменной быть равным 0, если игрок не используется. Поскольку у нас есть две игры, и игрок может находиться не более чем в 1 позиции в каждой игре, мы можем установить большое M равным 2 для всех игроков.

ompr::add_variable(is_used[i], i = 1:n_players, type = 'binary') %>%
ompr::add_constraint(sum_expr(is_used[i],i = 1:n_players) <= 15) %>%
# big M constraint ensuring that is_used is 1 if a player is used
ompr::add_constraint(2*is_used[i] >= sum_expr(x[i,j,k],j = 1:n_positions, k = 1:2), i = 1:n_players) %>%
person cookesd    schedule 17.12.2020
comment
Большое спасибо! Я относительно новичок в смешанном целочисленном программировании и ompr, так что все еще пытаюсь понять функциональность, но это работает отлично. - person Sam; 17.12.2020