Fair teams assignment

[oaeide]

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.

[Trigun87]

i'm doing something similar without success, i think the int or binary options aren't working really well

[JWally]

@oaeide;

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?

[JWally]

@Trigun87 , can you share your model?

[oaeide]

@JWally This is exactly what I want to accomplish

[JWally]

@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

¯_(ツ)_/¯

[oaeide]

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

[JWally]

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?

[oaeide]

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

[Trigun87]

@JWally i already open this with a model https://github.com/JWally/jsLPSolver/issues/90 and the code i use for generate the model @oaeide the code of my model is almost the same that can be used for ur problem my problem was to allocate people in a week u have to do something like skill1 + skill2+skill3 +rest = medianOfSkills // for each team min rest1 + rest2

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)

[oaeide]

@Trigun87 sorry, I'm having some trouble decoding how to use what you are suggesting...

@JWally do you think this package would be suited for what I am trying to do?

[JWally]

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

• create multiple versions of the same person (a_0, a_1)
• both versions have a 'self' attribute (a) that has a max of 1 so that only 1 version can be used

Where I'm struggling is coming up with an objective function that gives both teams parity.

[JWally]

@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 notifications@github.com 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 https://github.com/JWally/jsLPSolver/issues/99?email_source=notifications&email_token=AAS6F5YW6GAK3HNPO4A7FZLQSRX73A5CNFSM4JKAL6YKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEDNUJ2Y#issuecomment-551240939, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAS6F53RUEWFMV6RQDFZ5O3QSRX73ANCNFSM4JKAL6YA .

[Trigun87]

@JWally

from ur ex tot skill 17070 avg = 8535

min r1^2+r2^2  // with ^2 is always a sum with positive numbers and if u have a team with 9000 difference vs a team with 0 difference u get a bigger total vs 2 team with 4500 both
t1: p11*9000+p21*5000+p31*3000 .... + r1 = 8535
t2: p12*9000+p22*5000+p32*3000 .... + r2 = 8535
p11+p21+p31... = 5
p12+p22+p32... = 5
bin p*

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 and the min function should be min -505^2 + 505^2 = 510050

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 https://github.com/JWally/jsLPSolver/issues/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

[JWally]

I think I have it...

For simplicity, say we have 4 players to be split into 2 teams:

= players

---

a, score: 9000 b, score: 5000 c, score: 3000 d, score: 1

= teams

---

team00 team01

---

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)

[Trigun87]

@JWally if u have 3 teams what u do? i think this can't work :-) now that i think i forgot a rule on my LP

min r1^2+r2^2  // with ^2 is always a sum with positive numbers and if u have a team with 9000 difference vs a team with 0 difference u get a bigger total vs 2 team with 4500 both
t1: p11*9000+p21*5000+p31*3000 .... + r1 = 8535
t2: p12*9000+p22*5000+p32*3000 .... + r2 = 8535
p11+p21+p31... = 5
p12+p22+p32... = 5
bin p* // or int
p11+p12=1
p21+p22=1
[...]
px1+px2=1

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

[JWally]

@Trigun87 ;

try adding this to your model:

"options": {
    "timeout": 3000
}

[Trigun87]

@JWally with that u get a wrong result :-)

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)

[JWally]

@Trigun87,

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:

min: r1 + r2

score_team_00: 9000 p_1_0   + 5000 p_2_0   + 3000 p_3_0  + 10 p_4_0  + 10 p_5_0  +  p_6_0  + 10 p_7_0  + 10 p_8_0  + 10 p_9_0  + 10 p_10_0  + r0 = 8535
score_team_01: 9000 p_1_1   + 5000 p_2_1   + 3000 p_3_1  + 10 p_4_1  + 10 p_5_1  +  p_6_1  + 10 p_7_1  + 10 p_8_1  + 10 p_9_1  + 10 p_10_1  + r1 = 8535
team_00_players: p_1_0 + p_2_0 + p_3_0 + p_4_0 + p_5_0 + p_6_0 + p_7_0 + p_8_0 + p_9_0 + p_10_0 = 5
team_01_players: p_1_1 + p_2_1 + p_3_1 + p_4_1 + p_5_1 + p_6_1 + p_7_1 + p_8_1 + p_9_1 + p_10_1 = 5
person_0: p_0_0 + p_0_1 = 1
person_1: p_1_0 + p_1_1 = 1
person_2: p_2_0 + p_2_1 = 1
person_3: p_3_0 + p_3_1 = 1
person_4: p_4_0 + p_4_1 = 1
person_5: p_5_0 + p_5_1 = 1
person_6: p_6_0 + p_6_1 = 1
person_7: p_7_0 + p_7_1 = 1
person_8: p_8_0 + p_8_1 = 1
person_9: p_9_0 + p_9_1 = 1

int p_0_0
int p_0_1
int p_1_0
int p_1_1
int p_2_0
int p_2_1
int p_3_0
int p_3_1
int p_4_0
int p_4_1
int p_5_0
int p_5_1
int p_6_0
int p_6_1
int p_7_0
int p_7_1
int p_8_0
int p_8_1
int p_9_0
int p_9_1

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. I'm guessing because the first constraint you have is an equality constraint so that all scores equal 8535; but no combination of scores (that I see) can give that result; but I could be wrong. Am I missing something?

[Trigun87]

@JWally

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 :-) same for the other team

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) :-) still is hard for me to think a problem in that way instead of the linear way :-D is already hard to formulate a LP :-)

PPS u writed this

r1: { _obj: 1, score_team_01: 1 },
     r2: { _obj: 1 },

but r2 (should be linked to team_00, was my r0)

[oaeide]

@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 👍

[JWally]

Thanks!

Here's something I was playing with to test. Its throwaway, but might help with something /shrug ?

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