I have an assignment problem with the following aims:
- there are
nstudents, each of whom belongs to one of several different graduate programs. Each program has multiple students in it. (For a sense of scale, in our casenstudents = 120.) - there are
nweeksof collaborative group-work; in each week there are several different groups - in each week, a student gets assigned to a single group (in our case, there are 2 or 3 weeks and 15-20 groups per week)
- students assign a preference score to each group in each week
- (same program penalty) we want to penalize (but not block entirely) cases where two students from the same program end up in the same group
- (repeated pairing penalty) we want to penalize (but not block entirely) cases where two students are paired in a group for more than one week
I’ve thought about setting up the problem as follows: let A[i, j] ∈ (0, 1) indicate whether student i got assigned to group j (j being an index that wraps both weeks and group numbers into a single index). Then define the student-student correlation C = A*A', and let S[i1, i2] ∈ (0, 1) be 1 in cases where students i1 and i2 are in the same program. Then if ⊙ means the Frobenius inner product, the objective might be written
P⊙A + αS⊙C + βC⊙C
where P is the preference matrix and α and β are scalar coefficients that express the magnitude of the same-program and repeated-pairing penalties, respectively. The reasoning behind the C⊙C term is that it’s small when the correlation is 0 or 1, and grows rapidly for correlations of 2 or more. In code, this can be expressed as
@NLobjective(model, Min, sum(A[i, j] * P[i, j] for i = 1:nstudents, j = 1:totaloptions) +
penalty_sameprogram * sum(A[i1, j] * A[i2, j] * S[i1, i2] for i1 = 1:nstudents, i2 = i1+1:nstudents, j = 1:totaloptions) +
penalty_samepartner * sum(A[i1, j] * A[i2, j] for i1 = 1:nstudents, i2 = i1+1:nstudents, j = 1:totaloptions)^2)
where smaller P is better (we use 1=most-preferred, 4 = least-preferred) and both penalty coefficients are nonnegative.
I’m looking for general guidance about how to tackle this. I’ve been trying Juniper + Ipopt, but I’ve been dismayed by the performance. Even on a simple test case like this:
julia> students
6-element Vector{Student}:
StudentA Last (Program1)
StudentB Last (Program2)
StudentC Last (Program3)
StudentD Last (Program1)
StudentE Last (Program2)
StudentF Last (Program3)
preferences = (
[1 4;
1 4;
1 4;
4 1;
4 1;
4 1],
[1 3 4;
1 2 4;
1 4 3;
1 3 4;
1 2 4;
1 4 3],
)
I get
julia> @time assign!(students, preferences; penalty_sameprogram=5, penalty_samepartner=0.5)
0.957838 seconds (1.00 M allocations: 116.754 MiB, 4.65% gc time)
6-element Vector{Student}:
StudentA Last (Program1): [1, 1]
StudentB Last (Program2): [1, 3]
StudentC Last (Program3): [1, 1]
StudentD Last (Program1): [2, 3]
StudentE Last (Program2): [2, 2]
StudentF Last (Program3): [2, 2]
That’s livable, but obviously it’s a toy problem. With 120 students and ~40 groups, there’s about a 1min pause before the first round of Ipopt optimization; hitting Ctrl-C reveals it’s inside acyclic_coloring. And this seems to repeat each time Juniper calls Ipopt for a new solution. It’s only when I drop down to about 30 students that the gap between successive Ipopt runs is on the scale of 1s, but because I’ve not yet waited for it to finish I’m unsure how many such runs there will be.
Any suggestions for tackling this?