Assigning Classes

[Andrew Solomon]

Hi Dave

I think the area Raphael suggests is 'Integer Programming'.

With a bit of luck you'll get acceptable results with *linear* integer
programming using something like this:

http://sourceforge.net/projects/lipside/

but if you wind up getting the majority of students with exactly what they
want and a few outliers getting neither of their choices (turning them into
terrorists) you might have more luck with a non-linear integer programming
solution.

http://en.wikipedia.org/wiki/List_of_optimization_software

If I were doing the non-linear thing I'd probably start experimenting with
this:

http://www.maplesoft.com/contact/webforms/maple_evaluation.aspx

http://www.maplesoft.com/support/help/AddOns/view.aspx?path=GlobalOptimization/GlobalSolveMatrixForm

The fun bit will be modelling your problem into the structures these
systems offer, but I'm pretty sure you can get a close match.

Enjoy! :)

Andrew






On Mon, Sep 9, 2013 at 4:02 PM, Raphael Mankin <raph at mankin.org.uk> wrote:

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