Recently I have this problem at work that I've been looking and reading some solutions for. I would like to get some others ideas and thoughts on this to have them going through my mind to hopefully come up with a good solution that could be implemented into the system.

The Problem:

We have X amount of people that need to be put into Y amount of rooms. Each room can hold a certain amount of people, and can be different per room. I need to automatically assign these people to rooms.

General Rules:

• Certain groups of people can only room with their group.
• There can not be more than a ± 2 year age difference in room mates.
• You can only room with the people of the same gender.
• People can request a roommate (can assume this room mate already fits the rules as above), system should attempt to fulfill roommate requests, but it doesn't have too if can't.

So far I currently have a prototype solution working though I feel it does not really come up with an optimal solution, as I am getting a lot of rooms that only get one person rooming in them.

Currently I am just dividing everyone that can be roomed with each other into groups. Then for each person inside of each group I just assign them the next available room. This just feels too "greedy" I guess and I don't think I can rely on this to come up with an optimal solution (not in terms of time complexity, but in terms of a not having a lot of people rooming with each other).

So I was wondering what are some ideas others may have had. I am looking for some ideas to talk it out really. I am not looking for code solutions. Small pseudo code solutions at the most.

Thanks for any ideas anyone may have.

Simulated annealing is an easy way to find approximate solutions:

• Define a function that takes an assignment of people to rooms and returns a real number that indicates how unhappy we are with the assignment. This is probably just a weighted sum of penalties. We'll call this function "energy", following some analogy with Physics that I don't quite understand.
• Start with any assignment (everyone in the same room would do; or everyone unassigned, if you have a way to represent that).
• Set a temperature parameter T to some high initial value.
• Try a random perturbation (for instance, move one person to another room, or swap two people). If the energy goes down, accept it. If the energy goes up, accept it with probability exp((E_new - E_old) / T).
• Keep trying random perturbations and slowly decreasing the temperature parameter T.

If you decrease the temperature slowly enough, this will find a low-energy solution. It's surprising how well that simple algorithm works for many discrete optimization problems.

Sometimes you can easily compute the effect of a change on the energy, without computing it from scratch. Perhaps you have penalties per room and penalties per person, and you only need to reevaluate the room and people involved in the change. That can make the algorithm much faster.

21 hours ago, swiftcoder said:

Sounds like you are looking for constraint optimisation.

Looks like a great thing to look at. Will definitely read up on it. Thanks!

15 hours ago, alvaro said:

Simulated annealing is an easy way to find approximate solutions:

• Define a function that takes an assignment of people to rooms and returns a real number that indicates how unhappy we are with the assignment. This is probably just a weighted sum of penalties. We'll call this function "energy", following some analogy with Physics that I don't quite understand.
• Start with any assignment (everyone in the same room would do; or everyone unassigned, if you have a way to represent that).
• Set a temperature parameter T to some high initial value.
• Try a random perturbation (for instance, move one person to another room, or swap two people). If the energy goes down, accept it. If the energy goes up, accept it with probability exp((E_new - E_old) / T).
• Keep trying random perturbations and slowly decreasing the temperature parameter T.

If you decrease the temperature slowly enough, this will find a low-energy solution. It's surprising how well that simple algorithm works for many discrete optimization problems.

Sometimes you can easily compute the effect of a change on the energy, without computing it from scratch. Perhaps you have penalties per room and penalties per person, and you only need to reevaluate the room and people involved in the change. That can make the algorithm much faster.

Interesting approach. I like it. Going to use a white board to work through some things on it. Interesting. 

Quick Question:
Do you have any suggestions on the penalties? I assume these are like the constraints? Would that assumption be correct?

Thanks for the couple ideas though. Gives me a few ideas to look at.