Assigning Classes

[Raphael Mankin]

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