Using Julia to solve the student final project allocation problem

sui · December 1, 2020, 1:27am

I am doing a project that I have to use Julia code to solve a student’s final project allocation problem. I am kind of new to this kind of coding and new for Julia. I need some help with this.

Start with the problem, I have data for students and projects.

For students, I have 137 students who come from 4 different majors(such as, EE, ME, BIOM, and EMGT). For every student, they have chosen 10 projects that they want to work on in Rank. (For example, student 1 want to do project 10, 1, 5…)

On the project side, I have 3 pieces of information. 1, all project has their request for the student(For example, project A need EE student but other major does not require). 2, All project has a priority rank from 1 to 4. 1 is the most important and 4 is the less. 3, the Most project has funding. But Funding does not relate to the priority. For example, project A has $20,000 as funding, but the priority level is 2. Project B may not have any funding, but it is priority 1. In this case, I have to make sure the project B has the right student, but project A is less important.

For all students, they can only get into one project. In this project, I have to make sure that all priority 1 projects get the right student and try to make sure most students get into their first rank of project. For now, I have loaded the student and project information in Julia as [load student and project inform][1]

The workspace looks like this. [Data is the student inform, I only pick the top 4 of student rank of

I am looking to get the solution to this project. Like array for all student allocation. And plot the data like how many student’s projects is their first pick.

If possible, please give me some idea about how to work on the next. If there is a close example of Julia code will be great.

seba754 · December 1, 2020, 2:03am

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.

anon92994695 · December 1, 2020, 2:10am

If you think of each ranking as a weight, you can solve this assignment problem a variety of ways. One way, I think, I’m rusty anyways, should be via the hungarian algorithm. There are a few implementations of this in julia, but this one’s readme looked from a cursory glance anyway - to be pretty easy.

https://github.com/Gnimuc/Hungarian.jl

if you do this, please write up your approach :).

sui · December 1, 2020, 3:28am

Hello
Thank you for your information. I think I am working on case A as you said. however, I just really do not have an idea about the type of code. I am thinking of creating an array that is 137X35 (Student X project). However, I just have no idea about what would be next. If possible, will you please give me a similar but shorter and smaller code? And will you please explain a little bit about the code? That will help me understand how to program this type of thing faster.
For case B, it is a really interesting way to do it. I had never heard anyone told me that I can use Julia like that. Would you please explain a little bit more about that?

odow · December 1, 2020, 3:57am

Hi there! If you’re new to Julia, make sure you read: Please read: make it easier to help you.

If this question is a homework problem, you should be mindful of your schools honor code when asking “will you please give me a similar but shorter and smaller code?”

In general, you are more likely to receive help if you simplify your problem, outline what you have attempted so far, and provide code for where you got stuck, rather than asking for a complete solution approach.

seba754 · December 2, 2020, 1:08am

Hey Sui,

