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

[Michael Hennebry]

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. 
> solutions).

> 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.
same[m][k1][k2]==same[m][k2][k1].
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