Finding optimal combination with multiple constraints

Question

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.

Answer 1

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