[PYTHON] Can you solve sports scheduling?

Sports scheduling problem

Nice to meet you, everyone! I will write the article from today. Immediately, this time I would like to write about the sports scheduling problem. Let's take soccer as an example, but how do you decide on a soccer schedule? Looking at the j1 league, 18 teams have a good balance between home and away! Creating such a schedule is actually the same as the optimization problem! This time, let's solve this scheduling problem using Python's pulp!

Problem setting

Schedule a league of 6 teams and 10 matches. As a condition, home and away are not allowed three times in a row. Home is 5 times for each team! !! If the opening season is home, the closing season is away! !! And vice versa! !! We will organize this schedule to minimize the distance traveled by the team.

First of all, preparation

python

from pulp import *
import numpy as np
#Team gathering
team = ["A", "Y", "T","K","O","H"]
print("Team set I= {:}".format(team))

#Set of clauses
setu = ["1", "2", "3", "4", "5","6","7","8","9","10"]

print("Set of clauses setu= {:}".format(setu))



#distance
cc = [
      [ "H","T","O","Y","K","H","T","O","Y","K"],
      [ "O","H","K","A","T","O","H","K","A","T"],
      [ "K","A","H","O","Y","K","A","H","O","Y"],
      [ "T","O","Y","H","A","T","O","Y","H","A"],
      [ "Y","K","A","T","H","Y","K","A","T","H"],
      [ "A","Y","T","K","O","A","Y","T","K","O"],
     ]

c2 = [
      [ 912,100,528,130,116,912,100,528,130,116],
      [ 488,792,16,130,35,488,792,16,130,35],
      [ 20,100,810,506,35,20,100,810,506,35],
      [ 20,500,16,804,116,20,500,16,804,116],
      [ 488,500,528,506,330,488,500,528,506,330],
      [ 912,792,810,804,330,912,792,810,804,330],
     ]

c={}
for t in team:
    for s in setu:
        c[t,s]=c2[team.index(t)][setu.index(s)]
        
co={}
for t in team:
    for s in setu:
        co[t,s]=cc[team.index(t)][setu.index(s)]
        
print("Match c[t,s]: ")
for t in team:
    for s in setu:
        print("c[{:},{:}] = {:}, ".format(t, s, c[t,s]), end = "")

    print("")
print("")

The team brought in my favorite J1 league team! cc is a procession of competing teams, starting from the top row, in the order of A, Y, T, K, O, H teams. I guess there are 10 columns in some sections. Put the distances in an array of c. In co, put the battle team.

Main subject

python

#Declaration of problem
SportsScheduling = pulp.LpProblem("SportsScheduling", pulp.LpMinimize) #Defined as the smallest problem

#Variable declaration
x = {}
for t in team:
    for s in setu:
        x[t, s] = pulp.LpVariable("x({:},{:})".format(t,s), 0, 1, pulp.LpInteger )

#Objective function
SportsScheduling += pulp.lpSum( c[t,s]*x[t,s]  for t in team for s in setu), "TotalCost"




#Constraints
for t in team:
    SportsScheduling += x[t,"1"]+x[t,"2"]+x[t,"3"]  >= 1 
    SportsScheduling += x[t,"2"]+x[t,"3"]+x[t,"4"]  >= 1 
    SportsScheduling += x[t,"3"]+x[t,"4"]+x[t,"5"]  >= 1 
    SportsScheduling += x[t,"4"]+x[t,"5"]+x[t,"6"]  >= 1 
    SportsScheduling += x[t,"5"]+x[t,"6"]+x[t,"7"]  >= 1 
    SportsScheduling += x[t,"6"]+x[t,"7"]+x[t,"8"]  >= 1 
    SportsScheduling += x[t,"7"]+x[t,"8"]+x[t,"9"]  >= 1 
    SportsScheduling += x[t,"8"]+x[t,"9"]+x[t,"10"]  >= 1 
    
    SportsScheduling += x[t,"1"]+x[t,"2"]+x[t,"3"]  <= 2 
    SportsScheduling += x[t,"2"]+x[t,"3"]+x[t,"4"]  <= 2 
    SportsScheduling += x[t,"3"]+x[t,"4"]+x[t,"5"]  <= 2 
    SportsScheduling += x[t,"4"]+x[t,"5"]+x[t,"6"]  <= 2
    SportsScheduling += x[t,"5"]+x[t,"6"]+x[t,"7"]  <= 2 
    SportsScheduling += x[t,"6"]+x[t,"7"]+x[t,"8"]  <= 2 
    SportsScheduling += x[t,"7"]+x[t,"8"]+x[t,"9"]  <= 2 
    SportsScheduling += x[t,"8"]+x[t,"9"]+x[t,"10"]  <= 2 
    
#Alignment with opponents
for t in team:
    for s in setu:
        SportsScheduling += x[co[t,s],s]+x[t,s]  == 1 

for t in team:
    SportsScheduling += sum(x[t,s] for s in setu) <= 5
    
for t in team:
     SportsScheduling += x[t,"1"]+x[t,"10"] == 1   
    
SportsScheduling.solve()

I feel that this is the most important. It makes me sleepy. .. .. .. Define the variable. 0 for home and 1 for away. You can get the distance by multiplying the previous distance by this variable. Home doesn't move, so 0. Multiply by 1 for moving away.

As a constraint, if three consecutive games are 1 or more and 2 or less, the home away will not be three times in a row. Also, for example, X will play against Y. In that case either one must be 1 and either one must be 0. for that reason. We also put that constraint in order to make that match.

5 out of 10 games are home, so 5 or less is required. Add 1 to the opening and closing clauses.

The conditions are now complete! !! !! !! !!

Let's see the result!

for t in team:
    for s in setu:
        print("x[{:},{:}] = {:} ".format(t, s, x[t,s]), end = "")
    print("")
print("")

print("Problem formula")
print("--------")
print(SportsScheduling)
print("--------")
print("")




print("Calculation result")
print("")

print("Solution x[i,j]: ")
for t in team:
    for s in setu:
        print("{:},  "
              .format( x[t,s].value()), end="")
    print("")
print("")

Solution x[i,j]: 
0.0,  0.0,  1.0,  1.0,  0.0,  1.0,  1.0,  0.0,  0.0,  1.0,  
1.0,  1.0,  0.0,  0.0,  1.0,  1.0,  0.0,  0.0,  1.0,  0.0,  
0.0,  1.0,  0.0,  1.0,  0.0,  1.0,  0.0,  0.0,  1.0,  1.0,  
1.0,  0.0,  1.0,  0.0,  1.0,  0.0,  0.0,  1.0,  1.0,  0.0,  
0.0,  1.0,  0.0,  0.0,  1.0,  0.0,  1.0,  1.0,  0.0,  1.0,  
1.0,  0.0,  1.0,  1.0,  0.0,  0.0,  1.0,  1.0,  0.0,  0.0,  

............ I was able to do it for the time being w

I think I can build it better. It seems to be interesting because it seems that it can also be a problem of break minimization!

I would like to tackle this problem deeply in the future!

Thank you for watching.

We will continue to grow in the future! Then!