Fantasy premier league dream team algorithm?

Question

For those of you who are not familiar with FPL, here's a short version. You have players playing as either Goalkeeper, Defender, Midfielder or Forward. Each player has some price (either rounded to .5 or .0), and based on their real life performance you earn points. You have a budget of 100£ and you need to build a team, keeping in mind you have a limit for players on each position.

Now, the problem is: If you have all players prices, their positions and total number of points they scored in a season, how do you find the highest scoring team (team score is equal to sum of all players' individual points) with, for example, 4-4-2 formation? (1GK, 4DEF, 4MID, 2FWD)

I guess this is a variation of knapsack problem, where you have limitations to have exactly 11 players, and exactly 4-4-2 formation. So is that the best way to solve this problem and how would you solve it with these modifications/limitations, or is there a better solution?

Answer 1

You can formulate an integer program for this problem. For each player $i$ let $a_i$ be the number of points the player scored, $p_i$ is his price. Moreover, let $G, B, M, F$ be the set of goal keepers, backs, midfielders and forwards, respectively, $P := G \cup B \cup M \cup F$ the set of all players, and $C$ is the salary cap. We use binary variables $x_i \in \{0, 1\}$ for each player $i$, were $x_i = 1$ iff player $i$ is in the optimal roster, $0$ otherwise. The optimal roster is then induced by the solution of the following program: $$\begin{aligned} \text{maximize } & \sum_{i \in P} a_i x_i\\ \text{subject to } & \sum_{i \in P} p_i x_i \leq C\\ & \sum_{i \in G} x_i = 1\\ & \sum_{i \in B} x_i = 4\\ & \sum_{i \in M} x_i = 4\\ & \sum_{i \in F} x_i = 2\\ & x_i \in \{0, 1\} & i \in P \end{aligned} $$ Now you may have noticed that the objective function + capacity constraint is indeed a knapsack problem but you have additional constraints on the formation.

Although you can use a MIP solver of your choice, you might even exploit this knapsack structure as a subproblem by using a knapsack solver (I think there is some very popular dynamic programming approach).