Football match sequence - CP SAT

[Frédéric Girod]

Hi Laurent and community,

Here is a problem I'm stuck with : I have to create a sequence of football matches between 32 teams, played on 10 matchdays (or 10 weeks if you prefer), which makes 16 matches played every matchday (and so 160 total number of matches).

Among the traditional constraints that teams should play 10 different opponents, shouldn't play against itself, should alternate home/away matches .... , I'm stuck on 1 constraint, and I need your help from a CP-SAT constraints perspective:

- the 32 teams are comprised in 4 pots of 8 teams, and each team should play against for example 2 teams of pot 1, 3 teams of pot 2, 3 teams of pot 3 and 2 teams of pot 4, to guarantee a certain competitive balance or diversification ....

I know there is already some pieces of code out there dealing with sport schedule, but here, this is a bit different ...

How would you handle this constraint ?

Thanks.

Below my code:

from ortools.sat.python import cp_model

import pandas as pd

class SolutionPrinter(cp_model.CpSolverSolutionCallback):

  """Print intermediate solutions."""

  def __init__(self):

      cp_model.CpSolverSolutionCallback.__init__(self)

      self.__solution_count = 1

  def on_solution_callback(self):

      self.__solution_count += 1

  def solution_count(self):

      return self.__solution_count

# Creates the model.

model = cp_model.CpModel()

  

num_teams = 32

num_matches = 16

num_matchdays = 10

pot1 = list(range(1,8+1))

pot2 = list(range(9,16+1))

pot3 = list(range(17,24+1))

pot4 = list(range(25,32+1))

# Home main variable

int_home_x_match_md = {}

