C
Clyde Ingram
At my son's school, each year has about 45 children, in 3 classes of
15
children each. (Actually, each classroom contains 30 children -
banding together 15 from each of 2 years. But that is irrelevant.)
At the end of the summer term, the teachers have the difficult task of
deciding how to re-group the 45 children into 3 classes
for next year.
They ask each child to list 4 friends they would like to be in the
same
class with next year (the next autumn term).
The child ranks each friend according to strength of friendship.
Children
do not necessarily agree - just because Tom lists Dick and Harry, does
not
mean that Dick or Harry list Tom, or that they agree with how he ranks
them.
The teachers have the problem of how to split the 45 children into new
classes for next year, so that all children are as happy as possible.
(They also take the chance to separate children who squabble!)
This sounds like a straight-forward problem in optimization (but with
45x4
variables?). Unfortunately my mathematics is very rusty, and I do not
know
what algorithm to use to get a solution.
One of my mathematically-minded colleagues suggests constructing a
directed graph, with one vetex per child, and a directed edge per
preference - with a cost according to weighting. Somehow, I have to
partition the vertices into 3 subsets, cutting the minimum total cost
of weighted edges. Sounds plausible.
I would appreciate any advice on the algorithm and how to implement
it.
Are there any modules to do such an optimisation - or should I build
on Graph.pm, which I am just starting to look at, whilst wading into
"Mastering Algorithms with Perl", Chapter 8: "Graphs".
Thank-you and regards,
Clyde Ingram
15
children each. (Actually, each classroom contains 30 children -
banding together 15 from each of 2 years. But that is irrelevant.)
At the end of the summer term, the teachers have the difficult task of
deciding how to re-group the 45 children into 3 classes
for next year.
They ask each child to list 4 friends they would like to be in the
same
class with next year (the next autumn term).
The child ranks each friend according to strength of friendship.
Children
do not necessarily agree - just because Tom lists Dick and Harry, does
not
mean that Dick or Harry list Tom, or that they agree with how he ranks
them.
The teachers have the problem of how to split the 45 children into new
classes for next year, so that all children are as happy as possible.
(They also take the chance to separate children who squabble!)
This sounds like a straight-forward problem in optimization (but with
45x4
variables?). Unfortunately my mathematics is very rusty, and I do not
know
what algorithm to use to get a solution.
One of my mathematically-minded colleagues suggests constructing a
directed graph, with one vetex per child, and a directed edge per
preference - with a cost according to weighting. Somehow, I have to
partition the vertices into 3 subsets, cutting the minimum total cost
of weighted edges. Sounds plausible.
I would appreciate any advice on the algorithm and how to implement
it.
Are there any modules to do such an optimisation - or should I build
on Graph.pm, which I am just starting to look at, whilst wading into
"Mastering Algorithms with Perl", Chapter 8: "Graphs".
Thank-you and regards,
Clyde Ingram