# Optimization of discrete choice

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.

• How are the scores being computed? – theyaoster May 22 '17 at 21:04
• Its hit and throw in meters times 8 and sum the whole 3 person team, then run is 2400-60*T where T is the sum of the runners' time in seconds. I see I got a mistake in my simulation. I shouldn't have multiplied them already (by 8 the first two and 2400-60T) but rather minimise their running time and because of that keep the first two on original scale as well. I will edit it tomorrow :) – Jan Sila May 22 '17 at 21:41
• Its all concisely here: supercup.ptlab.cz/download/2017/…. For now I'm disregarding the last infield play part – Jan Sila May 22 '17 at 21:48

## 1 Answer

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.

• hi, thanks a lot! That looks exactly what I need. I'm on my way abroad now, but I have a look at it over the weekend and get back to you. Thanks a lot! – Jan Sila May 26 '17 at 12:45
• Excellent! Thanks a lot. Its exactly what I needed. – Jan Sila May 28 '17 at 18:02