Students will be assigned to several laboratories in class. I would like to find an assignment method with as few complaints as possible by a systematic method. Therefore, we will use integer programming.
I thought it would be easy to use the solver of Excel addin, but when I executed it, I got a message saying "There are too many variable cells." It seems that the number of variables is up to 200, so it cannot be used for this problem (100 students, 10 laboratories).
I thought about using CPLEX or an independent solver, but since the input file must be created automatically by the program anyway, this time I will move the solver from within the Python program.
Specifically, use the PuLP package.
Students have answered the desired order of each laboratory (1 is the highest).
import pulp
data = (
("name", "Yuino Lab", "Ari Nestgawa Lab", "Shishi Seiken"),
("Rei Ichido", 1, 2, 3),
("Go cold", 1, 2, 3),
("Kiyoshi Dese", 1, 3, 2),
("Hitoshi Oma", 3, 1, 2),
("Star size", 3, 1, 2)
)
Assignment is decided in two stages as follows.
Consider the student with the lowest rank among the students in terms of the order of preference of the laboratory to which they are assigned. For the sake of fairness, the highest priority is given to the order of preference for the laboratory to which such a worst student is assigned.
Therefore, even if 99 out of 100 students become the 1st laboratory in the desired order, if the remaining one becomes the 10th laboratory, all 100 students will be assigned to the 9th laboratory. Priority is given to those who are.
I want to keep the best and worst rankings that I found in the first stage, and make sure that everyone is as high as possible in the desired laboratory. However, it is better for students A and B to be assigned to the 2nd and 3rd laboratories than to be assigned to the 1st and 4th laboratories in the order of preference. In other words, improving the lower ranking is prioritized over improving the upper ranking.
constant $ m $: Number of students, $ n $: Number of laboratories, $ a_ {i, j} $: Students $ i (0 \ leq i \ leq m-1) $ laboratories $ j (0 \ leq j \ leq n-1) Desired order for $ ($ 1 \ leq a_ {i, j} \ leq n $), $ size_ {min} $: Lower limit of the number of people assigned to the laboratory, $ size_ {max} $: Laboratory Maximum number of people assigned to
variable 0-1 Variable $ x_ {i, j} $$ (1 \ leq i \ leq m, 1 \ leq j \ leq n) $ indicates that student $ i $ has been assigned to laboratory $ j $ .. If it is 1, assign it. The variable $ worst $$ (1 \ leq j \ leq n) $ represents the desired order of the assigned laboratory in the worst case.
Objective function: $ worst $ → minimize Constraint $ x_ {i, 1} + x_ {i, 2} + ... + x_ {i, n} = 1 $ Student $ i $ will always be assigned somewhere $ x_ {1, j} + x_ {2, j} + ... + x_ {m, j} \ geq size_ {min} $, $ x_ {1, j} + x_ {2, j} + .. . + x_ {m, j} \ leq size_ {max} $ The number of people assigned to the laboratory $ j $ is $ size_ {min} $ or more, $ size_ {max} $ or less $ a_ {i, 1} x_ {i, 1} + a_ {i, 2} x_ {i, 2} + ... + a_ {i, n} x_ {i, n} \ leq worst $ Student $ i The desired order of $ assigned laboratory is $ worst $ or higher
Let $ bound $ be the desired order of the worst case obtained by solving problem 1, that is, the value of $ worst $ in the optimal solution.
Objective function: $ \ sum_i a_ {i, 1} ^ \ alpha x_ {i, 1} + a_ {i, 2} ^ \ alpha x_ {i, 2} + ... + a_ {i, n} ^ \ alpha x_ {i, n} $ → minimize
$ \ Alpha $ is a real number greater than or equal to 1. If $ \ alpha = 1 $, the improvement from 2nd place to 1st place and the improvement from 3rd place to 2nd place are regarded as the same importance. If $ \ alpha> 1 $, priority is given to lower improvement. For example, if $ \ alpha = 2 $, the improvement from the 2nd place to the 1st place lowers the value of the objective function by $ 2 ^ 2 --1 ^ 2 = 3 $, but the improvement from the 3rd place to the 2nd place is $ 3 ^ 2- 2 ^ 2 = 5 $ lower.
Constraint $ x_ {i, 1} + x_ {i, 2} + ... + x_ {i, n} = 1 $ Student $ i $ will always be assigned somewhere $ x_ {1, j} + x_ {2, j} + ... + x_ {m, j} \ geq size_ {min} $, $ x_ {1, j} + x_ {2, j} + .. . + x_ {m, j} \ leq size_ {max} $ The number of people assigned to the laboratory $ j $ is $ size_ {min} $ or more, $ size_ {max} $ or less $ a_ {i, 1} x_ {i, 1} + a_ {i, 2} x_ {i, 2} + ... + a_ {i, n} x_ {i, n} \ leq bound $ Student $ i The desired order of the laboratory to which $ is assigned is $ bound $ or higher.
The same number of people will be assigned to the laboratory. If there is a remainder, reduce the difference in the number of people assigned to 1 or less. The following is a continuation of the above.
NUM_MEMBERS = len(data)-1 #Number of students
NUM_GROUPS = len(data[0])-1 #Number of groups
MIN_GROUP_SIZE = NUM_MEMBERS//NUM_GROUPS #Minimum number of people in a group
#Maximum number of people in a group(Maximum value-minimum value<= 1)
if NUM_MEMBERS % NUM_GROUPS == 0:
MAX_GROUP_SIZE = MIN_GROUP_SIZE
else:
MAX_GROUP_SIZE = MIN_GROUP_SIZE + 1
#Question 1
problem1 = pulp.LpProblem('FindWorstCase', pulp.LpMinimize)
# 0-1 variable x[i,j]Declare i:student, j:group
x = {}
for i in range(0, NUM_MEMBERS):
for j in range(0, NUM_GROUPS):
x[i, j] = pulp.LpVariable("x({:},{:})".format(i, j), 0, 1, 'Binary')
#Declare the integer variable worst. The value is 1 or more and the number of groups or less.
worst = pulp.LpVariable('worst', 1, NUM_GROUPS, 'Integer')
#Constraint A:Each student is assigned to exactly one group
for i in range(0, NUM_MEMBERS):
problem1 += sum(x[i, j] for j in range(0, NUM_GROUPS)) == 1
#Constraint B:The number of people in each group is above the minimum and below the maximum
for j in range(0, NUM_GROUPS):
problem1 += sum(x[i, j] for i in range(0, NUM_MEMBERS)) >= MIN_GROUP_SIZE
problem1 += sum(x[i, j] for i in range(0, NUM_MEMBERS)) <= MAX_GROUP_SIZE
#Constraint C:The laboratories to which each student is assigned are the same as or younger than worst in the order of preference.
for i in range(0, NUM_MEMBERS):
problem1 += sum(data[i+1][j+1] * x[i, j]
for j in range(0, NUM_GROUPS)) <= worst
#Objective function: worst, that is, the worst case in the desired order
problem1 += worst
#Solve the problem
problem1.solve()
print("Worst:", worst.value())
#Problem 2
bound = worst.value() #The worst case obtained is the bound in the desired order.
problem2 = pulp.LpProblem('AsssignAll', pulp.LpMinimize)
#Constraint A:Each student is assigned to exactly one group
for i in range(0, NUM_MEMBERS):
problem2 += sum(x[i, j] for j in range(0, NUM_GROUPS)) == 1
#Constraint B:The number of people in each group is above the minimum and below the maximum
for j in range(0, NUM_GROUPS):
problem2 += sum(x[i, j] for i in range(0, NUM_MEMBERS)) >= MIN_GROUP_SIZE
problem2 += sum(x[i, j] for i in range(0, NUM_MEMBERS)) <= MAX_GROUP_SIZE
#Constraints:The laboratories to which each student is assigned are the same as or higher than bound in the order of preference.
for i in range(0, NUM_MEMBERS):
problem2 += sum(data[i+1][j+1] * x[i, j]
for j in range(0, NUM_GROUPS)) <= bound
#Objective function
WEIGHT_EXPONENT = 1.2 #Α for weighting
problem2 += sum((data[i+1][j+1] ** WEIGHT_EXPONENT) * x[i, j]
for i in range(0, NUM_MEMBERS) for j in range(0, NUM_GROUPS))
#Solve the problem
problem2.solve()
print("name", "Laboratory", "Ranking")
for i in range(0, NUM_MEMBERS):
for j in range(0, NUM_GROUPS):
if x[i, j].value() > 0:
print(data[i+1][0], data[0][j+1], data[i+1][j+1])
Execution result
Worst: 2.0
Name laboratory ranking
Rei Ichido Yuino Lab 1
Go Yuino Lab. 1
Kiyoshi Dese Shishiseiken 2
Hitoshi Oma Ari Nestgawa Lab 1
Monoboshi Dai Ari Nestgawa Lab 1
Recommended Posts