[PYTHON] Grouping games with combinatorial optimization

what is this

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 **.

• Social golfer of LocalSolver Example Collection Is a hint.

Formulation & Python

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

Formulation

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

result

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

Supplement --Part 1

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.

Supplement-Part 2

--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