Divide into teams by combinatorial optimization

what is this

In the article of Master's Apprentices, "Solve workshop teaming as a combinatorial optimization problem blog-post.html) ”was formulated and solved.

problem

I want to divide ** 6 people ** (P, Q, R, S, T, U) into ** 3 teams ** (A, B, C). I want to make the four communication skills and their total ** even ** as much as possible. See the original article for details.

Communication ability score table

The communication skills of the six people are scored as follows for each controller, promoter, supporter, and analyzer. For example, Mr. P's controller ability is 6 points.

python


import numpy as np, pandas as pd
from pulp import *
from ortoolpy import addvars, addbinvars
score= pd.DataFrame([[6,0,1,3],[2,-1,3,5],[2,4,0,0],[3,4,5,0],[0,2,1,4],[2,3,-1,1]],
    columns='Controller Promoter Supporter Analyzer'.split(),index=list('PQRSTU'))
Number of teams,Number of members= 3,score.shape[0]
print(score)
controller Promoter Supporter Analyzer
P 6 0 1 3
Q 2 -1 3 5
R 2 4 0 0
S 3 4 5 0
T 0 2 1 4
U 2 3 -1 1

Formulate and solve in Python

In order to make it as uniform as possible, it is good if the variation can be minimized, but if it is formulated obediently, it becomes non-linear (quadratic) and difficult to solve. We have a small number of teams this time, so let's minimize the difference between the maximum and the minimum. Empirically, if the number of groups is small, the effect is similar to the minimum variance. Here, the weight of variation within teams is 1, and the weight of variation between teams is 1.5.

python


m = LpProblem() #Mathematical model
x = np.array(addbinvars(Number of members,Number of teams)) #allocation
y = np.array(addvars(Number of teams,2)) #Minimum and maximum in the team
z = addvars(2) #Minimum and maximum between teams
m += lpSum(y[:,1]-y[:,0]) + 1.5*(z[1]-z[0]) #Objective function
for i in range(Number of members):
    m += lpSum(x[i]) == 1 #Belong to some team
for j in range(Number of teams):
    m += lpDot(score.sum(1),x[:,j]) >= z[0]
    m += lpDot(score.sum(1),x[:,j]) <= z[1]
    for k in range(score.shape[1]):
        m += lpDot(score.iloc[:,k],x[:,j]) >= y[j,0]
        m += lpDot(score.iloc[:,k],x[:,j]) <= y[j,1]
m.solve() #Solution
Result x= np.vectorize(value)(x)
print(['ABC'[i] for i in (Result x@range(Number of teams)).astype(int)])
>>>
['C', 'A', 'A', 'B', 'C', 'B']

I got the same division as the original article. (In the original article, it was an approximate solution, but this is a strict solution)

Please note that the method of minimizing the difference between the maximum and the minimum is an approach that is not good for the general-purpose solver used this time, so the calculation time increases sharply at a large scale. In that case, it will be easier to solve if you change it so that there is a penalty if it goes out of a certain range.

reference -Grouping by combinatorial optimization -Combinatorial optimization, grouping games

that's all

Recommended Posts

Divide into teams by combinatorial optimization
Divide into teams by combinatorial optimization (minimize average deviation)
Divide into teams by combinatorial optimization (simulated annealing method)
Grouping by combinatorial optimization
Solving "cubes in cubes" by combinatorial optimization
Determine recorded programs by combinatorial optimization
Think about menus by combinatorial optimization
Horse racing winning method by combinatorial optimization
Use combinatorial optimization
Let's decide the date course by combinatorial optimization
Judging the finish of mahjong by combinatorial optimization
[Python] Divide Switch albums into folders by game
Let's decide the position of the fire station by combinatorial optimization
Combinatorial optimization to investigate stars
Grouping games with combinatorial optimization