Assigning Classes

[D Perrett]

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'.

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

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.

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.

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.

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