Combinatorial optimization for selecting the players of a football team

user_14894985 0
Viewed 125

I'm thinking of using integer programming to generate the optimal combination of football players to comprise a team.

Though the problem itself is simple, I'm having trouble formulating an efficient constraint for position eligibility.

I've searched stackoverflow for variants on the classic integer programming problems and came up with a temporary solution, but want to verify if the current one is efficient.

Problem
Select 11 players for a football (soccer) team from a finite set of potential players.
The team is composed of 11 slots: 5 offense, 5 defense, and 1 goal keeper.
Each role has its own respective pool of eligible players.
(e.g. goalies can only be selected from a set of players that have gloves)
Each player is assigned a 'skill score' that represents their skill

Objective function
Maximize: sum of all 11 player skill scores

Constraints

  1. All 11 slots must be filled with at least 1 player
  2. 1 player may occupy only 1 slot
  3. Each slot must be filled by a player that is eligible for the role

My temporary solution

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)

I could not yet think of an elegant way to operationalize 3, so my answer for now is to hard code each cell to be 0.

I'm planning to use an integer programming library in Python (cvxpy or PuLP).

Would the current design lead to any issues in convergence or computation time?

Would there be a more efficient way to model the problem?

Notes

  • For simplicity, let's assume that while a player can be a candidate for multiple roles, their skill point does not change depending on role
  • Would the problem formulation change if the players' skill scores change depending on their synergy with other players? I'm thinking that simply expanding the x matrix by nC2 possible interactions could work, but am curious if there are better solutions.
mixed-integer-programming knapsack-problem mathematical-optimization combinatorics algorithm
1 Answers

Your IP formulation looks OK. However, this problem can also be solved using Dynamic Programming:

Let the array dp[n][mask] represent the maximum possible score you can get for placing players from 1 to n into positions that the 0 digits in the mask's binary representation correspond. For example dp[5][0b11111110101] is equal to the maximum score you can get for placing players 1 to 5 into positions 2 and 4. (second and fourth bits of the mask are zero.)

Now we recursively define 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)
}

The base case is when 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
}
user_41806620
Related