-3

I manage co-curricular programs for the school I work at. Until now, they have signed up on a google form on a first-in best-dressed capacity, but there is lots of complaints about how some students get all of their preferences, while some get none.

As there is 1000+ students at this school and over 50 activities, it would be impossible to sort through their preferences manually and assign the classes. Is there another algorithm/code/software that will sort the classes so that:

  1. Everyone gets at least one preference
  2. Class sizes can be set to different limits
  3. Students can be assigned to more than one class after everyone has received at least one until the classes are full?

I'm a bit rusty so explanations/solutions for dummys would be super appreciated.

Thanks!

Hayley

  • 2
    I'm not sure what exactly is your question. If you're asking about an existing algorithm, chances are that the problem is too specific for that. I would rather see you coming with your solution and ask for help for the parts of it where you encounter specific problems. – Arseni Mourzenko May 27 '18 at 22:41
  • I recently listened to a podcast episode dealing with these sorts of problems from an economist perspective. It may point you in the right direction: econtalk.org/archives/2015/07/alvin_roth_on_m.html. In particular the section about assigning students to schools which I think is similar to your case – Winston Ewert May 27 '18 at 22:52
  • Thank you! I will definitely check that out. I would love to offer my own solution but I wouldn't know where to start - that's why I was hoping there might be code/software that people use. – Hayley Kennealy May 27 '18 at 23:08
0

It seems the current situation is: if someone signs up early enough when plenty of spots are still available, he/she will get everything asked for. You want to change that to a round robin sort of assignment.

You should wait for a number of applicants/requests that will fill every available spot. This can be easily checked for after each form being filled in. Once you have those, you close the registration. Sorry! Better luck next year.

Then you sort your applicants in the order of received applications. It is with this list of applicants you start to iterate, assigning the top preference of each applicant to an available class on each round. When you run out of spots you should have everything filled in a fair manner.

0

First, this really should be asked somewhere like stackoverflow. Software engineering is more than algorithm selection.

This is going to sound strange, but the most easily applicable algorithm (class of algorithms really) to your situation is Linear Programming, or its counterpart Integer Programming. The idea is to encode your constraints as a set of linear equations (perhaps restricted to integer solutions) and apply general-purpose solvers to either find a solution or prove none exist.

  • One advantage of this approach is the existence of FOSS solutions expressly designed to solve such problems quickly.
  • Another advantage is the ability to tweak your constraints and express many possible ideas without any major tweaks to the algorithm.

One way to go about this would be to define a binary variable x_s,a for each student s and each activity a expressing whether they will be in that activity or not and p_s,a expressing whether they preferred it or not. Then we define a fairly long list of inequalities (these can and should be programatically generated).

  • To enforce class size limits, for each activity a the sum (x_s1,a)+(x_s2,a)+...+(x_sn,a) can be bounded by your favorite constant.
  • To enforce preferences, for each student s you also require that (x_s,a1)+(x_s,a2)+...+(x_s,an) is at least 1, where the ai are restricted to be the activities that student prefers.
  • To enforce some sort of fairness, you can have an equation for each pair of students guaranteeing that no student is in more than one more activity than the other (if such balancing is desired).
  • To attempt to get full class sizes, you can set the linear objective function you want to optimize to simply be the sum of all the x_sa.
  • You'll need some other constraints for realism, for example that all the x_sa are non-negative and that they are bounded above by 1.

If you want more help with this approach, Dr. Nathan Axvig is always looking for new operations research projects. I've talked with him at a couple conferences, and he's knowledgeable and friendly. To quote his bio, "Dr. Axvig is keenly interested in establishing partnerships with businesses, non-profit organizations, and governments with the joint goals of providing his clients with useful solutions as well as giving his students valuable experience working on real real-world problems. To this end, Dr. Axvig has supervised a number of undergraduate consulting projects and is always looking for more."

  • Thank you so much for this! I am trying out some different scenarios but a colleague suggested something quite similar. Will update on how I go when I have time to run a full test. Thanks everyone! – Hayley Kennealy May 29 '18 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.