4

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).

  • I wrote a blog post about a similar problem some times ago orandtricks.wordpress.com/2013/09/19/… The problem I was analysing was about assigning guests to table for a wedding but it is quite similar I think. I'll try to add a proper answer later – Renaud M. Oct 7 '15 at 12:49
  • 1
    That's a really interesting problem. One approach would be to first detect cliques and then treat it as the knapsack problem. Another could be to first distribute them randomly and then look for swaps which improve the overall rating. Finding a guaranteed ideal solution smells quite NP-complete to me. – Philipp Oct 7 '15 at 13:00
  • 1
    @Philipp its a variation on the stable marriage problem. This particular one being closer to the stable roommates problem (though again, with variations). – user40980 Oct 7 '15 at 13:49
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.

  • 1
    How do you know this has found the global maximum rather than a local maximum score? – user40980 Oct 7 '15 at 13:27
  • @MichaelT I don't. That's why I said I am not sure it will always find the best solution. – Philipp Oct 7 '15 at 13:48
  • For reference, this approach is a simplified version of simulated annealing. To improve the chance of finding the global maximum you should have a chance of making a swap even if it decreases the overall score, and that chance should decrease to zero over time. – Jules Oct 30 '15 at 18:51
  • It may also be better to select bed1 and bed2 randomly at each iteration. – Jules Oct 30 '15 at 18:54
0

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$

  • Apparently there is no Mathjax support on programmers.SE so the above math model does not display correctly. Sorry about that – Renaud M. Oct 7 '15 at 20:14
0

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!

  • You won't have to look at all of the combinations in that formula if you use process of elimination to disqualify rooms in a "fast fail" fashion. Even at a million permutations (or even 10 million), the solution should be readily computable. – Robert Harvey Oct 30 '15 at 19:28
  • 6 kids in 2 rooms of 3 is not 120. It is 20. – Bent Mar 1 '16 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.