You are the secretary of the wedding party. Nine participants will play the game in three groups of three each. This game is played 4 times. Consider grouping ** any two people ** so that they can only be in the same group once **.
Let's solve it using Combinatorial optimization. As usual, [using PuLP and pandas](http://qiita.com/SaitoTsutomu/items/070ca9cb37c6b2b492f0#pulp%E3%81%A8pandas%E3%81%AE%E7%B5%84%E5%90%88 % E3% 81% 9B% E3% 81% AB% E3% 81% A4% E3% 81% 84% E3% 81% A6). The ** 0-1 variable Var ** indicates who, when, and which group holds.
python3
import pandas as pd
from pulp import *
from ortoolpy import addvars, addbinvars
from itertools import permutations
uss = [chr(65+i) for i in range(9)] # Users
a = pd.DataFrame([(us,wk,gr) for us in uss for wk in range(4)
for gr in range(3)], columns=['User','Time','Group'])
a['Var'] = addbinvars(len(a)) #variable
a[:3] #Display the first 3 lines
User | Time | Group | Var | |
---|---|---|---|---|
0 | A | 0 | 0 | v0001 |
1 | A | 0 | 1 | v0002 |
2 | A | 0 | 2 | v0003 |
Objective function | None |
---|---|
Constraints | Each person belongs to one group each time |
1 group is 3 people | |
Any two people can be in the same group only once (use a variable that becomes 1 in the same group) |
python3
m = LpProblem() #Mathematical model
for _,v in a.groupby(['User','Time']):
m += lpSum(v.Var) == 1 #Each person belongs to one group each time
for _,v in a.groupby(['Time','Group']):
m += lpSum(v.Var) == 3 #3 people in 1 group
for uu in permutations(uss,2):
y = addvars(4*3) #Variable that becomes 1 in the same group
m += lpSum(y) <= 1 #All two people can be in the same group only once
for w,(_,v) in zip(y, a[a.User.isin(uu)].groupby(['Time','Group'])):
m += lpSum(v.Var) <= 1+w #Relationship between y and Var
m.solve()
a['Val'] = a.Var.apply(value)
a[a.Val>0].groupby(['Time','Group']).User.sum() #Result display
Time Group 0 0 AFI 1 EGH 2 BCD 1 0 ABH 1 CEF 2 DGI 2 0 ACG 1 BEI 2 DFH 3 0 BFG 1 ADE 2 CHI
When formulated straightforwardly, the objective function is a quadratic nonlinear optimization. As it is, it cannot be solved by the MIP solver, so adding a new variable (y) for each pair will result in linear optimization (although there will be more variables). However, for large scale, an approximate solution such as local search may be more effective.
--PuLP's LpProblem is not a problem, it's a ** model **! --Problem: What you want to solve --Model: Expressed so that it can be handled by a computer
――When reviewing the results, it is the model, not the problem, that changes!
that's all
Recommended Posts