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.