Okay, so guys welcome back, this is 
discrete optimization, local search, part 
five. 
And what we're going to see today is 
sport scheduling. 
Remember, you know, when we did the first 
introductory lecture. 
I talked about scheduling, and NFL 
scheduling. 
So, today we're going to talk about some 
really hard scheduling problem, okay? 
And the key point, the reason why we want 
to do this is that we're going to talk 
about a really complex neighborhood, a 
beautiful neighborhood which was done by 
you know, some of my students and 
colleagues you know, Ares, Janis, and 
Lowell. 
And, and they really got obsessed with 
these problems, and I'll tell you some of 
the results at the end. 
So, so sport scheduling I told you at the 
beginning you know, is big business you 
know, radio and television network. 
Are willing to pay a lot of dollars and 
because a lot of the sport leagues now, 
you know, have, have, have very high 
revenue. 
And, you know, let's say in the US, we 
talk about baseball, or you know, 
basketball, football, and hockey. 
You know, the countries, you know, you 
talk about footie and soccer and other 
things. 
But in all cases, it's a big business, 
okay? 
And so, what I'm gona talk about today 
is, is called the traveling tournament 
problem TTP for short. 
And it's an abstraction of Major League 
Baseball of the United States, which was 
proposed by Kelly Easton, George 
Nemhauser, and Mike Trick. 
And so you would see, it's kind of a 
beautiful problem. 
It's very simple to state. 
It's amazingly hard, okay. 
And it basically abstracts, you know, 
major league baseball, which is more 
complicated. 
But it's essentially the essence of major 
league baseball. 
Now, why is it complicated? 
Because you'll see two facts. 
You'll see very complex feasibility 
constraints and I'm going to explain them 
to you later on. 
[SOUND] Okay, but essentially home/away 
patterns. 
The fact that teams cannot play too many 
times at home or away. 
And then it does a very complex and 
global objective function. 
You want to minimize the total distance 
which is basically travelled by these 
teams. 
And, you know, baseball is like you know, 
it's a national sport in the Unites 
States. 
These teams are flying from Boston. 
To Auckland, back to New York and so on 
and so forth, okay. 
So, essentially what you do here is you 
minimize the home, you know, you have to 
find this feasibility to, this feasible 
solution which is, which are tough and at 
the same time you have to optimize a 
complex objective function which is 
global. 
And the tension between these two things 
is what makes this problem very hard, 
okay. 
So, the input is very simple. 
You have n teams, okay. 
And you have a matrix which basically 
express the distance between the, the 
travel distance between every two teams. 
Okay, so I can index that matrix. 
Okay, which I will call d in this, in 
this lecture. 
Which basically tells me the distance for 
traveling point from, you know, team a to 
team b. 
Okay, now what I want as the result is is 
the double round-robin schedule. 
Okay, and that means that every team. 
Has to meet every other team twice. 
Once at home and once away. 
Okay, so basically, double round-robin. 
Okay, and the, the other way to think 
about it is that the season is basically 
divided in a number of weeks. 
And every, and every week, every team has 
to play against another team. 
Okay, so we have essentially two, two 
difficult, two types of contrast. 
The first one being the most difficult, 
okay. 
Which is, essentially, the home in a way, 
potter, okay. 
So you don't want to play too many games 
at home or way, okay, if you. 
The team is away all the time the fans 
can, you know, lose interest. 
If the team is playing too many games at 
home, you know, the fans are losing 
interest as well because they don't want 
to go to the stadium three days in a row, 
right? 
So, after two day, you are, you, you 
know, you get enough of eating popcorns 
and hot dogs and things like this. 
Okay, so essentially, you want 
essentially to have a limit on the number 
of successive games that you can play at 
home. 
The number of successive. 
You know, games that you play away, okay? 
So that's the first constraint. 
The second constraint is the no-repeat 
constraint. 
If you, if a plays against b, you know on 
a particular week, you don't want a 
playings against b even you know, at b 
stadiums on the next week. 
You don't want these two team to play 
each other just next, you know, just two, 
two successive week. 
You want to spread that out such that you 
know you make the schedule more 
interesting. 
So these are the two feasibility 
constraints that we will deal with and 
then the objective function is going to 
minimize the travel distance, okay? 
So every week a team is going to play 
against another team, okay? 
And it has to, sometimes it doesn't 
travel. 
Sometimes a team has to travel, and 
therefore you want to minimize this 
travel. 
And I'm going to distribute that on the, 
on, on a, on a populous schedule. 
So this is essentially, everything you 
need to know to understand this problem. 
This is essentially the schedule. 
For a TTP with six teams and obviously, 
if we have six team, seems they have to 
play against each other twice. 
We will have ten weeks. 
So, you see the ten weeks, you know, on 
the top, you see the six team over there. 
Every one of these row is going to be the 
schedule of one team. 
And I want to go with you over, you know, 
the schedule of one of the teams. 
So, you see this team one here? 
Team one is going to first play at home 
against team 6. 
And then it's going to move away and play 
at the stadium of team two. 
So, the @2 over there is basically 
telling you that team one is playing at 
the stadium of two. 
Then team one is going to fly back home, 
okay, and plays against team four. 
It's going to stay at home and play 
against team three. 
And then he's going to take this 
completely crazy road trip, okay? 
So, first moving and playing at this at 
five. 
Then moving from you know the stadium of 
five to the stadium of four playing at 
four. 
Then flying and playing against three you 
know, that's you know, again away. 
So, you have a sequence here of three 
away games. 
Then you know team one is going to fly 
back at home and play five, and then two, 
and then conclude the season by playing 
at six, okay? 
So, essentially what you see there is 
that the team is playing sometimes home 
then fly to play you know, in some of the 
stadium, fly back home. 
You know, play a sequence of the game at 
home, flying back away, can play a 
sequence of game away. 
Which basically means that in those cases 
you fly from one away stadium to another 
away stadium and so on, okay. 
Now, that, that's essentially the 
schedule of one team. 
Obviously, you can look at this thing 
from the week standpoint. 
So, the first week here, you see all the 
games. 
So, we already know that one is playing 
against six, right. 
So obviously, we also want to make sure 
that six is playing against one, rhat's 
the game, right? 
So, if one plays against six at home, we 
have to make sure that six plays away at 
one, right? 
And that's what you see in this 
particular, in this particular column. 
We also see here that team two is playing 
five, okay. 
Which basically means that team five is 
going to play @2, you know, away at two. 
And of course there is only one game 
which is at left, which is three is 
playing @4 and obviously four is playing 
at home against three, okay. 
So, this is a double Round Robin problem, 
okay. 
So, every team is going to play every 
other team twice. 
You see the schedule of one team here. 
You see one every, all the games that 
you're playing every week of the, the 
season, okay. 
Know, you have seen also the various 
constraints that I have shown you, right. 
So in this part of the case here, we see 
a sequence of three a we game, we comp at 
four. 
So, this particular, this particular 
schedule for team one is, basically, 
sunny flying all the physical 
constraints, okay. 
We never go away from and play three 
more, three games, you know, away. 
More than three games away and we never 
stay home and play more than three games 
at home. 
We also never play against a team just 
next to each other. 
You know, we play six at the beginning of 
the season and then at the end of The 
season, okay? 
So that's basically what the TTP is 
about, from a feasibility standpoint. 
Okay, so, this is one of the aspects. 
We saw the feasibility aspect. 
What we have to take into account as 
well, is the objective function. 
What you see here, is essentially the 
total distance which is traveled by team 
one. 
Okay, so when you look at the schedule, 
team one, the first, so bring it home 
again, six in the beginning then moving a 
two. 
So you see that the third travel that 
this team has to do is moving from one to 
two, okay. 
Then of usually, the team, is playing at 
home again, is four. 
So the team has to fly back home, and 
what you see there is the distance from 
two to one, we have to sum that, okay. 
So, the team is playing then at home 
against four, at home against three. 
So, nothing happens there, no travel. 
Then the team has to play, has to play at 
five. 
So, which basically means that the term, 
term that you see there is the travel 
between one, the stadium of, of team one, 
to five and that's the distance that you 
have there, okay? 
And that corresponds to the schedule. 
where the team is traveling, is traveling 
to five. 
Now from five the team is, is playing 
away after that at four. 
So you have a travel which is between 
five and four, and that's the next thing 
that you see in this particular sum, 
okay? 
So that's how you compute this objective 
function, okay? 
And this is only for the first team, but 
what you have to do is essentially 
compute that for every team. 
So you get this gigantic objective 
function. 
Summing all this travel distance for all 
the team, every time they move from home 
to away or from away stadium to another 
away stadium or away to home, okay. 
And so, we have to sum all these. 
And this is essentially the objective 
function that we are trying to optimize. 
So, to summarize, we have these 
feasibility constraints on the schedule, 
then we have this basic objective 
function that we have to satisfy. 
And we have to solve this problem. 
So, now you can get a feel why this is so 
complex, right? 
So, you have this crazy you know, 
visibility constraints and we have this 
gigantic objective function, okay? 
Now you can solve this. 
You can try to solve this with constraint 
programming. 
It's a good exercise. 
So, try it but what we're going to do now 
is trying to see how we can solve this 
with local search. 
[INAUDIBLE] And one of the things that I 
want you to think about is what kind of 
neighborhood should we use? 
Okay, so it's kind of crazy, right? 
So, you can't just pick up a particular 
slot there and change the value. 
Or it's kind of funny, you, you know, 
swapping these two things here doesn't 
mean very much because there are a lot of 
complications here, right? 
So when we are trying to design this 
neighborhood, we need a little bit to 
think about what this whole thing means, 
right? 
And so what I'm going to show is actually 
a complex neighborhood, which has 
multiple moves, okay? 
Not a single move but many moves and 
that's what makes this problem really 
interesting. 
So, I'm going to show you. 
You know, six essentially five types of 
move. 
So you can swap homes, swap rounds, swap 
teams And then swap partial rounds and 
swap partial teams. 
And I'm going to go over every one of 
them to show you the beautiful 
neighborhood that we are, kind of, that 
we are defining for this problem, okay. 
The first one is the easiest one, right? 
So, what we want to do is that we see 
here that team two is playing at four and 
obviously team four is playing against 
two. 
And does, does, you know, inside week 
five of the schedule, and in the week 
eight of the schedule, this team meets 
again. 
We know that they have to meet twice once 
at home, once away. 
Okay? 
For one of the teams, for both of the 
team actually. 
And so the during week, week eight what 
we know is that team two is playing 
against for away and obviously, team four 
is playing two at home, okay? 
And so this particular swap. 
Means that what this particular 
neighborhood means that we want to change 
essentially the home/away pattern, okay? 
So, instead at the beginning of the 
season of having team four, team two 
playing at four, we want to have team two 
playing at home against team four, right? 
And so, we are basically changing these 
things and we get this beautiful schedule 
now where you know team, team two plays 
at home first and then away against team 
four, okay? 
So, that's the basic idea. 
right, yeah. 
So, so that's a very simple move because 
it's essentially very local, right. 
So, you only move, you only basically 
affect these particular four slots, okay. 
So, we're going to do a much more radical 
move, which is swap rounds here, okay? 
So, you look at the particular week and 
you look at another week, okay? 
So, in a, in, in this particular case it 
doesn't really matter when. 
So, you can to it, take these two things 
and swap them entirely, okay? 
So, you may evaluate some of the 
constraints or you may change, now the 
objective function, but you can swap them 
and still have a round robin schedule, 
okay. 
So you still preserve the round robin 
schedule, and that's good, okay? 
So in a sense, you know, when you think 
about this neighborhood, the moves are 
always going to keep, you know, the round 
robin schedule satisfied, but all, all 
the time, okay? 
So what we might violate are the 
home/away pattern. 
And obviously we, we change the 
evaluation function. 
Because every time we swap two rounds 
like this the, the traveling patterns may 
change as well, okay? 
So, this is a very simple move as well. 
We take one particular round, we take 
another round, we just swap them, okay? 
Now, the next thing, the next move is 
actually pretty interesting. 
We looked at team two, we look, we look 
at team five and we say well you know, 
why don't we just swap the schedule of 
this team. 
It's a radical move, right? 
So, instead of having two you know plate 
schedule, we're going to change the 
schedule and, and use the schedule of 
six, okay? 
Or five in this particular case and four 
the same thing for five we use the 
schedule of two, okay? 
So, we basically look at the schedule of 
one team. 
The scaling of it on a team and then we 
swap them okay. 
Now there's a little bit you have you 
can't stop the whole thing completely 
because 2 and 5 are going to play shorter 
so keep these games okay. 
So in this particular case, it's very 
convenient because the game between the 
two of them. 
Is the first day of the, the first week 
of the season and the last, the la, the 
first week of the, the first week of the 
season and the last week of the season 
so, you can essentially you have these 
big blocks that you can just swap, okay? 
But the [INAUDIBLE] you know, the, the, 
the game between these two team could be 
the middle so you would swap everything 
else, okay? 
Now when we do that, okay? 
So, if we apply this thing, okay? 
So, we get this beautiful schedule at the 
bottom, but now there is something 
actually very interesting happening, 
right? 
So, you see two here which is playing at 
three, right? 
And, obviously what we would like to and 
before, okay? 
So, two was playing at one. 
Okay, so, when you look at this new 
schedule we also see that one, you know, 
is still playing @2. 
So, we have one, we have two playing @3 
but we have one playing @2. 
And that's not a game, right. 
So what ha, what is happening here is 
that we switch the games of these two 
team. 
But there were the opponent of these two 
teams and those have to be fixed as well. 
So, you have a bunch of other entries in 
this stable. 
That needs to be fixed. 
We have to make sure that when we swap 
the schedules, we are also swapping the 
opponents of these two teams. 
The teams that they were playing against. 
Okay. 
So, in a sense, that's what you do here. 
You fix all these guys. 
You swap them. 
And you get this beautiful table. 
Where essentially you swap these two, you 
know, these, these, these two teams. 
The schedule of these two teams. 
And you fix. 
And these are the blue entries there. 
Okay, you fix all the other opponent. 
So, it's kind of a complex move in the 
sense because you not only swap these 
two, the schedule of these two teams. 
But you have also to adjust the value of 
the opponent. 
Okay, so what [SOUND] you can see here is 
that it affects a huge part of the 
accurate schedule, right. 
So, so it's a, it's a big move. 
Okay, so one of the things that, that, 
that we're going to do now is look at 
this move especially the, the swap rounds 
and the swap teams, okay? 
And try to make them a little bit more 
fine grain, okay? 
Such that, we can, we can do you know, 
smaller move instead of effecting the 
entire well, really large part of the 
schedule. 
And this is what you have seen here, 
okay? 
So, we want to swap you know a, a round 
but not the entire round. 
We want to swap a [INAUDIBLE] subset of 
that round, okay. 
For instance, you know, some of the 
constraints we need evaluated for these 
things, okay, are the distances very bad 
for these two things. 
And we just want to swap these two, 
right? 
So we don't want to swap the rest of the 
round, okay? 
So here we say okay, so I want to swap, 
you know, the fact that team two is 
playing at one in week two, okay? 
And the fact that it's playing at, at six 
in week nine. 
So I want to really to swap these two 
things. 
Because that would give me, let's say, a 
distance which is much better, okay? 
So I want to do that, okay? 
And so, if I do that, what I, what's 
happening? 
If I actually swap these two things, 
okay, so I would have essentially, you 
know, the value here, which is one. 
I would have it on this particular week, 
on the week nine. 
But of course on week nine I'm already, I 
already have a game with one, right? 
So, we have to fix that as well, okay? 
So, we have to make sure that I'm not 
only swapping these two guys, but I'm 
constrained also to swap these two guys 
otherwise I would be having two ones on 
this particular week and that's not good, 
okay? 
So, one would be playing at home and away 
in this particular case. 
So, I have to swap that and obviously I'm 
changing the opponent of these guys so, I 
actually have to fix those guys as well 
as swap those guys as well. 
So the way to view this is that, in a 
sense, if I want to swap one and six, I 
have to look at the connected component 
between these things. 
I'm looking at how they are connecting 
with each other, in terms of the teams 
that they are already playing. 
And what you see here is, essentially, 
this round can be decomposed in several 
component. 
One of them is involving team one, two, 
six, and four. 
And the other one is involving team five 
and three. 
So what I'm basically swapping are all 
the games involving, you know, six, one, 
two, and four. 
And I"m basically keeping the games 
between five and three, this particular 
case, constant. 
And that's what you see here, okay? 
So, you see that team three and team five 
are not effected by this move, because 
they are not connected to six and one 
which were the two variables that I 
wanted to keep, okay? 
So, this is, this is this move. 
So it's a more interesting move, right? 
So, it's [UNKNOWN] it's only you know, 
basically swap partial parts of these 
rounds and so it's more flexible. 
You can actually select a little bit more 
carefully, you know, how, how you effect 
the schedule, okay? 
Now the last move is actually the most 
beautiful one. 
This is, this is swap partial team, okay? 
And once again what you see here is that 
I want to swap some part of the schedule 
between one and six, okay? 
So, I want to say oh, between team two 
and four, sorry. 
And team two on week nine is playing 
against one. 
And team four is playing against six. 
And what I want is that I want you know, 
I, I really want team one to play against 
six at that part and team one and team 
four to play against one. 
So, I want to swap these two guys. 
But if I do that, what's going to happen? 
So,you know that I, [UNKNOWN] you know 
you see six over there and you see a you 
know, one over there. 
So, if I put the six on top here. 
You know, you, you can already see that 
six is already on week four, you know I 
have already a six on week four. 
So, which basically means that, I would 
be playing at six twice, okay? 
So in a sense if I do that, I know that I 
will have to change this guy and also the 
same thing for the, for team four. 
You know I would have, I would have 
playing at once, twice. 
So, I need to also take care of this move 
and swap them between the two team, okay? 
So, that's what I'm going to do. 
I'm going to say, okay, I have to swap 
these guys as well. 
But now you see that I am introducing, 
you know five over there. 
I am touching to team five over there and 
also touching teams one, teams three over 
there, okay. 
So, that means that once again, you know, 
I, I have two, I have two teams that are 
affected by this thing. 
So, I will have to deal with those guys 
as well. 
And that's what you see that I'm doing 
here. 
So, I have more swaps to do, okay. 
And so I keep doing this and now at this 
point this is isolated. 
I have done all the swap and restored the 
fact that every team is playing against 
you know, every other team twice, once at 
home and once away. 
So, in a sense by propagating the 
information, I'm basically making sure 
that I'm restoring a round robin 
schedule, okay? 
Now, we have the same difficulty that 
I've shown you when we did the complete 
You know swap teams, which basically 
means that, I still have to fix the 
opponents of these teams, okay? 
So, all these cells here are not correct, 
but I'm going to fix them in the same way 
we fixed them before. 
And now I get this beautiful thing here, 
which is the final schedule. 
So, what is interesting here is that when 
you look at this move, this move is much, 
is much less drastic than, you know, just 
swapping The, the, the, the entire 
schedule of the two teams. 
I'm only swapping some part of the 
schedule and some part, of course, of the 
schedule of the opponents of this team, 
from these particular weeks, okay. 
And so that gives me a final grade, to 
actually modify the schedule. 
And this is really important when you try 
to solve these problems in practice and 
find very high quality solutions. 
Okay, so now I just want to tell you that 
this neighborhood is actually amazing, 
okay. 
So these are results of the TTP over 
time. 
I told you this is a very interesting and 
very difficult problem. 
So, people have been competing in trying 
to beat each other on this problem. 
And what you see, actually you probably 
cant see, but that's not a problem. 
So you see essentially people, you know, 
starting trying to beat each other on 
this particular, on this particular 
problem with starting from 2001. 
And on these three problems, which are 
the larger initial instance, 12 team, 14 
team and 16 team, you see that the last 
solution that was produced was produced 
by an algorithm using the neighborhood 
that I've shown you. 
And it's not been beaten for, let's say, 
five or six years at this point, okay. 
So, it's really a very nice neighborhood. 
Of course you have to use all the 
techniques that I will talk about, you 
know, in two or three lectures. 
But essentially this neighborhood is 
really powerful and really a nice way of 
actually finding very high quality 
solution. 
For these problems the solution which 
have been produced by this neighborhood 
have never be, beaten so far, okay? 
So, I'll, so at this point what we have 
seen is a lot of different ways of 
actually defining neighborhoods. 
Very simple one, tiny one where we just 
modify the value of a variable. 
Swaps and then we see some really 
complicated moves like the one we saw 
today. 
Where we effect large part of the 
schedules but not completely large part 
but also something which are 
intermediary. 
And this is the key for solving some 
particular problems. 
So, what we're going to see in the next 
couple of lecture is how we can actually 
escape local minimum, okay? 
Local minimum, because so far the only 
thing that we have done is essentially 
applying these move greedily. 
But if you want to find really high 
quality solution, you will have to be a 
little bit more careful. 
Okay, see you next time.