--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.
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.
| 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 |
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.
Temporarily, I'm making my most recent Python-related post run on Arukas.
that's all