# Mixed Integer programming - Problem modelling coincidence restriction in scheduling match problem

I am trying to model and solve a problem for maximize audience of matches that must be scheduled in different slots (I am using python PulP library). Below I explain the problem and the model process I followed:

• Maximize audience of 20 teams in 10 slots. Those teams belongs to 3 different categories. Matrix is given for the audience where rows and columns are the categories and contains the audience value. My model is based on binary decision variable as follows:
match_slot = [(team1, team2, slot) for team1 in range(20) for team2 in range(20) for slot in range(10)]

var_match_slot = pulp.LpVariable.dicts("var_partido_horario", match_slot, 0, 1, cat=pulp.LpBinary)


• Each slot has a reduction of audience given by:
penalty_slot = [0.4,0.55,0.7,0.8,1,0.45,0.75,0.85,1,0.4]

• Restrictions were added for :Teams only play once, they cannot play against themselves and they have to play in first and last slot minimum one match
for team in range(20):

model += pulp.lpSum([var_match_slot[team,team2,slot] + var_match_slot[team2,team,slot] for team2 in range(20) for slot in range(10)]) == 1

for team in range(20):

model += pulp.lpSum([var_match_slot[team,team,slot]  for slot in range(10)]) == 0

model += pulp.lpSum([var_match_slot[team1, team2, 0] for team1 in range (20) for team2 in range (20)]) >=1
model += pulp.lpSum([var_match_slot[team1, team2, 9] for team1 in range (20) for team2 in range (20)]) >=1


After my objective function to maximize audience looks like this:

model += pulp.lpSum([var_match_slot[(team1, team2, slot)] *audience[category[team1]][category[team2]]*penalty_slot[slot] for team1 in range(20) for team2 in range(20) for slot in range(10)])



This implementation works but I need to add a reduction of audience due to how many games are scheduled in same slot following the dictionary:

penalty_coincidence = {0:1, 1:1, 2:0.75,3:0.55,4:0.4,5:0.30,6:0.25,7:0.23,8:0.02,9:0.02}


I tried to add a new integer decision variable to count number of matches and then use the value to index this dictionary which will be added as factor in objective function. That does not work or I have a problem in my implementation.

• How does this differ from your previous question (or.stackexchange.com/questions/9958/…)?
– prubin
Feb 19 at 19:42
• Hello, I was trying to ask a more precise question and showing how the model was built. The link was added in the comment of previous one. I do not know what is the usual way of working. Feb 20 at 13:42
• For future reference, it is better to edit the original question, in particular so that any responses to the earlier version are visible to anyone responding to the newer version. If the follow up question is substantially different, then making it a new question is fine.
– prubin
Feb 20 at 15:49

Try this: (I don't know PuLP very well). I am assuming you have already built possible combinations like (team_1,Team_2, 0), (team_1,team_3,0),(team_1,team_3,1)... This is generally useful so that you can eliminate creating redundant variables like (Team1, Team1,0)

slot =[*range(10)]
idx = [*range(10)] #Assuming max 9 games can be scheduled in one slot
z = pulp.LpVariable.dicts("z", idx,slot, 0, 1, cat=pulp.LpBinary)
for s in slot:
model += pulp.lpsum(k*z[k,s] for k in idx) = lpsum(var_match_slot[(team, team, s)] for team in teams) # $$\sum_k kz_{k,s} = \sum_{(t1,t2)\in teams}x_{t1,t2,s}$$
model += pulp.lpsum(z[k,s] for k in idx) = 1# $$\sum_k z_{k,s} = 1$$

# Objective #$$\sum_k z_{k,s}penalty_slot[k]$$
model += pulp.lpSum(z[k,s]*penalty_slot[k] for k in penalty_slot for slot in range(10)])
# or
model += pulp.lpSum(z[k,s]*penalty_slot[k] for k in idx for slot in range(10)])

• You mean to add this to my already objective function? with penalty_slot you mean penalty_coincidence? What is the purpose of this model += pulp.lpsum(z[k,s] for k in idx) = 1 ? thanks Feb 19 at 19:07
• Your objective is to minimize penalty, right. Then I think it should be the objective. This constraint ensures for every slot only one $z$ is selected out of $z_{k,s}$ in the first constraint. Feb 19 at 19:17
• No, my objective is to maximize audience which is given by the type of matches and reduced by a factor of matches in same slot Feb 19 at 19:19
• Suppose solver decides number of games in 2nd slot is 4. Then solver needs to see the penalty for scheduling 4 games in a slot. How will it get? By those 2 constraints. First one say sum(1z,2z,3z,..10z)=4. Since z is binary it can select 1+3, so z1 & z3=1. But next constraint says pick up just one of the z. So it is forced to pick up z4=1. Then in the objective sum(z1p1,z2p2,z3p3,..) for slot 2. But since only z4=1, rest are 0 so only z4p4 for slot 2. Since Feb 19 at 19:26
• Basically my suggested constraints help you to pick up right penalty for number of games scheduled. Since you can't use decision var like x as an coincidence or index for penalty list so z helps to get that Feb 19 at 19:32