[PYTHON] 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)

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