[PYTHON] Jeux de regroupement avec optimisation des combinaisons

Qu'est-ce que c'est

Vous êtes le secrétaire de la noce. Neuf participants joueront le jeu en trois groupes de trois chacun. Ce jeu sera joué 4 fois. Pensez à regrouper ** deux personnes ** afin qu'elles ne puissent être dans le même groupe qu'une seule fois **.

• Golfeur social de Collection d'exemples LocalSolver Est-ce un indice.

Formulation et Python

Résolvons-le en utilisant Optimisation de combinaison. Comme d'habitude, [en utilisant PuLP et 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). La variable ** 0-1 Var ** indique qui, quand et quel groupe détient.

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] #Afficher les 3 premières lignes

Formulation

python3

m = LpProblem() #Modèle mathématique
for _,v in a.groupby(['User','Time']):
    m += lpSum(v.Var) == 1 #Chaque personne appartient à un groupe à chaque fois
for _,v in a.groupby(['Time','Group']):
    m += lpSum(v.Var) == 3 #3 personnes dans 1 groupe
for uu in permutations(uss,2):
    y = addvars(4*3) #Variables qui deviennent 1 dans le même groupe
    m += lpSum(y) <= 1 #Les deux personnes ne peuvent être dans le même groupe qu'une seule fois
    for w,(_,v) in zip(y, a[a.User.isin(uu)].groupby(['Time','Group'])):
        m += lpSum(v.Var) <= 1+w #Relation entre y et Var
m.solve()
a['Val'] = a.Var.apply(value)
a[a.Val>0].groupby(['Time','Group']).User.sum() #Affichage des résultats

résultat

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

Supplément - Partie 1

Lorsqu'elle est formulée simplement, la fonction objectif est une optimisation non linéaire quadratique. En l'état, il ne peut pas être résolu par le solveur MIP, donc l'ajout d'une nouvelle variable (y) pour chaque paire se traduira par une optimisation linéaire (bien qu'il y ait plus de variables). Cependant, à grande échelle, une solution approximative telle qu'une méthode de recherche locale peut être plus efficace.

Supplément - Partie 2

--LpProblem de PuLP n'est pas un problème, c'est un ** modèle **! --Problème: ce que vous voulez résoudre --Modèle: exprimé de manière à pouvoir être manipulé par un ordinateur

――Lors de l'examen des résultats, c'est le modèle, pas le problème, qui change!

c'est tout