3
$\begingroup$

I have 100 football (soccer) players, each with an "expected score" (higher is better) and price (e.g. 4300 dollars). I want to select the optimal combination of players with the highest combined score (i.e. a fantasy football formation) within a $50,000 budget, where a lineup must consist of the following formation:

  • Goalkeeper x1
  • Defender x2
  • Midfielder x2
  • Forward x2
  • Utility x1 (can be any position apart from GK)

Each player has a single position and a score, they cannot play in any other position. So in our example, say we have 18 goalkeepers, 22 defenders, 32 midfielders and 28 forwards. We need to select 1 GK (from the 18), 2 defenders (from the 22), 2 midfielders (from the 32), 2 forwards (from the 28) and one not already used non-goalkeeper as a "utility" (from the 100 - 18 = 82).

Currently, I am trying to select the optimal lineup using a brute force technique i.e. generate 1,000,000 random combinations of players which fulfills the above formation and select the lineup which has the highest score.

What other algorithms / techniques could I use to improve upon brute force in this computationally expensive environment (i.e. there are trillions of possible combinations)?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Just to be clear the utility player is a substitute for one of the utility positions? $\endgroup$
    – paparazzo
    Jan 2, 2017 at 19:16
  • 2
    $\begingroup$ 1,000,000 random combinations is not really brute force. That would be Monte Carlo. $\endgroup$
    – paparazzo
    Jan 2, 2017 at 20:07

3 Answers 3

Reset to default
3
$\begingroup$

It is a well known problem, known as the multidimensional knapsack problem, and it is easily solvable by dynamic programming for the parameter / problem size you are dealing with here. A very similar formulation is discussed, for example, here.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ And the name of this well-known problem is the multidimensional knapsack problem. It's easily solved by DP for a problem of this size, where you'll need only $(1+1)(2+1)(2+1)(2+1)(1+1)=104$ DP cells. $\endgroup$
    – j_random_hacker
    Jan 1, 2017 at 21:56
  • $\begingroup$ I assumed those to be constants. Optimization problems like this can get really nasty, I only meant to say that this particular one has a simple DP solution. $\endgroup$
    – quicksort
    Jan 1, 2017 at 22:15
1
$\begingroup$

This problem can be formulated as a mixed integer linear problem very easily.

Sets:

$P$ of all players. Each player costs $c$ and has a score of $w$

$GK,D,M,F$ Form a partition of $P$ (no player can play more than one position)

$NGK=D\cup M\cup F$

Variables:

$x \in \lbrace0,1\rbrace^{P}$ for each candidate player, indicating being chosen for its position.

$u \in \lbrace0,1\rbrace^{NGK}$ for each candidate non-goalkeeper, indicating being chosen as utility.

Constraints: Sums over each position must equal amount allowed for each position: $$\sum_{i\in GK} x_{i} = 1 $$ $$\sum_{i\in D} x_{i} = 2 $$ $$\sum_{i\in M} x_{i} = 2 $$ $$\sum_{i\in F} x_{i} = 2 $$ $$\sum_{u\in NGK} u_{i} = 1 $$

For each non goalkeeper, being chosen as utility implies not being chosen for its other position:

$$ x_i + u_i \leq 1 \quad \forall i \in NGK $$

Total cost must be less than budget:

$$\sum_{i \in P} x_i.c_i + \sum_{i \in NGK} u_i.c_i \leq 50000$$

Objective function: Maximize sum of all scores: $$max \quad \sum_{i \in P} x_i.w_i + \sum_{i \in NGK} u_i.w_i $$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for this, I dont understand the following though: " Sums over each position must equal amount allowed for each position". There is no 'amount allowed' for each position, there is only a limit for the entire team. Is this a mistake? $\endgroup$
    – p_mcp
    Jan 6, 2017 at 2:21
  • 1
    $\begingroup$ Tale a look at the constraints. We are summing over the candidates for each position , counting how much players have been selected for each position. Note the number of players for each position are 1 gk, 2 d, 2 m, 2 f, 1 u $\endgroup$
    – cladelpino
    Jan 6, 2017 at 2:36
-1
$\begingroup$

Short Cut - not perfect but if draft is tomorrow

Create a property productivity = goals / price
Rather than use decimal I would just go 100000 * goals / price

Take the top goalie by productivity
Top 2 defenders by productivity
Top 2 midfielders by productivity Top 2 forwards by productivity
Substitute the least productive defender, midfielder, or forward with top performing utility player if the utility player is a better performer
(assuming max one utility is a substitute)
This is not going to be perfect

If you are over the cap
Drop the highest salary and run again
This is not going to be prefect as some times dropping number 2 salary will be best
Back to if you are over the cap

If you are under the cap it gets trickier
Drop the lowest performer
From that position drop all player with <= goals
Run again
If under the cap back to step one

Brute Force / Random

Look at actual combinations 

gk    18     18
df    22    231
mf    32    496
fd    28    378
ut    76     76

Total number of combinations
59,247,707,904

I you take a random 1,000,000 (random) you are only looking a small fraction
The first short cut would be better than that

Dynamic programming

You can eliminate any player that cost more and produces less goals.

Could also eliminate any two player combos that cost more and produce less goals.

Quickly eliminate over the cap.

Keep the best score and skip if you don't have a chance of making the best score.

Looking at the dynamic programming I am not convinced that you would get the options down sufficiently. Even if every individual combination was dropped in 1/2 with dynamic programming that is 1.8 billion total combinations. At 1 per millisecond that is 59 years.

Would need to get the individual combinations down by a factor of 10x eacj to get it down to 7 days.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't think you can get away with the greedy solution here. $\endgroup$
    – quicksort
    Jan 2, 2017 at 19:15
  • $\begingroup$ @quicksort And I stated not going to be perfect. I also covered brute force. $\endgroup$
    – paparazzo
    Jan 2, 2017 at 19:19
  • 2
    $\begingroup$ Would beat what and by what metric? You provided a (dubious) approximate solution when an exact one was requested -- and even then, I believe a FPTAS for classes of problems even bigger than MILP exists. As an alternative, you provided the trivial brute-force approach, when a better exact solution is well studied in literature. I didn't downvote because I have anything against you, I downvoted because I believe this particular answer you gave is low quality and almost off-topic. $\endgroup$
    – quicksort
    Jan 2, 2017 at 20:20
  • $\begingroup$ @quicksort Not going to argue with you. $\endgroup$
    – paparazzo
    Jan 2, 2017 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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