Represent grouping as a Graph Partition Problem and implement a Kernighan-Lin heuristic

[aubreypc]

Background Info

In the graph partition problem, we must partition the vertex set V of a graph into k subsets such that that the edge-cut (total weight of all edges which go between different subsets) is minimized. In our case, each vertex in the graph would represent a particular student, and for any two vertices u and v we create an edge e between them if and only if those two students are allowed to be in the same group. Then we assign a weight to e representing the compatibility of the two students. With this setup, the edge-cut represents the total "unused compatibility" of the grouping, i.e. the sum of all compatibility scores for students who aren't in the same group -- we want to minimize this.

While graph partitioning is NP-hard, it has some fairly fast heuristics. Kernighan-Lin is one such option which applies in the case of bisecting the graph into 2 groups (k = 2). By recursively applying Kernighan-Lin, we can partition into k = 2^n groups for any n >= 1 in roughly O(log2(k) * |V|^2) time. However, other heuristics are available which are similar to Kernighan-Lin while generalizing to a k-way partition rather than a bisection, and perhaps without the logarithmic increase in complexity.

• Brief videos explaining graph partition problem and Kernighan-Lin: 1, 2
• Documentation for the Kernighan-Lin implementation in the NetworkX library
• A paper describing how to optimize for arbitrarily many objectives at once -- this will help us assign edge weights

Prototype implementation

We should begin by getting recursive K-L on one objective working before moving on to multi-objective optimization. This will involve:

• Computing compatibility between students
• Constructing a graph representing student conflicts (student pair conflict => no edge between vertex pair) and assigning compatibility scores as edge weights
• Running K-L recursively to partition students into 2^n groups

[Alex-Yarkosky]

It should be kept in mind that if non-negotiable conflicts are included by having situations where there are not edges between two individuals, it should first be checked that groups can be made to the user's specifications before any algorithm is utilized. If they cannot be made, the user should be asked to remove some or at least one of theses conflicts and could instead assign a low compatability score to the individuals. This would allow for the user to always get groups that fit the specifications they gave to our tool.

[Michionlion]

Additionally, there is the problem of calculating these compatibility scores -- if they are given by the user, the user must do a difficult calculation, and it is nearly impossible to get a compatibility score from some given characteristics of skill, since the compatibility score is dependent on the entire group, not just two students. I think this approach may be fundamentally limited by these problems.

[aubreypc]

@Alex-Yarkosky Good point! To ensure a grouping exists, I think it should suffice to check if each vertex u in the graph has degree(u) >= k, where k is the number of students per group, but I'm not certain about this -- would need to prove / find a proof.

@Michionlion Even if the compatibility scores are local to each pair of students, Kernighan-Lin should still result in a grouping which is reasonably good globally since it minimizes the number of highly compatible pairs of people which are not grouped together.

[Michionlion]

@aubreypc the problem is actually generating those compatibility scores, however. It's very difficult to imagine how a professor might choose them, and they are not really possible to calculate from other information easily. I may not have your insight, however.

[Alex-Yarkosky]

@Michionlion @aubreypc I think the best way to think about compatibility scores, assuming higher is better, is that everyone starts off at 5, assuming a 1 to 5 scale, meaning that the professor would have no reason to believe those individuals would have any problem working together. If the professor had any reason to believe students would have a problem or difficulty working together, then they could change to any other number on the scale. It may also be better to think of the compatability score in terms of conflict resolution or in other words, 5 means the students have no conflict and 1 could mean the students have conflicts but can work together with the rest in between being other various degrees of problematics between the two individuals. Hope this helps when thinking about the compatability scores!

[aubreypc]

@Michionlion Yeah, it's definitely hard to find good measures of compatibility. A couple ideas:

• I like @Alex-Yarkosky's suggestion. We could also give students a way to optionally self-report their perceived compatibility with other students on that same scale, since many professors may not be opinionated about the weights associated with particular pairs. In any case, this is a good intuitive way to think about the edge weights.
• Assign an integer weight to each vertex, and let the edge weight be the sum of the weights of its incident vertices -- the weight represents some measure of skill at a task, let's say as a scalar 0 <= x <= 1. After thinking about this for a second, my guess is that K-L would end up grouping all the highest weighted vertices together, in which case this metric would perhaps not be ideal for our use case -- would be interesting to see what K-L does. Eventually we could have a tuple of different weights so that multiple scores can be optimized for at once (see article linked in OP) with different scalars for the importance of each metric which might help.
• I don't know much about statistics, but maybe there'd be a good way to assign high compatibility to students at "opposite" ends of the score distribution so that they balance each other out?

@gkapfham Do you have any suggestions for how compatibility between pairs of students could be measured?

[aubreypc]

Before #229 can be merged, it needs test cases -- @finneyj2 has offered to work on these.