Assigning Classes

[Raphael Mankin]

On Mon, 2013-09-09 at 23:07 +0100, D Perrett wrote:
> I suspect this is the sort of problem where no solution will give you
> consistently unremarkable results if in the long run there are any
> unspoken requirements like 'students shouldn't be able to game the
> system by lying about their preferences'.

Indeed, there are generally many 'optimal', least cost, solutions.

> 
> Leaving that aside, a naive (computationally expensive) solution would
> be to take all the combinations of assigning students to courses, rule
> out the impossible, compute the 'optimability', and sort. That would
> be vast, you'd start by creating an array of length @courses **
> @students (more when you include the 'two courses' rule).

This approach has exponential complexity. Definitely infeasible. 
> 
> A better option (memorywise) might be to write a function that takes a
> list of students and assigns them one by one, measuring the accrued
> dissatisfaction as it goes. Where possible, it assigns people to where
> they want to be. It rejects a solution if it finds at any point a) it
> has empty classes and no students remaining; b) it has students
> remaining, but no acceptable place to put them (e.g. if none of
> choices 1-5 are present), or an unacceptable level of dissatisfaction
> has been reached (e.g. it's already exceeded the dissatisfaction of
> its best-case scenario so far). If a solution is rejected, it
> backtracks to the last decision it made, and makes a different
> decision. It will stop after either a) reaching a perfect solution (or
> an acceptable solution, if you can come up with a tolerable score), or
> b) running out of solutions. This would still be the same number of
> end-solutions, and getting to each solution would be slower, but it
> might not break trying to find an acceptable solution.

This is an informal description of what is done in several of the
existing algorithms.

> 
> Another option that comes to mind is randomly allocating them all,
> ensuring required conditions are filled, then iterate over the
> students, probably starting with the most dissatisfied to begin with.
> Where students are free to move without breaking required conditions,
> they should move to the class they prefer. Otherwise, they should look
> for trades (starting in their most preferred class). The trade need
> not be mutually beneficial, but it should benefit the overall score.
> Keep iterating over them all until things stabilise. Try this a few
> times with different random starting points and see if and how the
> score improves.

Synthetic annealing. It works, but it is slow. OTOH if the optimisation
function has many minima it can often find a better solution than other
techniques.


> 
> You could also try pulling some good results from the backtracker and
> using them as bases for the trading mechanism.
> 
> I think the two courses rule is a complication that can be partially
> by giving the most dissatisfied in the first course the first choice
> in the second course. Although really, we should be optimising for
> satisfaction across both courses simultaneously. which is still
> possible if you're using the backtracker method - you keep going with
> each solution, oonce you've allocated students in the first, you start
> allocating students to the second (dissatisfied first) until you've
> got a dissatisfaction figure for the two courses combined or until you
> need to backtrack back into the first course.

I don't know of any good techniques for the 'successive assignment'
problem. It was a problem I tried to handle many years ago when
assigning a smallish (~100) pool of engineers to a large (several k)
pool of repair jobs. In the end, we just did it one iteration at a time:
as each engineer reported in at the end of his current job we computed a
new assignment from scratch.

> 
> Daniel
> 
> On 9 September 2013 18:17, Andrew Solomon <andrew at illywhacker.net> wrote:
> > 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 :-)
> >> >
> >>
> >>
> >>