I’m a bit confused now, since this code line you posted (below) means you should have an understanding of optimization and linear programs.
using JuMP, GLPK, LinearAlgebra
Also, I googled the code for your course, and it involves Linear modelling, so you should be able to achieve something as described in the “solution by linear programming” of the assignment problem in wikipedia (Assignment problem - Wikipedia).
Don’t focus on the data structure, focus on first having the Linear Program that represents your problem. The code will just be the tool to solve this.
If you can start sketching the Linear Program, I think the community will be able to help you much more efficiently, having @odow’s comment present.
Unfortunately, I will not be able to provide the code you ask for, as it will be only a few lines long, and honestly too easy to adapt. I can, however, give you an outline of it (you can search for the how to implement here: https://jump.dev/JuMP.jl/stable/quickstart/)

Declare a “Model” variable
Attach the variables you will use (x_ijk, and/or y_i, etc), specify “Bin” if you’ll stick to 0-1 programming
Attach an objective function. Think about what gives you a sense of “improvement”, is it the students’ priorities, or the project ranking?
Attach all the restrictions. You need to think about each “piece of info” as a group of restrictions that will act over a “group of conditions”. For every “i” student, you’ll need a restriction, so for all the set of students, you’ll need a set of restrictions.
Solve the model using the aptly named “optimize!” function
Usually, you would return the solution vector using the “value(NameOfVariable)” function. In this case, since your variable will probably have an “ijk” index, you might need to use “value.(VariableName)” to retrieve all values if you want to do something like “sum()” or else(The dot operator will apply the “value” function to all components of the solution).

Best of luck,
S.

sui · December 2, 2020, 6:17am

Hello thanks for your time
I have kind of experience with the code, but not something like this. But yes, I am working on case A as you said. But I have some questions about how to locate the data as I want to.
1, I have students’ data as student id and top 4 picks. I am trying to load it into an array as 137x34 (student X project). However, the data for student pick is the project numbers. How can I load into the array? For example, I like to set student A as (1 0 0 … 10 9 …00…8 …7) I like to give the student pick a score as the first pick is 10, the second will be 9, etc.
2, I am trying to use @constraint to link the project request major to student major. But I just do not really know the next. (set funding constant as well) Will you just give some tips for that? Like how to set the projects in different level order?
3, I have a problem with the array output. How can I plot the array as I see it in the workspace? Not confusing in the repl window.
4, will you please explain a little bit about dot and bin? I check the Julia doc but I do not really understand those.

clearconsole()

using DelimitedFiles,JuMP, GLPK, LinearAlgebra
# using DelimitedFiles to load, read & write result to csv files
m = Model(GLPK.Optimizer)

csvfilename = "E:/Drop/Dropbox/Project/student.csv"
#located the target data csv file in computer
csv1filename = "E:/Drop/Dropbox/Project/project.csv"
csvdata = readdlm(csvfilename,',', header=true)
csvdatap = readdlm(csv1filename,',', header=true)
# header = true is option
data = csvdata[1]
data2 = csvdatap[1]
#load all numbers for as a arry
header = csvdata[2]
header2 = csvdatap[2]
#load the heders to remaind what are those numbers
#may not use the headers untill load into csv files
@variable(m,x[1:137,1:34]>=0)
@variable(m,U[1:34]<=6)#j as project
@variable(m,L[1:34]>=3)#j as project
@variable(m,s[])
#@objective(m,Max,)
#this is the Obj function I used. I was trying to maxmize the final score
#over all projects
@constraint(m,stp[i in 1:137,j in 1:34],x[i,j] <=U[i:j])
@constraint(m,stp[i in 1:137,j in 1:34],x[i,j] >=L[i:j])
@constraint(m,stp[j in 1:34],sum(x[i,j] for i in 1:137)<=1)
#stp means student to project
#first is limite 1 project has less than 6 student
#second is limite 1 project has more than 3 student
#third is limite only open 1 project for one student

optimize!(m)
println("SEED project student Informations :")
println("ME-1,EE-2,BIOM-3,EMGT-4")
#println(value.())
println(x)

#resultfile = open("result.csv", "w")
#println(resultfile, "node, first value, second value")
#for i in 1:length(value1)
#println(resultfile, "$i, $(value1[i]), $(value2[i])")
#end
#close(resultfile)

seba754 · December 2, 2020, 8:56am

Hey Sui,
Let’s go in order then:

I don’t understand very much what you want. Say you have a list of preferences for student A → [ 3, 4, 13, 2]. You want to assign scores to each value such as [10, 9, 8, 7]? I don’t understand why you want to load everything into matrix, as the structure you mention is a 137x34 matrix, where each element is a list of…preferences?
I have seen your code, but as I told you, you’re going to have to write the linear program you’re trying to implement for me to help you any further, as I literally won’t know until then what are you trying to implement (i.e I can’t tell just by your code why you’re using four sets of variables, or why are you bounding x_ij by U_ij (This will throw an error because you’re evaluating a value against a vector.
If you want to plot the results, I recommend making histograms. Like, how many students got their first, second, etc. priority. You can look into Gadfly (Home · Gadfly.jl) if you are familiar with grammar of graphics (ggplot), or using DataFrames (Introduction · DataFrames.jl), plus Plots (Home · Plots). If you are worried about where to see the output, if you are using the Juno IDE, a window will pop up for you, and its my editor of choice for Julia
For Bin, it’s a specification for the variable, so it can only take 0-1 values (https://jump.dev/JuMP.jl/stable/variables/#Binary-(ZeroOne)-constraints-1)
For dot, it’s an operator that will apply a function or operation, that works on a single element, to every element of an array, as per Mathematical Operations and Elementary Functions · The Julia Language

Bottom line, write down the LP, otherwise you won’t be sure about what you’re doing.
S.