1
$\begingroup$

I'm trying to find an optimal combination of players given certain constraints.

There are ~300 players. 10 players has to be chosen in the combination.

Each player has an assigned value. The goal is to optimize for the sum of their values.

Constraints:

  • Each player has a price. The sum of their prices has to be less than x.
  • Each player has a position (D, M, F). There has to be [3..5] D players, [3..5] M players and [1..3] F players, again, 10 players in total.
  • Finally, each player has a team (20 different teams). There mustn't be more than 3 players from the same team.

Brute forcing this takes simply too much time because there are tons of permutations. As far as I've researched, this seems to be most similar to multi dimensional knapsack problem and proposed way to do it should be dynamic programming.

However, beyond this information, I'm still not sure how to translate it into code. I'm using python.

$\endgroup$

1 Answer 1

0
$\begingroup$

I suggest you express this as an instance of integer linear programming, and use an off-the-shelf ILP solver. You will have a 0-or-1 variable $x_i$ for each player, where $x_i=1$ means that the $i$th player is selected and $x_i=0$ means that the $i$th player is not selected. Each constraint you list can be expressed as a linear inequality over the $x_i$'s. Then you can use an ILP solver to search for a feasible solution (or one whose price is minimal).

$\endgroup$
1
  • $\begingroup$ Thanks, I followed your advice and used this as a reference for writing my Python script: developers.google.com/optimization/mip/mip_var_array I've written my problem as a set of linear inequalities and the optimal solution can be found under a second! Thanks a lot! $\endgroup$
    – Liopan
    Jul 16 at 14:45

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.