Using Julia to solve the student final project allocation problem

Hey Sui,

What you have here is a classic assignment problem in Operations Research, where I work. Thus, my answer will be based on this.
Overall, you will have to first choose one of the two scenarios. You can choose to look for the optimum to your problem (case A), or just for a good solution to your problem (case B).
The code you screenshotted denotes a case A, as you are using linear programming (JuMP). If your model is small (Not a million variables/restrictions/etc. it will give you the solution quickly enough).
Case A: You are probable looking for a model with a binary decision variable X{i,j,k}, which has a value of 1 if a student “i”, with a major in “j”, get assigned to the project “k”, and 0 otherwhise. Each of the “pieces of information” you were given will become a set of restrictions (For example, the sum of all the decision variables for each of the projects must be equal to 1 will force your model to assign a single student per project). You should be looking into either knapsack problems like the one shown here for Convex.jl (Binary (or 0-1) knapsack problem · Convex.jl) or directly assignment problems in Julia (Beginners question: how to formulate this assignment/scheduling problem? - #2 by odow)
You need to only create one type of restriction for each information given, and then iteratively add them to the JuMP model.
I’ll just raise case B so that you are aware of it. Using dynamic programming (That is, iterating through the problem, e.g the student-project combination) you can make up a decision making process to find good solutions for your problem. For example, you could order your students’ first picks into a single array, and then assign them to your projects’ array sorted by priority. Then, do the same with your students’ second picks, and so on until all students are assigned. This solution will likely not find the optimum, but it can give you a very good solution, and you know it will converge to a solution under a limited time (depending on your problems size) unlike the LP, which you will never know when it will find your answer (but it’ll likely be very quick).
Best,
S.

10 Likes