[PYTHON] Find the dates for a jarring tournament

Introduction

--A sporting tournament will be held in ** 8 countries **. Suppose you play 4 games for 7 days. ――It is assumed that you know the popularity ranking of the previous reputation. ――As much as possible, try to make the match of the popular pair in the second half, and create a schedule that will make you feel uncomfortable until the end.

Let's solve this problem with Combinatorial Optimization.

Formulation

Let the variables be 0-1 variables that represent "choose and choose" the combination for country 1, country 2, and day.

Also, the "weight of the match on a day (k) with two countries (i, j)" corresponding to the variable is as follows. By maximizing the sum of these weights, "matches between countries with lower rankings" will be prioritized. $ Weight = \ frac {2 ^ k} {i rank \ times j rank} $

Maximize $ \ sum_i {weight _i x_i} $ sum of weights
Variables $ x_i \ in \ {0, 1 \} ~ ~ \ forall i \ in Candidate $ Whether to select that candidate td>
Constraints $ \ sum_ {i \ in j, k pairs ~~~~~} {x_i} = 1 ~ ~ \ forall j, k \ in \ mbox {country} $ One same pair
$ \ sum_ {i \ in day k including country j ~~~~~~~~~~~~~} {x_i} = 1 ~ ~ \ forall j \ in \ mbox {country }, \ forall k \ in \ mbox {day} $ Same day, one
This problem is a type of scheduling problem.

Try it with Python

First, create a table of combinations.

python3


import pandas as pd
from itertools import combinations, product
from pulp import *
ss = 'Italy Netherlands Japan South Korea Thailand Dominican Republic Peru Kazakhstan'.split()
rnk = {s:(i+1) for i, s in enumerate(ss)} #Country name → ranking
a = pd.DataFrame([(i, j, k, 2**k/rnk[i]/rnk[j]) for i, j in combinations(ss, 2)
                  for k in range(7)], columns='Country 1 Country 2 days Weight'.split())
a[:3]
>>>
Country 1 Country 2 days Weight
0 Italy Netherlands 0 0.5
1 Italy Netherlands 1 1.0
2 Italy Netherlands 2 2.0

Let's formulate and solve it.

python3


m = LpProblem(sense=LpMaximize) #Mathematical model
a['Var'] = [LpVariable('v%d'%i, cat=LpBinary) for i in a.index] #variable
m += lpDot(a.weight, a.Var) #Objective function
for _, b in a.groupby(['Country 1', 'Country 2']):
    m += lpSum(b.Var) == 1 #One in the same group
for s, i in product(ss, range(7)):
    #The same country, one on the same day
    m += lpSum(a.query('(Country 1=="{0}" |Country 2=="{0}") &Day=={1}'.format(s, i)).Var) == 1
m.solve() #Solution
a['Val'] = a.Var.apply(value) #result
#display
for i, b in a.groupby('Day'):
    print(i+1, 'Day')
    for _, r in b[b.Val > 0].iterrows():
        print(' %*s - %s'%(8-len(r.Country 1), r.Country 1, r.Country 2))
>>>
First day
Italy-Kazakhstan
Netherlands-Peru
Japan-Dominican Republic
Korea-Thailand
the 2nd day
Italy-Peru
Netherlands-Kazakhstan
Japan-Thailand
Korea-Dominican Republic
Third day
Italy-Dominican Republic
Netherlands-Thailand
Japan-Kazakhstan
Korea-Peru
Day 4
Italy-Thailand
Netherlands-Dominican Republic
Japan-Peru
Korea-Kazakhstan
Day 5
Italy-Korea
Netherlands-Japan
Thailand-Kazakhstan
Dominican Republic-Peru
Day 6
Italy-Japan
Netherlands-Korea
Thailand-Peru
Dominican Republic-Kazakhstan
Day 7
Italy-Netherlands
Japan-Korea
Thailand-Dominican Republic
Peru-Kazakhstan

The schedule for each day was output.

As another method, there may be a combination with a difference in strength in the first half and a combination with a difference in strength in the second half.

Bonus

Temporarily, I'm making my most recent Python-related post run on Arukas.

  • https://qiita-jupyter.arukascloud.io/ --After opening each article, select a cell, then hold down the Shift key and press the Enter key to execute. --This is the original image above.
    • https://hub.docker.com/r/tsutomu7/qiita-jupyter/

that's all

Recommended Posts