[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Fair soccer team split problem

From: Michael Hennebry
Subject: Re: [Help-glpk] Fair soccer team split problem
Date: Fri, 13 Apr 2012 10:37:52 -0500 (CDT)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

On Fri, 13 Apr 2012, Andreas F wrote:

For a team of 17 kids I am assigned to split the group into 2 teams for each 
match.  Lets say there are 20 matches in a season.  The objective is to divide 
the group such that each kid spend equally many matches together with any other 
kid (i.e. no two kids play most games on same team, while two almost never play 
on same team).

Using perl I have quickly created a script to randomly create teams. I would 
like it to be *fair*, but this approach isn't fair with only 20 matches (i.e. 

Is it feasible to use glpk to model this?

Yes, but you won't like it.
First of all, exact fairness is impossible.
With 17 kids and 20 matches,
some kid will be on the small team more often than the others.
No pair occurs no more than one more often than any other probably works.
The most straightforward model is an array of binaries:
For match m, kid k is on team team[m][k].
You will need auxillary variables same[m][k1][k2].
same[m][k1][k2]==1 iff kid k1 is on the same team as kidk2 in match , else 0.
In principle, same would not have to be declared integer,
but probably should be.

There are horrible symmetries.
Matches and kids are both fungible.

To alleviate those symmetries, you might generate a random schedule
and minimize some measure of the deviation from that schedule.
You can tell the solver to stop at the first solution.

The constraints are left as an exercise for the reader.

Michael   address@hidden
"On Monday, I'm gonna have to tell my kindergarten class,
whom I teach not to run with scissors,
that my fiance ran me through with a broadsword."  --  Lily

reply via email to

[Prev in Thread] Current Thread [Next in Thread]