0:00

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.

Â