Optimisation problem (assigning group members) solvable with VBA, Solver?

[Schwibach]

Hello, 

I have a rather interesting problem, I think.

I have 25 different groups and about 400 people who I need to assign to the groups.

Every person has individual preferences that will lead to a utility value for a place in a group.
The goal is to maximize the sum of the individual utilities i.e. make everybody as happy as possible.

There is a restriction that not more than 20 people can be assigned to any group.

I have set up a table with random values with 5 groups and 10 students for testing purposes.

The table gives all the individual utilities for each group assignment and I have one column with the selected group and then one column with the individual values for the selected group and the sum of the utilities.

My thought is that I could have VBA 
1. copy the selected groups copy and the resulting values in a new column
2. check if any of the restrictions (more than 20 people in one group) are violated

3. if no restrictions are violated and the sum of the utilities is greater than the one currently in the copied column, write the new (better) solution over the previous one

4. loop through all the possible choices for person 1
    then go to the next possible choice for person 2
    loop through all the possible choices for person 1
    repeat this for all the choices for person 2 
    and then for person 3 and so on.

I'm not very proficient in VBA, I can record and make some basic changes to macros, but I don't have a proper handle on this yet.

I'd appreciate any help you could give! 

[#2]

@Schwibach 

You wrote:

I have set up a table with random values with 5 groups and 10 students for testing purposes.

The table gives all the individual utilities for each group assignment and I have one column with the selected group and then one column with the individual values for the selected group and the sum of the utilities.

Were you intending to attach a copy of that spreadsheet? It would make it far more likely that someone would help if your test workbook were available to, you know, test possible solutions.

[#3]

@mathetes 

Thank you for your reply and the advice.

I attached my spreadsheet.

In columns M and N I have the an outline of what I would like to get as a result.

Is there maybe a way to create all possible variations, cycle through them and write over columns M and N in case the current variation produces a higher sum value and does not violate any restrictions?

[#4]

@Schwibach 

I have had a quick stab at the problem using Solver

[#5]

@Peter Bartholomew 

First of all, thanks for taking the time.

May I ask what you put into Solver?

Am I correct in assuming that you added Column I with the choice?

The result from there is not optimal. Student 1 would have a higher utility if he was in group 5 or E (which is empty)

[#6]

I tried using Solver. But it didn't do anything for me.

I data I changed the data validity of the cells where the variables are to whole numbers from 1-5.

But Solver only tells me it found a solution. The values however are just the ones that were in there to begin with.

[#7]

@Schwibach 

The gradient methods do seem to get stuck.  Evolutionary take a long time and I am not sure how well the problem will scale (you may finish by requiring a paid version of the Solver add-in).  I have applied constraints to values as part of named ranges 'choice' and 'groupSize' though the latter do not appear to be active (so every student appears to get their first choice).

[#8]

@Peter Bartholomew 

Thank you so much!

I tried to expand on your solution and changed the tables a bit, created some more groups and 130 dummy students. Also, there are now 140 total spots in all the different classes and I made individual restrictions for each group (They will differ depending on the class type and whether there is one or two identical groups. 

Now, it doesn't give me a solution. It says the restrictions cannot be met.

[#9]

@Schwibach 

Like you, I had problems with obtaining a feasible starting point; yet it is so easy to achieve manually!

Having moved students from the oversubscribed groups to group 6, I re-ran the optimisation.  This did give some improvement to the utility figure but there is no assurance of optimality.

[#10]

@Schwibach 

I have run the same Excel 365 workbook from a different starting point and obtained a different, but slightly inferior, solution.  Where students have moved groups from one solution to the next, I have compared their preferences before and after.  The starting point was to distribute the students uniformly using a repeating sequence of groups {6,1,2,3,4,5,6,6,1,2,3,...}