[PYTHON] Grouping by combinatorial optimization

problem

There are 26 groups, each consisting of the following people.

python3

import numpy as np
n = 26 #Number of groups
np.random.seed(11)
a = np.random.randint(10, 20, n) #Number of people per group
for i in range(n):
    print('group%2d %d people'%(i, a[i]))
>>>
Group 0 19 people
Group 1 10 people
Group 2 11 people
Group 3 17 people
Group 4 11 people
Group 5 17 people
Group 6 12 people
Group 7 18 people
Group 8 10 people
Group 9 10 people
Group 10 14 people
Group 11 12 people
Group 12 11 people
Group 13 15 people
Group 14 15 people
Group 15 17 people
Group 16 14 people
Group 17 11 people
Group 18 18 people
Group 19 18 people
Group 20 11 people
Group 21 13 people
Group 22 16 people
Group 23 12 people
Group 24 12 people
Group 25 10 people

――26 Divide the group into 6 rooms (0, 1, 2, 3, 4, 5). (Multiple groups in one room) --The same group will be in the same room. --Assign from the youngest group number to the youngest room number. --If you want to put groups a and b (a <b) in room numbers c and d, respectively, you must have c <= d. ――One room can accommodate up to 63 people.

Where should I divide the group?

Try to solve with Python

Formulate and solve a combinatorial optimization problem.

python3

from pulp import *
limit = 63 #Room capacity
m = LpProblem() #Mathematical model
#Number of rooms up to that group
x = [LpVariable('x%d'%i, lowBound=a[i], upBound=limit) for i in range(n)]
#Whether to divide the room into front and back groups
y = [LpVariable('y%d'%i, cat=LpBinary) for i in range(n-1)]
m += lpSum(x) #Objective function
m += lpSum(y) <= 6-1 #number of rooms=6 or less(The break is 6-1)
for i in range(n-1):
    m += x[i+1] >= x[i] + a[i+1] - limit * y[i] #Add the number of people in the same room
m.solve() #Solution
print(LpStatus[m.status])
print([int(value(x[i])) for i in range(n) if i==n-1 or value(y[i])])
>>>
Optimal
[57, 58, 57, 61, 58, 63]

--If the variance is the minimum, it becomes non-linear and difficult to solve. --Since the solver is difficult to solve when the maximum value is minimized, it is a constraint.

I referred to CodeIQ. [Optimization problems hidden in daily life] Algorithm that allocates examinees to the examination venue as evenly as possible

that's all