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?

  • $\begingroup$ How does the score of the team relate to the number of points each individual scored last season? We'd need to know the relationship before we could solve this. Are you assuming the team's score will be the sum of the performances of each individual player on the team? (I suspect that won't be a very good predictor, so I suspect there's an issue with your problem formulation, but you should tell us what assumptions you want us to make; we can't solve the algorithms problem without some assumption about that relationship.) $\endgroup$ – D.W. Jul 15 '18 at 17:05
  • $\begingroup$ Oh sorry, the score of the team is equal to sum of all players' individual points. $\endgroup$ – Vladimir Jul 15 '18 at 17:09
  • 2
    $\begingroup$ Rather than leaving a clarification in the comments, please edit the question so it contains all information needed to solve the problem. We don't want people to have to read the comments to understand what you are asking. Thank you! $\endgroup$ – D.W. Jul 15 '18 at 17:12

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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.