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.