Fair teams assignment #99
Comments
|
i'm doing something similar without success, i think the int or binary options aren't working really well |
|
If I understand what you're trying to accomplish, it sounds like you have the following set up?: a.) An arbitrary number of players need to be assigned to an arbitrary number of teams b.) Each player has a score / rating associated with their skill level (say between level-1:bad to level-10:pro) c.) You want to fill each team with the same number of players (you can't have a team with 1 level-10 player and another team with 10 level-1 players) d.) You want each team to have roughly the same sum-total player score. Is this kind of in the ballpark of what you're trying to accomplish? |
|
@Trigun87 , can you share your model? |
|
@JWally This is exactly what I want to accomplish |
|
@oaeide , This feels way too easy of a solution to be correct; but what about this: 1.) put all your players in an array 2.) Sort the array based on skill level 3.) For each team you have, pop a player out of the array into the team. 4.) Repeat until you no longer have any players to allocate ¯_(ツ)_/¯ |
|
That is indeed a way to do it, but it's not optimal, especially if there is uneven gaps in skill between the players. A very good post about this: https://cs.stackexchange.com/a/93549 |
|
Do you have some data to work with? Is score the only thing to take into consideration, or do gender / age enter into the mix like the problem you linked to? How many players / teams are you working with? |
|
2 teams and up to 10 players, always even number of players. At the moment only their past win rate (in %), but in the future probably a "rating" value between 1 and 10k |
|
@JWally i already open this with a model #90 and the code i use for generate the model but if u do in that way u still need to use binary vars and i think u encounter my same problem (100% cpu for hours without end) |
|
This is tricky, lol. To be honest, I'm not a CS wizard by any stretch; but I think it has to do with something like this:
Where you
Where I'm struggling is coming up with an objective function that gives both teams parity. |
|
@Trigun87,
Can you show what the model generated by your process would look like to
split 10 players across 2 teams so as to minimize the Skill difference
between the two teams.
For example; say your players are:
Alex, Skill: 9000
Brian, Skill 5000
Charles, Skill 3000
Dan, Skill 10
Eli, Skill 10
Frank, Skill 10
George, Skill 10
Hank, Skill 10
Ike, Skill 10
Jon, Skill 10
How would you split them into two teams of 5 players each so that the total
Skill of 1 team is as close as possible to the total skill of the other?
…On Thu, Nov 7, 2019 at 2:03 PM Øyvind Eide ***@***.***> wrote:
@Trigun87 <https://github.com/Trigun87> sorry, I'm having some trouble
decoding how to use what you are suggesting...
@JWally <https://github.com/JWally> do you think this package would be
suited for what I am trying to do?
—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
<#99?email_source=notifications&email_token=AAS6F5YW6GAK3HNPO4A7FZLQSRX73A5CNFSM4JKAL6YKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEDNUJ2Y#issuecomment-551240939>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AAS6F53RUEWFMV6RQDFZ5O3QSRX73ANCNFSM4JKAL6YA>
.
|
|
from ur ex i'm missing something but something like that should be working a solution should be something like a team with 9040 skill and the other with 8030 with r1 = -505 and r2 = 505 if u try to have the 9k and 3k in the same team u get the r1 and r2 bigger and this will increase ur min function the problem is that u have to use 11^n_team bin vars and from what i saw this doesn't work :-D like i said in my issue #90 where i use this https://jsfiddle.net/z5v8cnxL/ if u change the line 33 or 45 for allow the bin or int to works the code go in a loop |
|
I think I have it... For simplicity, say we have 4 players to be split into 2 teams: = players a, score: 9000 = teams team00 Its kind of lengthy to explain, and the model might be more intuitive. If not, feel free to follow up. Basically, you create an instance of each player for each team. For one team, the player's score is positive; and for the other, his score is negative. You put enough constraints in so that each player is used only once, and each team gets exactly {{x}} people. You solve to minimize the absolute value of the score. You can do this by minimizing the score; but putting a constraint on it so the score stays above 0. I'm not sure this is 100% right; but here's an article on how to better do it: http://lpsolve.sourceforge.net/5.1/absolute.htm And here's what the final model looks like: {
"name": "Fair-Teams",
"optimize": "score",
"opType": "min",
"constraints": {
"a": {
"equal": 1
},
"b": {
"equal": 1
},
"c": {
"equal": 1
},
"d": {
"equal": 1
},
"team_00": {
"equal": 2
},
"team_01": {
"equal": 2
},
"constraint_score": {
"min": 0
}
},
"variables": {
"a_team00": {
"a": 1,
"team_00": 1,
"score": 9000,
"constraint_score": 9000
},
"a_team01": {
"a": 1,
"team_01": 1,
"score": -9000,
"constraint_score": -9000
},
"b_team00": {
"b": 1,
"team_00": 1,
"score": 5000,
"constraint_score": 5000
},
"b_team01": {
"b": 1,
"team_01": 1,
"score": -5000,
"constraint_score": -5000
},
"c_team00": {
"c": 1,
"team_00": 1,
"score": 3000,
"constraint_score": 3000
},
"c_team01": {
"c": 1,
"team_01": 1,
"score": -3000,
"constraint_score": -3000
},
"d_team00": {
"d": 1,
"team_00": 1,
"score": 1,
"constraint_score": 1
},
"d_team01": {
"d": 1,
"team_01": 1,
"score": -1,
"constraint_score": -1
}
},
"ints": {
"a_team00": 1,
"a_team01": 1,
"b_team00": 1,
"b_team01": 1,
"c_team00": 1,
"c_team01": 1,
"d_team00": 1,
"d_team01": 1
}
}
which puts B&C on 1 team (8000 points) and A&D on another (9001 points) |
|
@JWally without the last part a player could be in both teams :-D but i still think it will trig the bug of the ints or bins and will never end |
|
try adding this to your model: "options": {
"timeout": 3000
}
|
|
@JWally i tried to solve my LP but got wrong result :-) https://jsfiddle.net/dfnwv8gh/1/ (but i didn't put the ^2 on the min function so this can be the problem) |
|
I'm not sure I follow your model (just curious, why do you start in LP instead of building a JSON). I start with your LP: Which becomes this model: { opType: 'min',
optimize: '_obj',
constraints:
{ score_team_00: { equal: 8535 },
score_team_01: { equal: 8535 },
team_00_players: { equal: 5 },
team_01_players: { equal: 5 },
person_0: { equal: 1 },
person_1: { equal: 1 },
person_2: { equal: 1 },
person_3: { equal: 1 },
person_4: { equal: 1 },
person_5: { equal: 1 },
person_6: { equal: 1 },
person_7: { equal: 1 },
person_8: { equal: 1 },
person_9: { equal: 1 } },
variables:
{ r1: { _obj: 1, score_team_01: 1 },
r2: { _obj: 1 },
p_1_0: { score_team_00: 9000, team_00_players: 1, person_1: 1 },
p_2_0: { score_team_00: 5000, team_00_players: 1, person_2: 1 },
p_3_0: { score_team_00: 3000, team_00_players: 1, person_3: 1 },
p_4_0: { score_team_00: 10, team_00_players: 1, person_4: 1 },
p_5_0: { score_team_00: 10, team_00_players: 1, person_5: 1 },
p_6_0: { score_team_00: 1, team_00_players: 1, person_6: 1 },
p_7_0: { score_team_00: 10, team_00_players: 1, person_7: 1 },
p_8_0: { score_team_00: 10, team_00_players: 1, person_8: 1 },
p_9_0: { score_team_00: 10, team_00_players: 1, person_9: 1 },
p_10_0: { score_team_00: 10, team_00_players: 1 },
r0: { score_team_00: 1 },
p_1_1: { score_team_01: 9000, team_01_players: 1, person_1: 1 },
p_2_1: { score_team_01: 5000, team_01_players: 1, person_2: 1 },
p_3_1: { score_team_01: 3000, team_01_players: 1, person_3: 1 },
p_4_1: { score_team_01: 10, team_01_players: 1, person_4: 1 },
p_5_1: { score_team_01: 10, team_01_players: 1, person_5: 1 },
p_6_1: { score_team_01: 1, team_01_players: 1, person_6: 1 },
p_7_1: { score_team_01: 10, team_01_players: 1, person_7: 1 },
p_8_1: { score_team_01: 10, team_01_players: 1, person_8: 1 },
p_9_1: { score_team_01: 10, team_01_players: 1, person_9: 1 },
p_10_1: { score_team_01: 10, team_01_players: 1 },
p_0_0: { person_0: 1 },
p_0_1: { person_0: 1 } },
ints:
{ p_0_0: 1,
p_0_1: 1,
p_1_0: 1,
p_1_1: 1,
p_2_0: 1,
p_2_1: 1,
p_3_0: 1,
p_3_1: 1,
p_4_0: 1,
p_4_1: 1,
p_5_0: 1,
p_5_1: 1,
p_6_0: 1,
p_6_1: 1,
p_7_0: 1,
p_7_1: 1,
p_8_0: 1,
p_8_1: 1,
p_9_0: 1,
p_9_1: 1 } }Which isn't feasible. |
|
r1 and r2 are free and is the difference from the team score to the avg value of each team, so if u have p0 +p4+p5+p6+p7+R0 u have r0 at 500 or something near :-) PS i don't use the json bc i didn't know the syntax ... but i think i got it how it works is a matrix^t of my problem (if i got it right) :-) PPS u writed this but r2 (should be linked to team_00, was my r0) |
|
@JWally Thank you, your solution seems to be exactly what I was looking for. I have only been able to do some easy testing so far, but it looks to be working perfectly. I even think I managed to figure out how to keep some players on the same team. The whole calculation is very fast as well, just a couple of ms 👍 |
|
Thanks! Here's something I was playing with to test. I'm still trying to figure out how to do this for more teams, but am having trouble conceptualizing the objective function. I'll close this for now. var fs = require("fs");
var solver = require("../../src/solver");
var teams = ["team 1", "team 2"];
var people = [];
// ********* CHANGE NUMBER OF PEOPLE HERE ***************** //
// Fill Out People
for(var i = 0; i < 16; i++){
people.push({
"name": i,
"score": parseFloat((Math.random() * 10000).toFixed(0))
});
}
people.sort(function(a,b){return b.score > a.score ? -1: 1});
// Build out the model;
var model = {
"name": "TEAMS",
"optimize": "score",
"opType": "min",
"constraints": {
"constraint_score": {"min": 0}
},
"variables": {},
"ints": {},
"options": {
"timeout": 20000
}
}
teams.forEach(function(team){
// Each Team requires people.length / team.length people...
model.constraints[team] = {"equal": people.length / teams.length};
})
people.forEach(function(person){
// add a self constraint for each person
model.constraints[person.name] = {"equal": 1};
// Everything going forward is a combo of team, person...
for(var j = 0; j < teams.length; j++){
// Lets name this variable a combo of name / team
//
// (THIS IS HORRIBLE! SHAME! SHAME! SHAME!)
var var_name = `{"team": "${teams[j]}", "score": ${person.score}, "person": "${person.name}"}`;
// Maybe this works / maybe it doesn't
var sign = j % 2 == 1 ? -1 : 1;
// Add An Int constraint on the Variable we're 'bout
// to create...
model.ints[var_name] = 1;
// Build out the variable...
model.variables[var_name] = {};
model.variables[var_name][person.name] = 1;
model.variables[var_name][teams[j]] = 1;
model.variables[var_name].score = person.score * sign;
model.variables[var_name].constraint_score = person.score * sign;
}
});
var solution = solver.Solve(model);
console.log({
"feasible": solution.feasible,
"result": solution.result,
"integral": solution.isIntegral
});
delete solution.feasible;
delete solution.result;
delete solution.isIntegral;
delete solution.bounded;
// *BARF!*
var results = Object.keys(solution).map(function(x){return JSON.parse(x)});
results.sort(function(a,b){return a.score > b.score ? -1 : 1})
var final_teams = {};
results.forEach(function(x){
if(!final_teams[x.team]){
final_teams[x.team] = [];
}
final_teams[x.team].push(x);
});
console.log(final_teams); |
I'm new to LP, and I was wondering if it's possible to use this library to assign players to teams based on a player score? I'm trying to set up a model to get balanced teams, but I can't really see how it should be structured.
The text was updated successfully, but these errors were encountered: