Algorithm to determine best combination of keeping students together in their camp rooms

Question

I have a problem I'd like to solve and am not sure whether there is a known algorithm or how the best way to approach it would be.

Say for example there is a class of 30 students who are going on a school camp. They will each share a room with other students. Each student can provide a list of 3 friends that they ideally want to share a room with.

I'd like to know if there is a programmatic way to determine the best outcome for keeping students together with who they requested to go with?

There is also another complication here, being that there are x amount of rooms, each room allowing a varying amount of students per room (up to 7).

Answer 1

This solution isn't very fast and I am not sure that it will always finds the best solution, but I think it should be a viable strategy to find a good enough solution.

What you need first is a function to calculate the score of a room. The score is simply the sum of the number of fulfilled wishes of all its current inhabitants.

First distribute all students randomly on all beds in the camp (beds can be empty). Then look for beds in two different rooms where swapping the occupants (or moving the one occupant when one bed is empty) would improve the sum of the scores of both rooms:

for each bed as bed1
    for each bed as bed2 which comes after bed1
        if swapping the occupants of bed1 and bed2 improves the total score
           swap occupants of bed1 and bed2

Repeat this until no swaps are found.

Possible flaw: This method will not find an improvement which requires to move more than two people to reach a positive change in score. I am not sure if such situations are possible, though.

Answer 2

As far as I can tell this problem is a special case of the quadratic assignment problem (QAP)

If the size of the problem is reasonable I would probably try modelling it as an integer problem and solve it with a MIP solver (see GLPK or CBC for open source solvers).

The mathematical problem would probably look something like that (assuming that all room have the same capacity, if you want to model heterogeneous rooms, the model would be a bit different):

Let us assume that Q is the capacity of the room. Let S be the set of students. Let $x_{i,j}$ be a binary variable saying that student i is in the same room as student j. Let $a_{i,j}$ be 1 if i wants to be with j and 0 otherwise.

We try to maximise $\sum_{i \in S, j \in S} x_{i,j}a_{i,j}$

Subject to:

$\sum_{j \in S} x_{i,j} = Q, \forall i \in S$ $x_{i,j} = x_{j,i}, \forall i \in S, j \in S$ $x_{i,k} \geq x_{i,j} + x_{j,k} - 1, \forall i \in S, j \in S, k \in S$

Answer 3

Wow, not easy task, since basically the number of possible results grows with the formula

Total = M! / (n! * (M - n)!) (Combination without repetition)

For 6 kids in two rooms of three, is already 120 possibilities. Just do the math for your numbers and you will clearly see you need another approach.

This type of problem is what is call an NP-Hard. If you find a solution, you will never be sure that is the best till you try all the possibilities.

You can read a bit about genetic algorithms, that basically what it does is randomize the selection using ideas similar to the, yep!, genetics.

You will also need a goodness function, to understand when one solution is better than other.

Another approach is to analyze your population and find if you can find rules to distribute them. E.g Males vs females, with this you already divide your problem in half.

Different courses, ages, likeness, etc...

Im trying to make an algorithm, if I found an acceptable solution, I will let you know!