Комбинаторная оптимизация подбора игроков футбольной команды

Я думаю об использовании целочисленного программирования для создания оптимальной комбинации футболистов, составляющих команду.

Хотя сама проблема проста, мне сложно сформулировать эффективное ограничение для получения права на должность.

Я искал в stackoverflow варианты классических задач целочисленного программирования и нашел временное решение, но хочу проверить, эффективно ли текущее.

Задача
Выберите 11 игроков для футбольной (футбольной) команды из конечного набора потенциальных игроков.
Команда состоит из 11 слотов: 5 атакующих, 5 защитников и 1 вратарь. .
Каждая роль имеет свой собственный пул подходящих игроков.
(например, вратарей можно выбрать только из группы игроков, у которых есть перчатки)
Каждому игроку назначается «оценка навыков», которая отражает их навыки

Целевая функция
Максимизация: сумма всех 11 очков навыков игроков.

Ограничения

  1. Все 11 слотов должны быть заполнены хотя бы одним игроком.
  2. 1 игрок может занимать только 1 слот
  3. Каждый слот должен быть заполнен игроком, имеющим право на эту роль.

Мое временное решение

Let xij: player i in consideration for slot j (j=1, 2,..., 11, 1 <= i <= n)
and w: n x 1 weight matrix representing skill score for player i

1. sum_j(xij) == 1 for each slot j
2. 0 <= sum_i(xij) <= 1 for each player i
3. 0 <= xij <= 1 if player i is eligible for slot j, == 0 otherwise

maximize sum(wTx)

Я еще не мог придумать элегантный способ ввести в действие 3, поэтому сейчас мой ответ - жестко закодировать каждую ячейку как 0.

Я планирую использовать библиотеку целочисленного программирования на Python (cvxpy или PuLP).

Приведет ли текущий дизайн к каким-либо проблемам с конвергенцией или временем вычислений?

Есть ли более эффективный способ смоделировать проблему?

Примечания

  • Для простоты предположим, что, хотя игрок может быть кандидатом на несколько ролей, его очки навыков не меняются в зависимости от роли.
  • Изменится ли формулировка задачи, если очки навыков игроков изменятся в зависимости от их взаимодействия с другими игроками? Я думаю, что простое расширение матрицы x на nC2 возможных взаимодействий могло бы сработать, но мне любопытно, есть ли лучшие решения.

algorithm knapsack-problem combinatorics mathematical-optimization mixed-integer-programming
person ydp    schedule 27.12.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Ваш IP-адрес выглядит нормально. Однако эту проблему также можно решить с помощью динамического программирования:

Пусть массив dp[n][mask] представляет максимально возможное количество очков, которое вы можете получить за размещение игроков от 1 до n на позиции, которым соответствуют цифры 0 в двоичном представлении mask. Например, dp[5][0b11111110101] равно максимальному баллу, который вы можете получить за размещение игроков с 1 по 5 на позиции 2 и 4. (второй и четвертый биты маски равны нулю).

Теперь мы рекурсивно определяем dp[n][mask]:

dp[n][mask] = max{
    dp[n-1][mask], # the case when we don't use player n
    max_j{ dp[n-1][mask|(1<<j)] + w[n] } (1 <= j <= 11 and mask's jth bit is 0)
}

Базовый случай - когда n=0.

dp[0][mask] = {
    -infinity, if there are 0 bits in mask # there are empty positions left, we want to strictly discourage this case.
    0, if all 11 bits of mask is 1
}
person yemre    schedule 27.12.2020