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.