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

Recommended Posts

Grouping by combinatorial optimization
Grouping games with combinatorial optimization
Solving "cubes in cubes" by combinatorial optimization
Determine recorded programs by combinatorial optimization
Divide into teams by combinatorial optimization
Think about menus by combinatorial optimization
Use combinatorial optimization
Horse racing winning method by combinatorial optimization
Let's decide the date course by combinatorial optimization
Minimize the number of polishings by combinatorial optimization
Judging the finish of mahjong by combinatorial optimization
Divide into teams by combinatorial optimization (minimize average deviation)
Divide into teams by combinatorial optimization (simulated annealing method)
Combinatorial optimization to investigate stars
Combinatorial optimization with quantum annealing
Let's decide the lecture of PyCon JP 2016 by combinatorial optimization
Let's decide the position of the fire station by combinatorial optimization
Solving 4-color problems with combinatorial optimization
Go see whales with combinatorial optimization
Pave the road with combinatorial optimization
The power of combinatorial optimization solvers
Think about transformation rock-paper-scissors by optimization
Design of experiments and combinatorial optimization
SVM optimization by active set method
Solving game theory with combinatorial optimization
Combinatorial optimization techniques seen in puzzles
Explanation of production optimization model by Python
Solving nurse scheduling problems with combinatorial optimization
Finding the patrol boat route by optimization