Assigning Classes
Raphael Mankin
raph at mankin.org.uk
Mon Sep 9 16:02:42 BST 2013
Second thoughts: I was slightly wrong in my previous reply.
This is not a 0/1 problem so the Hungarian does not apply. However it is
a general integer transportation problem with limited link capacities.
The Hungarian would apply if you were assigning students to private
tutors; that is a 0/1 problem.
Each student represents a bundle of k resources that have to be
'transported' to the destinations (classes), where each student has to
attend k classes. k can be different for each student.
Each destination has a capacity: the size of the class.
Each 'link' joining a student to a class has a cost: the student's
unhappiness at taking that class. It also has a limiting capacity of 1
(a student can only attend a class once).
A web search of 'integer transportation problems' will find the
algorithm.
On Mon, 2013-09-09 at 12:45 +0000, Dave Cross wrote:
> I have offered to help a friend[1] solve what sounds like an
> interesting problem.
>
> She has a list of courses that are offered. Some of these courses have
> a maximum class size and others are effectively infinite (I don't
> believe that second part, but hey!) There are about thirty of these
> courses.
>
> She also has a list of students who have decided which courses they
> are interested in doing. For each student, we have their five
> favourite choices - ranked from 1 to 5.
>
> The problem is, of course, to find the optimum arrangement of students
> to courses so that each student is doing the course as close to their
> first choice as possible.
>
> There are, however, a couple of extra constraints.
>
> 1/ Each course much be run with at least two students. So if there is
> a course that has no students choosing it, two students must be
> assigned to it.
>
> 2/ Each student actually does two courses. So if someone is forced
> into a course because of rule 1 above, we can sweeten the pill
> slightly by guaranteeing (insofar as we can) that they get their first
> choice for their other course.
>
> I'm sure that most of this must be a previously solved problem. But
> I'm not sure where to start looking.
>
> Any ideas would be much appreciated.
>
> Cheers,
>
> Dave...
>
> [1] And those of you who know that my wife is a teacher might well
> draw conclusions about who that friend is :-)
>
More information about the london.pm
mailing list