[Solved] Planning school trip, need students assigned rooms

[wingrider78]

Hello,

I have a very difficult task ahead of me. I need to sort 300 students into hotel rooms for a school trip. Each student is being asked to give a list of 5 other students they would like to share their room with. We are hoping to be able to sort them out so they can have at least of of their chosen 5 in their hotel room that is holding 4 students.

I have created a small sample data set with 9 students, their 5 choices, going into 3 rooms of 3 students (just to test things out, I figured that if this idea can actually work, scaling up shouldn't be an issue)

I have attached the sample spreadsheet.

Students are in B1:J1
Their 5 choices are in B2:J6

They need to be put into rooms in cells B9:D11

If a student is already put in a room, they need to be removed from the available data set so they don't get put in a second room.
If possible, each student will be placed with at least one of their chosen friends.

I don't know if this is possible in calc, or if it needs to be done in a database...I'm stumped.

Thanks in advance!

[Villeroy]

If you do this on a spreadsheet then it should be a big one made of paper rather than arithmentic CALCulation software. Of course, you could earn some merits with the development of a school trip database (design once for hundreds of trips) but that would take some investment of development time (days rather than hours).

[John_Ha]

Google for a solution - someone has done this before so why reinvent the wheel?

Search with allocation preferences and similar terms to find things like Preference Group Allocation at https://www.statsdirect.com/help/Defaul ... _group.htm.

If doing it manually I would try to simplify it. About the only suggestion I can think of is to split them into 10 sets of 30 and allocate the 30s. This is because 10 x 30^2 is 10x smaller than 300^2 (I know it isn't a square relation - it's probably worse - but you should get the idea). Then look at the sets and allocate the ones you couldn't allocate with others in the other sets.

I keep thinking of a 30 x 30 grid with names across the top and down the side, with crosses showing which student prefers another. I also wonder if you get a broad band down the diagonal? I think you need always to enter the preferences the students down the side. Don't mix top and sides. This will probably end up with a triangular matrix rather than a square one - the other triangle will be empty and can be ignored. Possibly re-arrange the rows to try to get all the x in a bunch and then manually allocate.

I cannot think of an easy way to portray a three dimensional 28 x 28 x 7 array (28 student x 28 student x 7 rooms) in Calc.

I would consider getting 90% with friends to be a good result. I think this is a computationally intense problem a little like the travelling salesman problem.

[MrProgrammer]

Hi, and welcome to the forum. Thank you for your attachment.

I need to sort 300 students into hotel rooms for a school trip. Each student is being asked to give a list of 5 other students they would like to share their room with. We are hoping to be able to sort them out so they can have at least of of their chosen 5 in their hotel room that is holding 4 students.

You have a problem in Linear Programming. Yours is an "Integer Programming" problem, an especially difficult case. A spreadsheet is not a good tool for solving this. This type of problem is hard, so unless its size is small enough that one can check every possible configuration, the best one can hope for is to find a fairly good approximation even if it is not optimal. For 300 students and 75 rooms there are 10⁵¹¹ ways to arrange the students, so it is not possible to check all the configurations.

Section 13 (Solvers and scripting (programming) languages) lists some of the tools which have been created for Linear Programming problems.

I have created a small sample data set with 9 students, their 5 choices, going into 3 rooms of 3 students (just to test things out,

A spreadsheet can try to find a good selection by generating many random ones and looking for the maximum preference matches in them. This attachment generates and checks 250 random selections for your "small sample data set". It is likely to find one with many preference matches because there are only 1680 ways to assign 9 students to three rooms. But this simple approach will be less successful with your real problem since 10⁵¹¹ possibilities is far from what any computer can check. That's why the tools in section 13 were developed.

202110201127.ods

(84.75 KiB) Downloaded 138 times

If this solved your problem please go to your first post use the Edit button and add [Solved] to the start of the subject field. Select the green checkmark icon at the same time.

[Tutorial] Ten concepts that every Calc user should know

[John_Ha]

Google for a solution - someone has done this before so why reinvent the wheel?
Search with allocation preferences and similar terms ...

A search with group allocation preferences quickly found https://clevergroups.com/ which does exactly what you want and appears to be free.

Clever Groups

Clever Groups is a preference-based group generator. This means that each student in a class can submit a list of preferences of who they want to be in a group with, from most to least. The teacher can then generate groups by selecting the max size of the groups or the total number of groups.

[Villeroy]

Personal preferences are not random. At least one could identify groups of people who prefer each other mutually.

[gpgrego]

I agree with MrProgrammer, He wrote: "You have a problem of Linear Programming".
In OpenOffice, LibreOffice or Excel for these problem can be used "Solver" too.

You can get a little help from your math teacher.

Unfortunately in OpenOffice and LibreOffice the Solver settings are not saved when
you close the file, so you need to rewrite them every time you reopen.

[wingrider78]

Thank you everyone for your thoughts and ideas. It looks like I have a few things to look into, thank you for the suggestions. I'm sorry I haven't responded sooner, I didn't realize the notification email went into my spam folder.

Once I go over everything, I will mark the thread as solved.

[wingrider78]

Hi, and welcome to the forum. Thank you for your attachment.

I need to sort 300 students into hotel rooms for a school trip. Each student is being asked to give a list of 5 other students they would like to share their room with. We are hoping to be able to sort them out so they can have at least of of their chosen 5 in their hotel room that is holding 4 students.

You have a problem in Linear Programming. A spreadsheet is not a good tool for solving this. This type of problem is hard, so unless its size is small enough that one can check every possible configuration, the best one can hope for is to find a fairly good approximation even if it is not optimal. For 300 students and 75 rooms there are 10⁵¹¹ ways to arrange the students, so it is not possible to check all the configurations.

Section 13 (Solvers and scripting (programming) languages) lists some of the tools which have been created for Linear Programming problems.

I have created a small sample data set with 9 students, their 5 choices, going into 3 rooms of 3 students (just to test things out,

A spreadsheet can try to find a good selection by generating many random ones and looking for the maximum preference matches in them. This attachment generates and checks 250 random selections for your "small sample data set". It is likely to find one with many preference matches because there are only 1680 ways to assign 9 students to three rooms. But this simple approach will be less successful with your real problem since 10⁵¹¹ possibilities is far from what any computer can check. That's why the tools in section 13 were developed.

202110201127.ods

If this solved your problem please go to your first post use the Edit button and add [Solved] to the start of the subject field. Select the green checkmark icon at the same time.

[Tutorial] Ten concepts that every Calc user should know

I had fun going through your file. I tried scaling up to 100 students into 25 rooms. While I enjoyed playing in the file, it just wasn't feasible to use this for even 100 students. Even taking the number of random selections up to 45000, I still wasn't able to more than around 25 students who were matched with someone they wanted.

[wingrider78]

I agree with MrProgrammer, He wrote: "You have a problem of Linear Programming".
In OpenOffice, LibreOffice or Excel for these problem can be used "Solver" too.

You can get a little help from your math teacher.

Unfortunately in OpenOffice and LibreOffice the Solver settings are not saved when
you close the file, so you need to rewrite them every time you reopen.

Playing with "solver" I wasn't able to get very good results. I used the screenshot images you had for the options. Once I hit solve, I wasn't able to get many students matched with the ones that were in their selections. Maybe I wasn't doing something right. Thank you for your time and input.

[wingrider78]

Google for a solution - someone has done this before so why reinvent the wheel?
Search with allocation preferences and similar terms ...

A search with group allocation preferences quickly found https://clevergroups.com/ which does exactly what you want and appears to be free.

Clever Groups

Clever Groups is a preference-based group generator. This means that each student in a class can submit a list of preferences of who they want to be in a group with, from most to least. The teacher can then generate groups by selecting the max size of the groups or the total number of groups.

Thank you for finding this website. I never knew the proper terms to search when doing my initial web searches. This will work perfectly based on my 9 student tests that have done. This is what I will use once we have all the data from the kids.

[John_Ha]

I never knew the proper terms to search when doing my initial web searches.

The ability to create a good search argument is now an essential life skill.

I find it is an iterative process as even a poor starting argument will usually find something which then allows you to refine the argument until eventually you home in precisely on what you want. Notice how my first argument was allocation preferences and the search results suggested refining it to group allocation preferences which gave exactly what was needed.