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

image.png

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
User Time Group Var
0 A 0 0 v0001
1 A 0 1 v0002
2 A 0 2 v0003

Formulation

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

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

Recommended Posts

Grouping games with combinatorial optimization
Grouping by combinatorial optimization
Combinatorial optimization with quantum annealing
Solving 4-color problems with combinatorial optimization
Maximize restaurant sales with combinatorial optimization
Go see whales with combinatorial optimization
Pave the road with combinatorial optimization
Solving game theory with combinatorial optimization
Let's stack books flat with combinatorial optimization
Solving nurse scheduling problems with combinatorial optimization
Use combinatorial optimization
Create an academic society program with combinatorial optimization
Solving school district organization problems with combinatorial optimization
Solving the N Queen problem with combinatorial optimization
Solving the N Queens problem with combinatorial optimization
Road installation with optimization
Getting Started with Optimization
Create games with Pygame
Try function optimization with Optuna
Combinatorial optimization to investigate stars
Games using IMU with SenseHat
Restore disjointed photos with optimization!
General-purpose global optimization with Z3
Adjust hyperparameters with Bayesian optimization
Solving Knapsack Problems with Google's OR-Tools-Practicing the Basics of Combinatorial Optimization Problems
Solving "cubes in cubes" by combinatorial optimization
Determine recorded programs by combinatorial optimization
The power of combinatorial optimization solvers
Bayesian optimization very easy with Python
Design of experiments and combinatorial optimization
Optimization learned with OR-Tools Part0 [Introduction]
Combinatorial optimization techniques seen in puzzles
Divide into teams by combinatorial optimization
Think about menus by combinatorial optimization
Solve combinatorial optimization problems with Google's OR-Tools (5) Decide on a date course