for match in range(1,num_matches//num_matchdays+1): # 16

    for md in range(1,num_matchdays+1):             # 10

        int_home_x_match_md[(match, md)] = model.NewIntVar(1, num_teams, 'home match %i matchday %i ' % (match, md))

# Away main variable

int_away_x_match_md = {}

for match in range(1,num_matches//num_matchdays+1): # 16

    for md in range(1,num_matchdays+1):             # 10

        int_away_x_match_md[(match, md)] = model.NewIntVar(1, num_teams, 'away match %i matchday %i ' % (match, md))

########### Create the constraints #############################################################################################

# Teams shouldn't play against itself

for match in range(1,num_matches//num_matchdays+1):

    for md in range(1,num_matchdays+1):

        model.Add(int_home_x_match_md[(match, md)] != int_away_x_match_md[(match, md)])

# Make sure the 32 teams are different for each matchday

# Aggregate home and away integer variables in a same vector (int_x_match_md) in order to eventually add an AllDifferent constraint

int_x_match_md = {}

for match in range(1,num_matches//num_matchdays+1):

    for md in range(1,num_matchdays+1):

        int_x_match_md[(match, md)] = model.NewIntVar(1, num_teams, 'match %i matchday %i ' % (match, md))

        int_x_match_md[(match+num_matches//num_matchdays, md)] = model.NewIntVar(1, num_teams, 'match %i matchday %i ' % (match, md))

        int_x_match_md[(match, md)] = int_home_x_match_md[(match, md)]

        int_x_match_md[(match+num_matches//num_matchdays, md)] = int_away_x_match_md[(match, md)]

for md in range(1,num_matchdays+1):

    model.AddAllDifferent([int_x_match_md[(match, md)] for match in range(1,num_matches//num_matchdays+num_matches//num_matchdays+1)])

# Make the matches (pairings) all different

int_z_match_md = {} # to create a pairing of the 2 integer variables int_home_x_match_md and int_away_x_match_md

for match in range(1,num_matches//num_matchdays+1): # 16

    for md in range(1,num_matchdays+1):             # 10

        int_z_match_md[(match, md)] = model.NewIntVar(1, num_teams*num_teams, 'z variable match %i matchday %i ' % (match, md))

        model.Add(int_z_match_md[(match, md)] == int_home_x_match_md[(match, md)] * num_teams + int_away_x_match_md[(match, md)])

model.AddAllDifferent([int_z_match_md[(match, md)] for md in range(1,num_matchdays+1) for match in range(1,num_matches//num_matchdays+1)])

# Add home/away alternation constraints for (matchday 1 - matchday 2) and (matchday 9 - matchday 10)

boo_constr = []

boo_home_team = {}

boo_away_team = {}

for md in range(1,num_matchdays+1):

    for t in range(1,num_teams+1):

        for match in range(1,num_matches//num_matchdays+1):

            boo_home_team[t,match,md] = model.NewBoolVar('home_team_'+str(t)+' is playing match '+str(match)+' on matchday '+str(md))

            model.Add(int_home_x_match_md[(match, md)] == t).OnlyEnforceIf(boo_home_team[t,match,md])

            boo_away_team[t,match,md] = model.NewBoolVar('away_team_'+str(t)+' is playing match '+str(match)+' on matchday '+str(md))

            model.Add(int_away_x_match_md[(match, md)] == t).OnlyEnforceIf(boo_away_team[t,match,md])

boo_home_away_alternation_md1_md2 = {}

boo_home_away_alternation_md9_md10 = {}

for t in range(1,num_teams+1):

    boo_home_away_alternation_md1_md2[t] = model.NewBoolVar('home_team_'+str(t)+' is alternating on matchdays 1-2')

    model.Add(sum(boo_home_team[t,match,1]+boo_home_team[t,match,2] for match in range(1,num_matches//num_matchdays+1)) <= 1)#.OnlyEnforceIf(boo_home_away_alternation_md1_md2[t])

for t in range(1,num_teams+1):    

    boo_home_away_alternation_md9_md10[t] = model.NewBoolVar('home_team_'+str(t)+' is alternating on matchdays 9-10')

    model.Add(sum(boo_home_team[t,match,9]+boo_home_team[t,match,10] for match in range(1,num_matches//num_matchdays+1)) <= 1)#.OnlyEnforceIf(boo_home_away_alternation_md9_md10[t])

solver = cp_model.CpSolver()

solver.parameters.max_time_in_seconds = 5

solution_printer = SolutionPrinter()

status = solver.Solve(model)

[Frédéric Girod]

The output looks like this, in term of format: cf file.

[blind.lin...@gmail.com]

Did you solve this?

I played around with it (I've decided to get up to speed on CP-SAT)
and the code you posted doesn't really work as is. I found some bugs
here and there, but maybe I'm just not understanding what you are doing?

I can post my code if you want, but since I changed things slightly,
I'm going to try first to make comments inline with your code, below:

Also, I don't yet see anything in your current code to show the "pots"
stuff.

...

Okay, I have an issue with this. Why are you doing

num_matches//num_matchdays in the following loops?

if num_matches is 16, num_matchdays is 10, then
num_matches//num_matchdays = 1

Don't you really want match in range(1,num_matches + 1) ??

> for match in range(1,num_matches//num_matchdays+1): # 16
> for md in range(1,num_matchdays+1): # 10
> int_home_x_match_md[(match, md)] = model.NewIntVar(1, num_teams,
> 'home match %i matchday %i ' % (match, md))
>
> # Away main variable
> int_away_x_match_md = {}

ditto

> for match in range(1,num_matches//num_matchdays+1): # 16
> for md in range(1,num_matchdays+1): # 10
> int_away_x_match_md[(match, md)] = model.NewIntVar(1, num_teams,
> 'away match %i matchday %i ' % (match, md))
>
>
> ########### Create the constraints
> #############################################################################################
>
> # Teams shouldn't play against itself

again, and every time, no idea why you are integer dividing

> for match in range(1,num_matches//num_matchdays+1):
> for md in range(1,num_matchdays+1):
> model.Add(int_home_x_match_md[(match, md)] !=
> int_away_x_match_md[(match, md)])
>
> # Make sure the 32 teams are different for each matchday
> # Aggregate home and away integer variables in a same vector
> (int_x_match_md) in order to eventually add an AllDifferent constraint
> int_x_match_md = {}
> for match in range(1,num_matches//num_matchdays+1):
> for md in range(1,num_matchdays+1):
> int_x_match_md[(match, md)] = model.NewIntVar(1, num_teams, 'match
> %i matchday %i ' % (match, md))
> int_x_match_md[(match+num_matches//num_matchdays, md)] =
> model.NewIntVar(1, num_teams, 'match %i matchday %i ' % (match, md))
> int_x_match_md[(match, md)] = int_home_x_match_md[(match, md)]
> int_x_match_md[(match+num_matches//num_matchdays, md)] =
> int_away_x_match_md[(match, md)]
> for md in range(1,num_matchdays+1):
> model.AddAllDifferent([int_x_match_md[(match, md)] for match in
> range(1,num_matches//num_matchdays+num_matches//num_matchdays+1)])
>

So below is another issue. The way you are making unique matches is
interesting, but doing it your way caused the "alternation" constraint
below to cause the solver to bail out with "INFEASIBLE". Instead, I
would recommend something like "home * 100 + away", so you get, for
example, 132 if team 1 is home, team 32 is away.

>
> # Make the matches (pairings) all different
> int_z_match_md = {} # to create a pairing of the 2 integer variables
> int_home_x_match_md and int_away_x_match_md
> for match in range(1,num_matches//num_matchdays+1): # 16
> for md in range(1,num_matchdays+1): # 10
> int_z_match_md[(match, md)] = model.NewIntVar(1,
> num_teams*num_teams, 'z variable match %i matchday %i ' % (match, md))
> model.Add(int_z_match_md[(match, md)] ==
> int_home_x_match_md[(match, md)] * num_teams + int_away_x_match_md[(match,
> md)])
> model.AddAllDifferent([int_z_match_md[(match, md)] for md in
> range(1,num_matchdays+1) for match in
> range(1,num_matches//num_matchdays+1)])

I replaced the above with:

for match in range(1,num_matches+1): # 16

for md in range(1,num_matchdays+1): # 10
int_z_match_md[(match, md)] = model.NewIntVar(1,

num_teams*100+num_teams+1, # probably +1 is superfluous

'z variable match %i matchday %i ' % (match, md))

model.Add( int_z_match_md[(match, md)] == int_home_x_match_md[(match, md)] * 100 + int_away_x_match_md[(match, md)])

model.AddAllDifferent([int_z_match_md[(match, md)] for md in range(1,num_matchdays+1) for match in range(1,num_matches+1)])


>

For the alternation constraint, I also tweaked your code. I think
setting constraints on both home and away is overkill, possibly
leading to conflicts.

I replaced the above with:

boo_home_team = {}
# for md in range(1,num_matchdays+1):
for md in [1,2,9,10]: # only care about alternating 1&2, 9&10
for t in range(1,num_teams+1):
for match in range(1,num_matches+1):
boo_home_team[(t,match,md)] = model.NewBoolVar('home_team_'+str(t)+' is playing match '+str(match)+' on matchday '+str(md))

model.Add(int_home_x_match_md[(match, md)] == t).OnlyEnforceIf(boo_home_team[t,match,md])

for t in range(1,num_teams+1):
home_away_alternation_md1_md2 = []
home_away_alternation_md9_md10 = []
# boo_home_away_alternation_md1_md2[t] = model.NewBoolVar('home_team_'+str(t)+' is alternating on matchdays 1-2')
for match in range(1,num_matches+1):
# alternate day 1, 2
home_away_alternation_md1_md2.append(boo_home_team[(t,match,1)])
home_away_alternation_md1_md2.append(boo_home_team[(t,match,2)])
# alternate day 9, 10
home_away_alternation_md9_md10.append(boo_home_team[(t,match,9)])
home_away_alternation_md9_md10.append(boo_home_team[(t,match,10)])

model.Add(sum(home_away_alternation_md1_md2) == 1)
model.Add(sum(home_away_alternation_md9_md10) == 1)

>
>
> solver = cp_model.CpSolver()
> solver.parameters.max_time_in_seconds = 5
> solution_printer = SolutionPrinter()
> status = solver.Solve(model)

In order to see the print out of the results, I added at the end:


print('Solve status: %s' % solver.StatusName(status))
print('Optimal objective value: %i' % solver.ObjectiveValue())
print('Statistics')
print(' - conflicts : %i' % solver.NumConflicts())
print(' - branches : %i' % solver.NumBranches())
print(' - wall time : %f s' % solver.WallTime())

for md in range(1,num_matchdays+1): # 10

for match in range(1,num_matches+1): # 16
print('day',md,'match',match,'home',solver.Value(int_home_x_match_md[(match, md)]),
'away',solver.Value(int_away_x_match_md[(match, md)]),
'z match',solver.Value(int_z_match_md[(match, md)]))

Again, I'm not yet touching your "pots" of play requirement, but the
solution so far looks like teams only play each other once, and from
day 1 to day 2 and day 9 to day 10 every team is home team just once
(and away the other day).

Regards,

James E. Marca

(I will try to attach my code as an attachment so that it doesn't get formatted by my editor)

[Frédéric Girod]

Hi James,

Many thanks for your help !

I run your code and I get no solution (Solve status: MODEL_INVALID) ... I don't know why.

Moreover, indeed I didn't manage the pots approach, because I don't know how to handle this optimally ...

Any suggestion about this ? The tricky thing is the fact to consider at the same time home and away matches in this respect.

Thanks again.

[Frédéric Girod]

It seems that the following constraint is creating the Solve status: MODEL_INVALID :

# Teams shouldn't play against itself

for match in range(1,num_matches+1):

[Frédéric Girod]

It works fine without the above constraint !

Any suggestion related to the pot constraint ?

The 32 teams are comprised in the 4 pots of 8 teams, and each team should play against for example 2 teams of pot 1, 3 teams of pot 2, 3 teams of pot 3 and 2 teams of pot 4, to guarantee a certain competitive balance or diversification ....

[Frédéric Girod]

Please any thoughts ?

[Laurent Perron]

Are you sure there is a solution is with the pot constraints ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Le jeu. 1 août 2019 à 09:23, Frédéric Girod <fred.fred...@gmail.com> a écrit :

Please any thoughts ?

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/1d42861f-e4fa-455f-b511-0c160b3bd97b%40googlegroups.com.

[blind.line]

Strange the code runs fine on my laptop. Which version of OR Tools are you using?

Also, I’ll think about the inter-group competition constraint and if I come up with anything I’ll post it. 

James

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/85fd2cc0-6008-49e9-a009-a9e7b7cec00d%40googlegroups.com.

[Frédéric Girod]

No worries for the OR-Tools version ...

Yes I'm sure there is a solution is with the pot constraints ...

Thanks James.

[Frédéric Girod]

James,

Regarding my pots constraint, I tried this way (using int_z_match_md to handle home and away matches at the same time), but it doesn't seem to be working.

Do you have any kind of ideas why this doesn't work ?

boo_pot1_team = {}

boo_pot2_team = {}

boo_pot3_team = {}

boo_pot4_team = {}

for md in range(1,num_matchdays+1):

    for t in range(1,num_teams+1):

        for match in range(1,num_matches+1):

            boo_pot1_team[t,match,md] = model.NewBoolVar('home_team_'+str(t)+' is part of the pot 1 in MD'+str(md)+' and match '+str(match))

            model.Add(int_z_match_md[(match, md)] >= t*100+1).OnlyEnforceIf(boo_pot1_team[t,match,md])

            model.Add(int_z_match_md[(match, md)] <= t*100+8).OnlyEnforceIf(boo_pot1_team[t,match,md])

            boo_pot2_team[t,match,md] = model.NewBoolVar('home_team_'+str(t)+' is part of the pot 2 in MD'+str(md)+' and match '+str(match))

            model.Add(int_z_match_md[(match, md)] >= t*100+9).OnlyEnforceIf(boo_pot2_team[t,match,md])

            model.Add(int_z_match_md[(match, md)] <= t*100+16).OnlyEnforceIf(boo_pot2_team[t,match,md])

            boo_pot3_team[t,match,md] = model.NewBoolVar('home_team_'+str(t)+' is part of the pot 3 in MD'+str(md)+' and match '+str(match))

            model.Add(int_z_match_md[(match, md)] >= t*100+17).OnlyEnforceIf(boo_pot3_team[t,match,md])

            model.Add(int_z_match_md[(match, md)] <= t*100+24).OnlyEnforceIf(boo_pot3_team[t,match,md])

            boo_pot4_team[t,match,md] = model.NewBoolVar('home_team_'+str(t)+' is part of the pot 4 in MD'+str(md)+' and match '+str(match))

            model.Add(int_z_match_md[(match, md)] >= t*100+25).OnlyEnforceIf(boo_pot4_team[t,match,md])

            model.Add(int_z_match_md[(match, md)] <= t*100+32).OnlyEnforceIf(boo_pot4_team[t,match,md])

for t in range(1,num_teams+1):

    

    pot1_diversification = []

    for match in range(1,num_matches+1):

        for md in range(1,num_matchdays+1):

            pot1_diversification.append(boo_pot1_team[(t,match,md)])

    model.Add(sum(pot1_diversification) <= 2)

        

    pot2_diversification = []

    for match in range(1,num_matches+1):

        for md in range(1,num_matchdays+1):

            pot2_diversification.append(boo_pot2_team[(t,match,md)])

    model.Add(sum(pot2_diversification) <= 3)

    

    pot3_diversification = []

    for match in range(1,num_matches+1):

        for md in range(1,num_matchdays+1):

            pot3_diversification.append(boo_pot3_team[(t,match,md)])

    model.Add(sum(pot3_diversification) <= 3)

    

    pot4_diversification = []

    for match in range(1,num_matches+1):

        for md in range(1,num_matchdays+1):

            pot4_diversification.append(boo_pot4_team[(t,match,md)])

    model.Add(sum(pot4_diversification) <= 2)

[blind.lin...@gmail.com]

I'm playing around with a different approach, but it isn't working yet

> --
> You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/3664e4de-4e44-43d7-927d-90d89efbf3b7%40googlegroups.com.


--

James E. Marca

[Laurent Perron]

Hi

I hope you all saw https://github.com/google/or-tools/blob/stable/examples/cpp/sports_scheduling_sat.cc

Just saying

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/20190803181938.GA1%406b0018d613f7.

[blind.lin...@gmail.com]

Nope didn't see that, I'll check it out and compare.

But I was looking for a problem to learn CP-SAT, and this was pretty
good. Now I can study the differences with the C++ code and learn
more. And maybe blow some more dust off my 25-year-old C++ skills.
win-win!

Anyway, I solved the "equal pots play" aspect, but the solution
is still super slow...took about 90 minutes to get a solution.

Basic idea to balance "pots" play is that there are 16 unique groups
of combinations of the 4 pots, so I constrained each to have exactly
10 games.

boo_11 is pot 1 home, pot 1 away, constrained to 10 games;
boo_12 is pot 1 home, pot 2 away, constrained to 10 games;
and so on for all 16 combinations.

A little bit tedious and brute-forcey, but it seems to work. Code snippets

```
# lists for the booleans for pot to pot play
boo_11 = []
boo_12 = []
boo_13 = []
...

for md in range(1,num_matchdays+1):
for match in range(1,num_matches+1):
# set things up for inter-pool play constraints
...
boo_11.append(model.NewBoolVar('pot 1 home pot 1 away in match '+str(match)+' on day '+str(md)))
boo_12.append(model.NewBoolVar('pot 1 home pot 2 away in match '+str(match)+' on day '+str(md)))
... blah blah blah ...

# loop over each team in each pot, to set what I think of as
# negative space constraints...A implies Not(B).
# For t in pot1, if we know (is true) that the home team is
# from Pot 1 (A), then it must be false that the home team is from
# any other pot, so boo_2? can be set to 0 (false) (not B)

for t in pot1:
model.Add(boo_21[-1] == 0).OnlyEnforceIf(boo_home_team[(t,match,md)])
model.Add(boo_22[-1] == 0).OnlyEnforceIf(boo_home_team[(t,match,md)])
model.Add(boo_23[-1] == 0).OnlyEnforceIf(boo_home_team[(t,match,md)])
... etc ...
... and also for the away side of the match ...
model.Add(boo_34[-1] == 0).OnlyEnforceIf(boo_away_team[(t,match,md)])
model.Add(boo_44[-1] == 0).OnlyEnforceIf(boo_away_team[(t,match,md)])

for t in pot2:
model.Add(boo_11[-1] == 0).OnlyEnforceIf(boo_home_team[(t,match,md)])
model.Add(boo_12[-1] == 0).OnlyEnforceIf(boo_home_team[(t,match,md)])
model.Add(boo_13[-1] == 0).OnlyEnforceIf(boo_home_team[(t,match,md)])
...
... ditto for pot3, pot4 ...

# then tell the solver how many should be true, otherwise it will
# happily set them all false and there will be no pot mixing going on

model.Add(sum(boo_11) >= 10)
model.Add(sum(boo_22) >= 10)
model.Add(sum(boo_33) >= 10)
model.Add(sum(boo_44) >= 10)

model.Add(sum(boo_12) >= 10)
model.Add(sum(boo_13) >= 10)
model.Add(sum(boo_14) >= 10)
model.Add(sum(boo_21) >= 10)
model.Add(sum(boo_23) >= 10)
model.Add(sum(boo_24) >= 10)
model.Add(sum(boo_31) >= 10)
model.Add(sum(boo_32) >= 10)
model.Add(sum(boo_34) >= 10)
model.Add(sum(boo_41) >= 10)
model.Add(sum(boo_42) >= 10)
model.Add(sum(boo_43) >= 10)

```

Setting this last constraint was interesting. Probably can be ==
rather than >=, but I was slowly ratcheting up the constraint. At >=
8, the answer was wrong, but came back in 30 seconds. There was a
good bit of inter-pot play happening, just not even across the
board. Bumping up to >=9 took more than 600 seconds, so I just did 10
and let it run on my server, where it solved in 90 minutes.

I'm going to clean up my code a bit and see if I can't get rid of some
extraneous constraints and speed things up, then I'll post it,
probably on Monday.

Regards,
James

> To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEeaxAmmFsoWem7r0MS02wpYdf%3Dt6kxhC2iS24xe3PZDDqQ%40mail.gmail.com.

[Frédéric Girod]

Many thanks James for this approach.

It does the job for sure, but I'm wondering why I end up with the same result whatever the constraints model.Add(sum(boo_11) >= 10)  or model.Add(sum(boo_11) == 10) or model.Add(sum(boo_11) <= 3)  ....

Moreover, how would you control for the minimum number of teams in each pot ? Because your approach is adding a good diversification within pots, but we could possibly end up with 0 team or only 1 team in one particular pot ...

[blind.lin...@gmail.com]

Replies inline below:

On Mon, Aug 05, 2019 at 06:54:39AM -0700, Frédéric Girod wrote:
> Many thanks James for this approach.
>
> It does the job for sure, but I'm wondering why I end up with the same
> result whatever the constraints model.Add(sum(boo_11) >= 10) or
> model.Add(sum(boo_11) == 10) or model.Add(sum(boo_11) <= 3) ....

Well, *I* don't see exactly get the same results.

I think what is happening is that without these sum constraints, the
solver has no reason to set the boo_xy variables to be true. It can
set them all false without any consequences. As the target sum goes
up, the solver will set an appropriate number true to meet the needs
of the sum constraint. However, if the total sum across all of the
games is not 160, then there is still slack there for the solver to
play with.

So the constraint set to 10 across all combinations is binding, less
than 10 is really isn't binding, because the sum of sums is less than
the number of games.

In my final code (attached) I dump the pot-to-pot play sums in the final
solution to check this.

>
> Moreover, how would you control for the minimum number of teams in each pot
> ? Because your approach is adding a good diversification within pots, but
> we could possibly end up with 0 team or only 1 team in one particular pot
> ...

Well, yes, it is a cheat to set to 10. Better would be to force the
sum of sums to be equal to the total number of expected games, and
then to set specific sums according to some rule.

It isn't hard to come up with a breaking case. Suppose you have 41
teams in 5 pots, with one extra team in pot 1, and with 20 games each
game day but one team gets a bye every week, and suppose you have 11
game days, not 10. Then almost nothing breaks down evenly.

The best way is probably to have the league scheduler decide up front
how to break down the pot to pot sums. Another way might be to
require that the total sum of sums == total number of games, and then
set various equality constraints, so, say, sum (pot_11) == sum(pot_22)
== sum(pot_33) == sum(pot_44), and so on.

My code and output are attached. I added some comments, but was
unable to get it to run much faster. I just ran it with the latest
changes and it completed successfully. Latest run time is about 70
minutes (4,229 seconds) on my server.


James E. Marca

[Frédéric Girod]

Thanks so much James for the time you spent on it.

Your code is brilliant, and makes a lot of sense from my point of view.

And you're right, we couldn't impose the teams to be uniformly or equally broken down in the 4 pots.

But do you think it could be possible to add a minimum number of teams per pots, i.e. 1 or 2, in order for the teams to be present in the 4 pots, or to get at least 2 teams present in each pot ?

[Frédéric Girod]

Because it is not always the case ...

I ran your code :

Nb of teams in pots:

	Pot_1	Pot_2	Pot_3	Pot_4
team_1	2	2	3	3
team_2	3	2	2	3
team_3	1	2	4	3
team_4	1	4	2	3
team_5	5	1	2	2
team_6	3	3	2	2
team_7	3	3	2	2
team_8	2	3	3	2
team_9	4	2	1	3
team_10	3	1	4	2
team_11	2	3	2	3
team_12	0	4	4	2
team_13	3	4	1	2
team_14	2	2	3	3
team_15	3	2	3	2
team_16	3	2	2	3
team_17	2	3	3	2
team_18	2	4	0	4
team_19	2	3	4	1
team_20	2	3	2	3
team_21	2	3	3	2
team_22	3	1	3	3
team_23	3	2	2	3
team_24	4	1	3	2
team_25	1	4	1	4
team_26	5	3	1	1
team_27	2	2	4	2
team_28	1	4	3	2
team_29	4	1	2	3
team_30	2	3	3	2
team_31	1	1	4	4
team_32	4	2	2	2

[blind.lin...@gmail.com]

Oh, I *think* I get what you are saying now.

Correct me if I'm wrong, but you're saying, for example, that team_1
plays 2 times against pot 1, two times against pot 2, and three times
against teams from pots 3 and 4. In contrast, team 12 plays zero
times against pot 1, 4 times against pots 2 and 3, and two times
against pot 4. What you are saying is that you want that to be more
balanced across teams, right?

Well that wasn't your original request! You just said you wanted play
between pots to be evenly distributed. The constraints do that. They
do *nothing* about making sure there is an even distribution of teams
from within the pot. All it should take is setting up another
constraint and making it roughly uniform. Something like your matrix
below, but each entry is set >= num_matchdays // num_pots,
which in this case is 10 // 4 = 2.

By the way, in my code if you comment out the constraint at about line 330 of

#model.Add(sum(boo_11) == 10)

and then add a new variable all_pots and an associated constraint

all_pots = []

...
# inside the loop, where boo_xy are created, do:

for b in [boo_11,boo_12,boo_13,boo_14
,boo_21,boo_22,boo_23,boo_24
,boo_31,boo_32,boo_33,boo_34
,boo_41,boo_42,boo_43,boo_44]:
all_pots.append(b[-1])

... then later at about line 340 add the sum of sums constraint

model.Add(sum(all_pots) == num_matches * num_matchdays)

I'm seeing a 10 minute speed up (60 minutes instead of 70).

Regards,

James

On Mon, Aug 05, 2019 at 01:42:17PM -0700, Frédéric Girod wrote:
> Because it is not always the case ...
>
> I ran your code :
>

> *Nb of teams in pots:*

> --

[Frédéric Girod]

Hi James,

Many thanks again.

You're totally right, I want the output to be more balanced across teams, that's why I was speaking about possibly a minimum number of teams per pot.

In my example above, team 12 allocation is not acceptable because it plays zero times against pot 1.

I didn't get how to ensure a more evenly distributed output in your message above, by tweaking your code in lines 330, 340 ...

Ideally, a good way to guarantee an even distribution would be for example to set out this rule :

- Team pot 1 should play versus 2 teams of pot 1, 3 teams of pot 2, 3 teams of pot 3, 2 teams of pot 4.

- Team pot 2 should play versus 3 teams of pot 1, 2 teams of pot 2, 2 teams of pot 3, 3 teams of pot 4.

- Team pot 3 should play versus 3 teams of pot 1, 2 teams of pot 2, 2 teams of pot 3, 3 teams of pot 4.

- Team pot 4 should play versus 2 teams of pot 1, 3 teams of pot 2, 3 teams of pot 3, 2 teams of pot 4.

That is just an example, but I don't see how to tweak your code to eventually end up with such constraints.

[Frédéric Girod]

Or maybe just guaranteeing a minimum number of 2 teams per pots could be easier implemented ...

[Frédéric Girod]

I tried with this kind of constraint :

model.Add(sum(boo_11_)+sum(boo_12_)+sum(boo_13_)+sum(boo_14_) >= 2), 

where boo_11_  is a boolean = 1 when team is in pot 1 home pot 1 away.

But the solver finds no solution with such constraints...

[Frédéric Girod]

Sorry the solver finds a solution finally, but the minimum 2 teams per pot is not fulfilled ....

[blind.lin...@gmail.com]

On Tue, Aug 06, 2019 at 12:55:26AM -0700, Frédéric Girod wrote:
> Hi James,
>
> Many thanks again.
>
> You're totally right, I want the output to be more balanced across teams,
> that's why I was speaking about possibly a minimum number of teams per pot.
>
> In my example above, team 12 allocation is not acceptable because it plays
> zero times against pot 1.
>
> I didn't get how to ensure a more evenly distributed output in your message
> above, by tweaking your code in lines 330, 340 ...

Oh yeah that was unrelated. That was just for speeding up my code.

>
> Ideally, a good way to guarantee an even distribution would be for example
> to set out this rule :
>
> - Team pot 1 should play versus 2 teams of pot 1, 3 teams of pot 2, 3 teams
> of pot 3, 2 teams of pot 4.
> - Team pot 2 should play versus 3 teams of pot 1, 2 teams of pot 2, 2 teams
> of pot 3, 3 teams of pot 4.
> - Team pot 3 should play versus 3 teams of pot 1, 2 teams of pot 2, 2 teams
> of pot 3, 3 teams of pot 4.
> - Team pot 4 should play versus 2 teams of pot 1, 3 teams of pot 2, 3 teams
> of pot 3, 2 teams of pot 4.
>
> That is just an example, but I don't see how to tweak your code to
> eventually end up with such constraints.

Yeah I'm not sure exactly how to do it either, but that approach is
what I would do. Cross the boo_xy variable with the possible teams t
for each match, stash in one array per matrix cell, and then sum those
up to get the contents of each cell in your matrix. Then require each
cell to be >= 2. But that's going to be a lot more constraints, and
will slow the model down significantly, so I wonder if putting in that
kind of constraint will remove the need for the boo_xy--pot-balancing
constraints I already put in.

I'm going to study the C++ example today, then I'll get back to this
wrinkle. But I have a proposal to write too so I probably won't get
back to it today.

James E. Marca

[Frédéric Girod]

Thanks James, your help is much appreciated.

[Frédéric Girod]

Hi James,

I have tried to implement your approach above (crossing the boo_xy variable with the possible teams t for each match, then sum up ...), but after the solver ran 2 hours, it didn't find any solution with this type of constraint (for example below, on pot 1)

# pot 1

for t in range(1,num_teams+1):

    model.Add(sum(boo_11[t]+boo_12[t]+boo_13[t]+boo_14[t]+boo_21[t]+boo_31[t]+boo_41[t]) >= 2)

Did I do something wrong ?

[blind.lin...@gmail.com]

I don't know, but I would expect it to take a very long time. It
isn't terribly fast without that constraint, and adding that pool
balancing adds a ton more constraints. Let it run overnight and see
if it converges. If it doesn't say "INFEASIBLE", then maybe the
solution exists.

Otherwise, try to streamline the constraints.

>
> --
> You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/8b2f40da-3b55-4368-86d9-3a25d3db07d1%40googlegroups.com.


--

James E. Marca

[blind.lin...@gmail.com]

Hi Frédéric,

I took a look at the C++ version of sports scheduling hinted at by
Laurent and after figuring out what was happening with the sequence of
four AddBoolOr constraints (that's a blog post, I guess), I was able
to modify it to work with your problem.

As you might expect, it runs much faster---about 5 minutes on my
laptop using 6 cores.

A few learnings from that exercise---I don't think you need to keep
track of your variables int_home_x_match_md and int_away_x_match_md.
The C++ code has no such explicit tracking of who plays whom, and it
works just fine. I just had to back out the teams by looking at which
of the fixture tracking variable array was true. In your code, you
have the lines:

```
model.Add(int_home_x_match_md[(match, md)] == t).OnlyEnforceIf(boo_home_team[(t,match,md)])
model.Add(int_away_x_match_md[(match, md)] == t).OnlyEnforceIf(boo_away_team[(t,match,md)])
```

While it would take some writing to rework all of your constraints, I
don't think you don't need that, which will help eliminate a whole
bunch of variables and constraints. I think you can get by just using
your boo_home_team[t,match,md] and boo_away_team[t,match,md].

Second, I did that pool balancing as I suggested, with a loop over
teams and then teams withing opposing pools:

```
pool_play = [] # play between pools, for team vs pool balancing
pool_balance = [] # also play between pools, for pool vs pool
...
# pool play loop
# home team group is outer loop
for ppi in range(num_groups):
pool_balance.append([])
for t in groups[ppi]:
pool_play.append([])
# other team group is inner loop
for ppj in range(num_groups):
pool_balance[ppi].append([])
pool_play[t].append([])
# over all the days, have to play each pool at least once
for d in matchdays:
for opponent in groups[ppj]:
if t == opponent:
# cannot play self
continue
pool_play[t][ppj].append(fixtures[d][t][opponent])
pool_balance[ppi][ppj].append(fixtures[d][t][opponent])
# over all the days, have to play each pool at least once
model.AddBoolOr(pool_play[t][ppj])
# now for group to group, balance play
# 10 is hardcoded for now
for ppi in range(num_groups):
for ppj in range(num_groups):
model.Add(sum(pool_balance[ppi][ppj]) == 10)

```

Basically, what I am doing with the pool_play list is to make sure
that over all the days, each team plays at least one team (AddBoolOr)
from each pool. Then with the pool_balance list, I am requiring that
each pool play every other pool ten times (still hardcoded because I'm
lazy).

I've attached code and output.

Hope that helps.

James

On Wed, Aug 07, 2019 at 12:16:17AM -0700, Frédéric Girod wrote:

[Frédéric Girod]

Hi James !

Thank you so very much to have turned the C# code into my project.

Indeed your findings are very interesting.

Following this new approach of modeling sports schedule, do you think we could also handle my 4 pots constraint, in order to end up with balanced match sequences ?

[blind.lin...@gmail.com]

My code does already! Read the output...the pots (I call them pools
and groups in the code) are balanced, both pot to pot and team to pot.

Regards,
James

[Frédéric Girod]

Oh sorry James.

I had not taken time yet to go through your code.

And I don't know why, but your code is bugging on my personal laptop (it happened already). I will run it on my professional laptop tomorrow.

Meanwhile, I'm taking a look at your code !

Many thanks again.

[blind.lin...@gmail.com]

On Wed, Aug 07, 2019 at 12:26:30PM -0700, Frédéric Girod wrote:
> Oh sorry James.
>
> I had not taken time yet to go through your code.
>
> And I don't know why, but your code is bugging on my personal laptop (it
> happened already). I will run it on my professional laptop tomorrow.

Could be lots of reasons. I've had that sort of issue in the past, so
these days I run OR Tools in a docker container and every machine has
the identical container. Makes things reproducible and transferrable
(esp. to clients!).

But if you don't run Docker, it is a bit of a pain to get up and
running the first time.

>
> Meanwhile, I'm taking a look at your code !
>
> Many thanks again.
>

> --
> You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/bec602a8-bfb8-42cf-b025-ccb0f9a08aec%40googlegroups.com.


--

James E. Marca

[Frédéric Girod]

sorry to bother again James, but could you tell me where in your code do you handle the pots constraint ?

Did you set out a minimum number of teams per pot ? If not, how do you make sure plays are evenly spread between groups ?

[Frédéric Girod]

Because I don't see where and how this is managed in your code ....

[blind.line]

??  Didn’t I say already??

I copied that but in my earlier email. Did you read it?  I said “Second, I did that pool play balancing...” and then I cut and paste the code, then I summarized what it does. 

And the output proves that it works reasonably well, as every team plays at least one tame vs every group/pot. 

James

On Aug 7, 2019, at 12:42, Frédéric Girod <fred.fred...@gmail.com> wrote:

sorry to bother again James, but could you tell me where in your code do you handle the pots constraint ?

Did you set out a minimum number of teams per pot ? If not, how do you make sure plays are evenly spread between groups ?

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/9b723fd8-b267-4681-912d-7748d109cccc%40googlegroups.com.

[Frédéric Girod]

Sorry I got confused between pools, groups, pots...

[Frédéric Girod]

James, now I see better how all this works ... and it is quite brilliant.

More generally speaking, it seems more efficient to handle boolean variables instead of integer variables, especially when it comes to optimization / combinatorial problems.

The constraint model.AddBoolOr(pool_play[t][ppj]) in line about 94 is quite powerful to get teams to play each pool at least once, but I'm not sure we could generalize this approach to impose, for example, that any team can play each pool at least twice or exactly twice (or exactly third for one particular pool) ....

What do you think ?

[blind.lin...@gmail.com]

On Wed, Aug 07, 2019 at 01:28:02PM -0700, Frédéric Girod wrote:
> James, now I see better how all this works ... and it is quite brilliant.
>

Don't give me the credit for the brilliance...I just translated the
C++ example to python and modified around the margins to adjust it to
your case.

> More generally speaking, it seems more efficient to handle boolean
> variables instead of integer variables, especially when it comes to
> optimization / combinatorial problems.
>
> The constraint model.AddBoolOr(pool_play[t][ppj]) in line about 94 is quite
> powerful to get teams to play each pool at least once, but I'm not sure we
> could generalize this approach to impose, for example, that any team can
> play each pool at least twice or exactly twice (or exactly third for one
> particular pool) ....

Well,

AddBoolOr(list_of_bool)

is the *same* as

Add(sum(list_of_bool)>= 1)

So if you want to do >=2, 3, etc, then just use model.Add(sum(...)>=2)

If you have specific requirements, you can hard-code them, or have
a lookup table, etc.

>
> What do you think ?
>

> --
> You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/84634eeb-5330-4d9b-91af-6d0c1bc6c642%40googlegroups.com.


--

James E. Marca

[Laurent Perron]

Good job James!

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/20190807221354.GA1%4085db2e882bbb.

[Frédéric Girod]

Great job James and many thanks.

[Frédéric Girod]

Hi James,

Sorry to bother again: do you have any kind of idea why imposing a minimum of 2 teams per pots ( model.Add(sum(pool_play[t][ppj])>= 2) ) results in an infeasible solve status ?

Because I notice the solver has enough leeway to find a solution ...

[blind.line]

Yeah...my constraint is buggy.  It’s just summing the home games. You can tell by looking at the output. 

I fixed it, and as soon as it runs properly I’ll post the fix. 

James

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/fb93d99c-ee4b-4bac-8100-6b90fbe1e6ec%40googlegroups.com.

[Laurent Perron]

Once the code is complete, can you submit a PR to add it to examples/contrib ?

That would be very nice 

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/9C006837-C78F-494D-8362-561322D215A3%40gmail.com.

[J. E. Marca]

Okay, I cleaned stuff up, turned on command line options, etc etc.

I try now to consistently use "pool" instead of group or pot.

Things are a little different than before.  The pool to pool balancing recognizes that teams cannot play themselves.  So, for example, pool 0 vs pool 0 is constrained to a lower value than pool 0 vs pool 1.

Similar issue in team vs pool constraints...if the team is playing its own pool, there are fewer *possible* games than if a team is playing versus a different pool, and the constraints are adjusted accordingly.

The big change is that this version of the code will actually work if there are enough game days such that teams play each other multiple times.  In your original test case, 10 days is not enough time for all 32 teams to play each other.  Now if you set 31 or 62 or more days, the solver will work properly, and teams will play each other only once within the 31-days needed for all teams to play each other.  So from day 1 to day 31, team i will play team j once; from day 32 to day 61, team i will play team j once; and so on.

Code attached. 

Laurent, I will submit a PR adding it to example/contrib soon. 

[Frédéric Girod]

Hi James,

Many thanks.

Great job again.

With regards to the pot constraint, I guess the constraint below is controlling for any team having to play each pool at least once, or twice, ...

model.Add(sum(pool_play[t][ppi]) >= local_count)

So I guess I should set the variable 'local_count' to 2, if I wanna make each team to play each pool at least twice....

But it doesn't seem to work.

Do I badly use your code ?

[Frédéric Girod]

Moreover, I was wondering if there is a technical way to log or display the number of feasible solutions while the solver is running ?

[Laurent Perron]

parameters log_search_progress

Le mar. 13 août 2019 à 09:10, Frédéric Girod <fred.fred...@gmail.com> a écrit :

Moreover, I was wondering if there is a technical way to log or display the number of feasible solutions while the solver is running ?

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/5421d22b-e26a-4c1f-84d6-ebef73126e2d%40googlegroups.com.

--

--Laurent

[blind.lin...@gmail.com]

On Tue, Aug 13, 2019 at 09:10:36AM -0700, Frédéric Girod wrote:
> Moreover, I was wondering if there is a technical way to log or display the
> number of feasible solutions while the solver is running ?

in my code, use the --debug command line flag to turn on the solver's
log search progress

>
> --
> You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/5421d22b-e26a-4c1f-84d6-ebef73126e2d%40googlegroups.com.


--

James E. Marca

[Frédéric Girod]

Thanks Laurent and James.

James, have you got an idea why changing 'local_count' variable in the constraint isn't changing anything to the output ?

If I'm not mistaken, I still get teams not represented by a pool.

[blind.lin...@gmail.com]

On Tue, Aug 13, 2019 at 02:26:44AM -0700, Frédéric Girod wrote:
> Hi James,
>
> Many thanks.
>
> Great job again.
>
> With regards to the pot constraint, I guess the constraint below is
> controlling for any team having to play each pool at least once, or twice,
> ...
>
> model.Add(sum(pool_play[t][ppi]) >= local_count)
>
>
> So I guess I should set the variable 'local_count' to 2, if I wanna make each team to play each pool at least twice....

No, actually, that will tend to fail. One cannot arbitrarily force a
number of matchups. My code tries to make the most possible matchups
while balancing across pools.

Consider your special case of 32 teams, 4 pools, and let's say we're
talking about the first team (t==0).

Each pool has 8 teams.

Team 0 is in pool 0.

The maximum possible games team 0 can play against pool 0 is 7
(because team 0 cannot play team 0

The most possible versus pools 1,2,3 is 8 (t0 vs t7,t8,...t15 etc)

That is covered in the code:

```python
my_size = len(pools[ppi])
other_size = len(pools[ppj])
# this team vs all other teams, figure max games vs this pool
pool_matchup_count = int(other_size)
if t in pools[ppi]:
# "other pool" is actually my pool. can't play self
pool_matchup_count = int((my_size-1))
local_count = matchups*pool_matchup_count

```

Again, in your 32 team, 10 matchdays case, you are in the
"matchups_exact==False" case, so it is more complicated. You have to
distribute the remaining games (at most 10 per team) across the pools:

```python
if not matchups_exact:
# in this case, last round of matchups is not complete. must play less
games_remaining = total_games - ((matchups-1)*unique_games)
# print(total_games,matchups,unique_games,games_remaining,pool_matchup_count,(games_remaining*pool_matchup_count//unique_games))
# print(local_count,'becomes...')
local_count = int((matchups-1)*pool_matchup_count + games_remaining*pool_matchup_count//unique_games)
# print(local_count)
# assert 0

model.Add(sum(pool_play[t][ppi]) >= local_count)

```

(Those print statements and the assert 0 was put there so I could
study what local_count was under different conditions)

So the distribute pool play rule is a simple scaled ratio

total_unique_games games left to play
------------------ = ---------------------
pool matchup count local_count

so local_count = games_left_to_play * (pool_matchup_count/total_unique_games)

pool_matchup_count is 7 (again, because we're talking about pool 0, team 0)

total_unique_games if every team plays every team is 32*31/2 = 992/2 = 496

games left to play is 160 (10 days, 16 games per day)

matchups = 1, so matchups-1 = 0, so ignoring that term...

so:
local_count_for_t0_vs_pool0 = 160 * (7 / 496)
= 2.25
= 2 (after rounding with integer division //)

Local count *is* set to 2 for team 0 versus pool 0.

Because you have so few games compared to 496, the local count for
team 0 versus pools 1,2,3 is also 2 (2.6 or so rounds to 2)

If you uncomment the print lines above, and if you call my program with:

python src/cp_sat/sports_schedule_sat.py -t 32 -d 10 -p 4 --max_home_stand=2 --debug

then you will see the print statements:

...
160 1 496.0 160.0 7 2.0
7 becomes...
2
160 1 496.0 160.0 8 2.0
8 becomes...
2
160 1 496.0 160.0 8 2.0
8 becomes...
2
160 1 496.0 160.0 8 2.0
8 becomes...
2
...

And then the final output should show the result:

...
team 1 (home or away) versus pool 0 = 2
team 1 (home or away) versus pool 1 = 3
team 1 (home or away) versus pool 2 = 3
team 1 (home or away) versus pool 3 = 2
team 2 (home or away) versus pool 0 = 4
team 2 (home or away) versus pool 1 = 2
team 2 (home or away) versus pool 2 = 2
team 2 (home or away) versus pool 3 = 2
...

or something similar. All teams play at least two games versus all pools.

You can change the program to force a special case of course, but I
was trying to solve the general case. If you run with 31 days, then

python src/cp_sat/sports_schedule_sat.py -t 32 -d 31 -p 4 --max_home_stand=2 --debug


Then that outputs matchups of:

...
team 1 (home or away) versus pool 0 = 7
team 1 (home or away) versus pool 1 = 8
team 1 (home or away) versus pool 2 = 8
team 1 (home or away) versus pool 3 = 8
team 2 (home or away) versus pool 0 = 7
team 2 (home or away) versus pool 1 = 8
team 2 (home or away) versus pool 2 = 8
team 2 (home or away) versus pool 3 = 8
...

Does that makes sense?

>
>
> But it doesn't seem to work.
>
>
> Do I badly use your code ?
>
>

James E. Marca

[blind.lin...@gmail.com]

On Tue, Aug 13, 2019 at 09:10:36AM -0700, Frédéric Girod wrote:

> Moreover, I was wondering if there is a technical way to log or display the
> number of feasible solutions while the solver is running ?

I don't know. You might need to set up a SolutionPrinter callback and then call:

solver.SearchForAllSolutions(model, solution_printer)

In order to see all feasible solutions. But that could take a very
long time to find all solutions. I haven't really played with that
aspect of the solver

Regards,
James

[Frédéric Girod]

James,

Thanks for the explanations, they make a lot of sense.

2 things:

- If I want to change the program to force a special case (e.g. minimum number of opponents from pot 2 for teams from pot 1 is 3), then do you think that forcing local_count = 3 for teams in pot 1 and opponents in pot 2, can work ? But I don't see how to link with opponents...

- When I set up the SolutionPrinter callback and then call    solver.SearchForAllSolutions(model, solution_printer) , it doesn't work, apparently due to the presence of an explicit optimization function (min...), for some reasons are not aware of.

[blind.line]

Frédéric,

On Aug 13, 2019, at 12:11, Frédéric Girod <fred.fred...@gmail.com> wrote:

James,

Thanks for the explanations, they make a lot of sense.

2 things:

- If I want to change the program to force a special case (e.g. minimum number of opponents from pot 2 for teams from pot 1 is 3), then do you think that forcing local_count = 3 for teams in pot 1 and opponents in pot 2, can work ? But I don't see how to link with opponents...

That would take some rewriting. I’d set up a csv or json input file if you want that flexibility. 

- When I set up the SolutionPrinter callback and then call    solver.SearchForAllSolutions(model, solution_printer) , it doesn't work, apparently due to the presence of an explicit optimization function (min...), for some reasons are not aware of.

Well, delete the minimization line. That was ported from the C++ example. In most cases I’ve been able to get it to push the “breaks” value down to the number of days, so you can probably set that to a hard equality. Or maybe number of days +1. (I’m away from computer and can’t text right now.)

Not really sure if the theory behind the concept of breaks, but it seems it isn’t always possible to force strict alternation of home and away games, so this constraint is trying to minimize the number of times a break happens—a team has two consecutive home games or away games. 

(The C++ code had a value equal to the number of match days (=2 * num_teams - 4), but it was set in terms of number of teams, so I punted on that one and picked matchdays rather than the original 2 * num_teams - 4. Seems to work.)

James

[Laurent Perron]

If you have more than 2 teams, you must have breaks. There is a known lower bound.  Like n-2.

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/80C19062-1D9D-4B22-95BA-761C4DCE1A88%40gmail.com.

[Frédéric Girod]

James,

If you have additional time, I would be very keen to be able to use a csv file with all the minimum number of teams per pots ...

That would be great.

And for all the possible solutions, I tried to store those, but when I delete the minimization line, it doesn't work either: I get a bunch of 0 for the different outputs.

I'm also away from my laptop, but that's what I have in mind ... ~30 outputs with 0.

[blind.line]

Frédéric,

No offense intended, but I think I’ve had my fill of this problem...details like flexible input handling etc are not interesting to me. 

James

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/97b04282-6537-4f80-b87b-7b9485229584%40googlegroups.com.

[J. E. Marca]

Right.  I should have looked it up!

In "Scheduling in sports, an annotated bibliography",  http://dx.doi.org/10.1016/j.cor.2009.05.013 they discuss the problem in terms of "A complete graph Kn on n nodes is used to represent single round-robin tournaments.  Its nodes 1...n represent the teams"  Then later they cite de Werra D. Scheduling in sports. In: Hansen P, editor. Studies on graphs and discrete programming. Amsterdam: North-Holland; 1981. p. 381–95. "Based on the complete graph model, it is shown that schedules for n teams with even n have at least n − 2 breaks. ... Furthermore, for odd n schedules without any breaks are constructed."

In this program, in which there might not be enough days for a round robin tournament, I think setting the breaks lower bound to number of days is okay.  But maybe should be number of days - 1, given that number of days for a round robin tournament with one game per day is n-1.

On Tuesday, August 13, 2019 at 12:49:16 PM UTC-7, Laurent Perron wrote:

If you have more than 2 teams, you must have breaks. There is a known lower bound.  Like n-2.

Le mar. 13 août 2019 à 12:45, blind.line <blind.li...@gmail.com> a écrit :

Frédéric,

On Aug 13, 2019, at 12:11, Frédéric Girod <fred.fre...@gmail.com> wrote:

James,

Thanks for the explanations, they make a lot of sense.

2 things:

- If I want to change the program to force a special case (e.g. minimum number of opponents from pot 2 for teams from pot 1 is 3), then do you think that forcing local_count = 3 for teams in pot 1 and opponents in pot 2, can work ? But I don't see how to link with opponents...

That would take some rewriting. I’d set up a csv or json input file if you want that flexibility. 

- When I set up the SolutionPrinter callback and then call    solver.SearchForAllSolutions(model, solution_printer) , it doesn't work, apparently due to the presence of an explicit optimization function (min...), for some reasons are not aware of.

Well, delete the minimization line. That was ported from the C++ example. In most cases I’ve been able to get it to push the “breaks” value down to the number of days, so you can probably set that to a hard equality. Or maybe number of days +1. (I’m away from computer and can’t text right now.)

Not really sure if the theory behind the concept of breaks, but it seems it isn’t always possible to force strict alternation of home and away games, so this constraint is trying to minimize the number of times a break happens—a team has two consecutive home games or away games. 

(The C++ code had a value equal to the number of match days (=2 * num_teams - 4), but it was set in terms of number of teams, so I punted on that one and picked matchdays rather than the original 2 * num_teams - 4. Seems to work.)

James

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools...@googlegroups.com.

[Frédéric Girod]

I totally understand.

Many many thanks James for this great job.

[Frédéric Girod]

Hi Laurent,

A quick question for you specifically: I tried everything to get the number of feasible solutions but failed to do so.

The parameters log_search_progress is True (or debug in James code), I have used a SolutionPrinter() and solver.SearchForAllSolutions(model, solution_printer), but I don't get anything....

Have you got another idea ?

Le mardi 13 août 2019 18:15:07 UTC+2, Laurent Perron a écrit :

parameters log_search_progress

Le mar. 13 août 2019 à 09:10, Frédéric Girod <fred.fre...@gmail.com> a écrit :

Moreover, I was wondering if there is a technical way to log or display the number of feasible solutions while the solver is running ?

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/5421d22b-e26a-4c1f-84d6-ebef73126e2d%40googlegroups.com.

--

--Laurent

[blind.lin...@gmail.com]

I got solutions to print with these sorts of steps:

First, I'm assuming I'm passing my variable "fixtures", which is array of array of array:

class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""

def __init__(self, variables):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__variables = variables
self.__solution_count = 0

def on_solution_callback(self):
self.__solution_count += 1
for vi in self.__variables:
# print(vi)
for vij in vi:
# print(vij)
for vijk in vij:
# print(vijk)
if self.Value(vijk): # fixture is true, print the details
print('%s=%i' % (vijk, self.Value(vijk)), end='\n')
print()

def solution_count(self):
return self.__solution_count


That is, only print the fixtures that are "true"

Second, you can't minimize,

# model.Minimize(sum(breaks))

you have to set the breaks bound as a hard constraint,

// literature aside, if matchdays is odd, cannot hit the bound
if num_matchdays % 2:
model.Add(sum(breaks) == num_matchdays+1)
else:
model.Add(sum(breaks) == num_matchdays)



and you can't use more than 1 worker. So:

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = time_limit
solver.parameters.log_search_progress = debug
# cannot search with multiple CPUs
# solver.parameters.num_search_workers = num_cpus
# Search and print out all solutions.
solution_printer = VarArraySolutionPrinter(fixtures)
status = solver.SearchForAllSolutions(model, solution_printer)


But this is a bad idea, because it takes forever (one worker is slow)
and you get tons of solutions.

For example, with 4 teams, 2 days, 2 pools, I see 16 valid combinations

#1 0.00s num_bool:44
fixture: day 0, home 1, away 0=1
fixture: day 0, home 3, away 2=1
fixture: day 1, home 1, away 3=1
fixture: day 1, home 2, away 0=1
...
#16 0.01s num_bool:44
fixture: day 0, home 0, away 1=1
fixture: day 0, home 2, away 3=1
fixture: day 1, home 1, away 3=1
fixture: day 1, home 2, away 0=1

Notice there are super minor differences in the fixtures from one
schedule #1 to schedule #16.

4 teams, 2 pools, 3 days => 32 schedules
4 teams, 2 pools, 4 days => 128 schedules
4 teams, 2 pools, 5 days => 448 schedules
4 teams, 2 pools, 6 days => 1888 schedules
4 teams, 2 pools, 7 days => 3040 schedules

With just 8 teams, 2 pools, 4 days, I saw more than 80,000 valid
combinations float in 400 seconds before I got bored of looking
at my screen scrolling.

For your case of 32 teams, 8 pools, 10 days, there are far more than
that, I'm sure, but here you hit the CPU irritant---one worker
doesn't get to the first solution inside of 10 minutes.

Regards,
James

On Wed, Aug 14, 2019 at 02:15:56AM -0700, Frédéric Girod wrote:
> Hi Laurent,
>
> A quick question for you specifically: I tried everything to get the number
> of feasible solutions but failed to do so.
>
> The parameters log_search_progress is True (or debug in James code), I have
> used a SolutionPrinter() and solver.SearchForAllSolutions(model,
> solution_printer), but I don't get anything....
>
> Have you got another idea ?
>
>
> Le mardi 13 août 2019 18:15:07 UTC+2, Laurent Perron a écrit :
> >
> > parameters log_search_progress
> >
> > Le mar. 13 août 2019 à 09:10, Frédéric Girod <fred.fre...@gmail.com

> > <javascript:>> a écrit :

> >
> >> Moreover, I was wondering if there is a technical way to log or display
> >> the number of feasible solutions while the solver is running ?
> >>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "or-tools-discuss" group.
> >> To unsubscribe from this group and stop receiving emails from it, send an

> >> email to or-tools...@googlegroups.com <javascript:>.

> >> To view this discussion on the web visit
> >> https://groups.google.com/d/msgid/or-tools-discuss/5421d22b-e26a-4c1f-84d6-ebef73126e2d%40googlegroups.com

> >> <https://groups.google.com/d/msgid/or-tools-discuss/5421d22b-e26a-4c1f-84d6-ebef73126e2d%40googlegroups.com?utm_medium=email&utm_source=footer>
> >> .
> >>
> >
> >
> > --
> > --Laurent

> >
> >
>
> --
> You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/34dfd097-2dfe-4949-8f08-93ec7ace59de%40googlegroups.com.


--

James E. Marca