[PYTHON] Gruppieren von Spielen mit Kombinationsoptimierung

Was ist das

Sie sind die Sekretärin der Hochzeitsfeier. Neun Teilnehmer spielen das Spiel in drei Dreiergruppen. Dieses Spiel wird 4 mal gespielt. Gruppieren Sie ** zwei beliebige Personen ** so, dass sie nur einmal in derselben Gruppe sein können **.

• Social Golfer von LocalSolver Example Collection Ist ein Hinweis.

Formulierung & Python

Lösen wir es mit Kombinationsoptimierung. Wie üblich [mit PuLP und 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) Die Variable ** 0-1 Var ** gibt an, wer, wann und welche Gruppe enthält.

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] #Zeigen Sie die ersten 3 Zeilen an

Formulierung

python3

m = LpProblem() #Mathematisches Modell
for _,v in a.groupby(['User','Time']):
    m += lpSum(v.Var) == 1 #Jede Person gehört jedes Mal zu einer Gruppe
for _,v in a.groupby(['Time','Group']):
    m += lpSum(v.Var) == 3 #3 Personen in 1 Gruppe
for uu in permutations(uss,2):
    y = addvars(4*3) #Variablen, die in derselben Gruppe zu 1 werden
    m += lpSum(y) <= 1 #Alle zwei Personen können nur einmal in derselben Gruppe sein
    for w,(_,v) in zip(y, a[a.User.isin(uu)].groupby(['Time','Group'])):
        m += lpSum(v.Var) <= 1+w #Beziehung zwischen y und Var
m.solve()
a['Val'] = a.Var.apply(value)
a[a.Val>0].groupby(['Time','Group']).User.sum() #Ergebnisanzeige

Ergebnis

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

Ergänzung - Teil 1

Bei einfacher Formulierung ist die Zielfunktion eine quadratische nichtlineare Optimierung. Da dies nicht der Fall ist, kann es vom MIP-Solver nicht gelöst werden. Das Hinzufügen einer neuen Variablen (y) für jedes Paar führt zu einer linearen Optimierung (obwohl es mehr Variablen gibt). Im großen Maßstab kann jedoch eine ungefähre Lösung wie eine lokale Suchmethode effektiver sein.

Ergänzung - Teil 2

--PuLPs LpProblem ist kein Problem, es ist ein ** Modell **! --Problem: Was Sie lösen wollen --Modell: Wird so ausgedrückt, dass es von einem Computer verarbeitet werden kann

――Bei der Überprüfung der Ergebnisse ändert sich das Modell, nicht das Problem!

das ist alles