How do you find the best student assignment in the classroom?

Question

23 students of level A, 24 from level B and 30 from level C should be assigned to three classes. Classes should be almost exactly the same size. Different levels can be mixed into one class, but it is better to avoid it. In any case, there must be either 0 students from one level in the class, or more than 6.

Can you help me solve this combinatorial optimization problem? The following is an example of input and output. Bonus points if you can show me how to solve a common problem!

Input:

pupils = { "A" : 23, "B" : 24, "C": 30 } 

Output example (not very good!)

 Class #1 : {'A': 9, 'B': 6, 'C': 10}, Class #2 : {'A': 10, 'B': 9, 'C': 7}, Class #3 : {'A': 11, 'B': 9, 'C': 6} 

Edit : Here is my very hacky, completely undocumented, semi-rough code. This is ugly, but it works! I would like to know how I can write a more elegant solution.

Answer 1

The main difficulty here is that you have a problem with multi-criteria optimization. You have three things that I think you are interested in, that you can either consider goals or “soft constraints”:

• Getting similar class sizes
• Minimizing class levels
• Having a sufficient number of students from a level in the class if there are students in the class.

Note that I wrote an optimization model for AMPL. Since you use Python, there are similar optimization modeling languages ​​for python, such as PuLP and pyomo, which you can use. The model should not be too complicated to translate.

Here is an integer programming model and a data file that emphasizes an objective number of 1 while keeping the problem (integer) linear. To this end, the optimization problem finds the same solution that you gave in your example. I hope you can use this and add other restrictions and / or objective conditions and get more effective solutions.

The goal is to minimize the largest class size. The variable of interest is y [i, j]. y [i, j] for i in LEVEL, j in the class CLASS - the number of students from level i assigned to class j. It is assumed that you have an entry for the minimum number of students from each level in each class, if they are assigned to this level.

The object function may not be what you want, but it is a way to try to even out the linear sizes of the classes. I also do not promise that this is the most effective way to solve the problem. Maybe the best custom algorithm for the problem, but all I had to do was express the limitations and purpose, and not write the algorithm. This is probably good enough for your use.

Using the Gurobi solver on neos-server.org (you can use lpsolve or another open source optimization solver), I got a solution

 y := 1 1 14 1 2 9 1 3 0 2 1 6 2 2 0 2 3 18 3 1 6 3 2 16 3 3 8 ; 

Model:

 set LEVEL ordered; set CLASS; param maxClassSize {CLASS}; param minLevelNumberInClass {LEVEL, CLASS}; param numInLevel {LEVEL}; var z >= 0; var y{LEVEL, CLASS} integer, >= 0; var x{LEVEL, CLASS} binary; #minimize maximum class size minimize obj: z; subject to allStudentsAssigned {i in LEVEL}: sum {j in CLASS} y[i,j] = numInLevel[i]; #z is the largest of all classes sizes subject to minMaxZ {j in CLASS}: z >= sum {i in LEVEL} y[i,j]; subject to maxClassSizeCon {j in CLASS}: sum {i in LEVEL} y[i,j] <= maxClassSize[j]; #xij = 1 if any students from level i are in class j subject to defineX {i in LEVEL, j in CLASS}: y[i,j] <= min(numInLevel[i], maxClassSize[j]) * x[i,j]; #if any students from level i are assigned to class j, then there is a minimum #if x[i,j] = 1, y[i,j] >= minLevelNumberInClass[i,j] subject to minLevel {i in LEVEL, j in CLASS}: minLevelNumberInClass[i,j] * x[i,j] <= y[i,j]; 

Data file for your example:

 set LEVEL := 1 2 3; set CLASS := 1 2 3; param minLevelNumberInClass: 1 2 3 := 1 6 6 6 2 6 6 6 3 6 6 6 ; param maxClassSize := 1 77 2 77 3 77 ; param numInLevel := 1 23 2 24 3 30 ;