Highest possible value of combinations of 5

According to https://www.heroescounters.com/teampicker a Hero has a synergy value with another hero, Heroes of the Storm have 60+ heroes each one with a synergy value for example:

HeroID  Synergy.With.HeroID      Synergy.Points
1               2                       97
1               3                       95
1               4                       94
45              1                       2
45              2                       11


A Team in heroes of the storm have 5 heroes, and the full synergy of a team is calculated by the formula:

Team_total_synergy = Synergy_Points(Hero1 with Hero2) +
mean(Synergy_Points(Hero3 + Hero1) + Synergy_Points(Hero3 + Hero2)) +

mean(Synergy_Points(Hero4 + Hero1) + Synergy_Points(Hero4 + Hero2) + Synergy_Points(Hero4 + Hero3)

[And so on... till Hero5]


Explaining the formula: Each Synergy Value after the synergy of Hero 1 and Hero 2 is calculated by the Mean of that Hero with the rest of the team, When Hero5 is added up i got the synergy of the team summing all the values.

My Answer is, How can I find the Team with the greatest possible synergy given that formula, and how can I write the code to find it given the possibility there are 64 Heroes(approximately) without brute-forcing all all 64^5 combinations of heroes.

• Looks like a reverse traveling sales man problem... Jun 9 '17 at 14:22
• it's only 2^30 combinations, that is doable in an hour. Jun 9 '17 at 14:22
• You actually have $\binom{64}{5}$ combinations of heroes (unless you can have twice the same hero). Can you specify the formula ? Is it $\sum_{i,j,i \neq j} synergy_{i,j}$ ? Or do you calculate is differently for different hero numbers ? Jun 9 '17 at 14:24
• You can't have twitch the same hero and hero synergy is calculated the same way for all possibilities(just picking the Points Value from Dataset), the formula you gave is correct. Jun 9 '17 at 17:36

Define a graph $G=(V,E)$, where $V$ is the set of heroes, and $E$ a link between two heroes, with their synergy value $s_{i,j}$ for $(i,j) \in E$.

Define, for $i \in V$, $X_i$ the boolean variable equal to 1 iff you take hero $i$

Define additional real positive variables $Y_{i,j}$ for the cost, which are equal to 1 in the final solution iff heroes $i$ and $j$ are selected.

You want to solve

$\max \sum_{(i,j) \in E} Y_{i,j}s_{i,j}$

such that $\sum_{i \in V}X_i = 5$

$\forall (i,j) \in E, Y_{i,j} \leq X_i$

$\forall (i,j) \in E, Y_{i,j} \leq X_j$

other formulations are possible. I like this one, since it only has $|V|$ boolean variables

If that does not work (too much computation time), try to modify some already existing algorithms to find cliques, such as the one from Tarjan and Trojanowski.

Sidenote, you are lucky that the number of heroes is limited by 5. Otherwise, it would be a maximum clique problem, which is NP-complete.

• Sounds Great! Can you suggest me an integer programming framework to implement this on python or R? Jun 9 '17 at 17:40
• @CiaoVasconselos I think glpk (open source) and cplex or gurobi (licenced) both have interfaces with python, for R I am not sure. I don't use them though. Jun 10 '17 at 0:23