Optimization of discrete choice

Question

I've been struggling to solve this:

Imagine we have a baseball competition and I'm coaching a team. I have 3 disciplines; throw,hit and timed run. I have 20 kids on the team and for each discipline, I can only select 3 players, so in total 9 players out of 20.

Regardless of probability distribution, if I know their performance:

"player","throw","hit","run" "player_1", 21.3, 37.7, 15.9 "player_2", 31.6, 25.6, 13.8 "player_3", 34.4, 26.2, 16.2 "player_4", 24.5, 30.6, 15.8 "player_5", 27.6, 21.0, 12.8

My idea is to pick all triples in each discipline and calculate the total score - the sum of the scores of the triples across disciplines. Then sort the total scores from the highest and find the best combination that has 9 unique players. But is there maybe a classic optimization setup which could solve this?

At this moment I make combinations of all players (in reality there has to be at least 9 players, at most 12, or 15 at the very most) and calculate scores for each discipline. So here is a team of players 1,2 and 3 and if I chose this team to do throw, they make 699.669, if they were chosen to hit they make 716.366 etc..

array([[('player_1', 'player_2', 'player_3'), 699.669, 716.366, 560.84],
       [('player_1', 'player_2', 'player_4'), 620.174, 752.086, 574.684],
       [('player_1', 'player_2', 'player_5'), 645.072, 675.044, 693.528],
       [('player_1', 'player_2', 'player_6'), 709.838, 754.494, 553.737],
       [('player_1', 'player_2', 'player_7'), 588.217, 732.063, 559.164],
       [('player_1', 'player_2', 'player_8'), 768.252, 769.758, 571.34],
       [('player_1', 'player_2', 'player_9'), 603.737, 685.582, 652.956],
       [('player_1', 'player_2', 'player_10'), 649.677, 796.177, 545.73],
       [('player_1', 'player_3', 'player_4'), 642.474, 756.265, 482.426],
       [('player_1', 'player_3', 'player_5'), 667.372, 679.223, 601.27],
       [('player_1', 'player_3', 'player_6'), 732.138, 758.673, 461.479],
       [('player_1', 'player_3', 'player_7'), 610.517, 736.243, 466.906],
       [('player_1', 'player_3', 'player_8'), 790.552, 773.937, 479.082],
       [('player_1', 'player_3', 'player_9'), 626.037, 689.761, 560.698],
       [('player_1', 'player_3', 'player_10'), 671.977, 800.356, 453.472],
       [('player_1', 'player_4', 'player_5'), 587.877, 714.943, 615.114],

So basically now my problem is to choose 3 teams, each for 1 discipline which maximises overall gain for the team. Hence there has to be 9 unique players.

Many thanks.

Answer 1

This problem is a linear assignment problem(https://en.wikipedia.org/wiki/Assignment_problem) which means there are many ways to solve it in polynomial time. To formulate it in this way let there be nine non zero tasks which are equivalent to being selected and 11 zero tasks which have penalty zero, which are equivalent to not being selected. Each player can obviously only do one task. This means there are now an equal amount of tasks and agents which means it is now a linear assignment porblem. The hungarian algorithm (https://en.wikipedia.org/wiki/Hungarian_algorithm) is a good choice for this. you need to model your scores as negative numbers, or assign a proportional penalty. The penalties for zero task are still zero in this formulation meaning you can basically ignore them. as soon as you have optimal choices for the 9 non zero tasks, assign the last 11 tasks randomly. you can maybe make your problem smaller by eliminating players that are strongly dominated by 9 players in each field (do not have to be the same players) but this only gives small gains since not many players will be that bad. The wikipedia should give you an idea of how to implement the hungarian algorithm, but please let me know if you need more help.