1 00:00:00,240 --> 00:00:04,270 Okay, so guys welcome back, this is discrete optimization, local search, part 2 00:00:04,270 --> 00:00:06,850 five. And what we're going to see today is 3 00:00:06,850 --> 00:00:09,640 sport scheduling. Remember, you know, when we did the first 4 00:00:09,640 --> 00:00:12,890 introductory lecture. I talked about scheduling, and NFL 5 00:00:12,890 --> 00:00:15,640 scheduling. So, today we're going to talk about some 6 00:00:15,640 --> 00:00:19,610 really hard scheduling problem, okay? And the key point, the reason why we want 7 00:00:19,610 --> 00:00:23,310 to do this is that we're going to talk about a really complex neighborhood, a 8 00:00:23,310 --> 00:00:28,290 beautiful neighborhood which was done by you know, some of my students and 9 00:00:28,290 --> 00:00:31,770 colleagues you know, Ares, Janis, and Lowell. 10 00:00:31,770 --> 00:00:35,480 And, and they really got obsessed with these problems, and I'll tell you some of 11 00:00:35,480 --> 00:00:39,100 the results at the end. So, so sport scheduling I told you at the 12 00:00:39,100 --> 00:00:42,540 beginning you know, is big business you know, radio and television network. 13 00:00:42,540 --> 00:00:47,100 Are willing to pay a lot of dollars and because a lot of the sport leagues now, 14 00:00:47,100 --> 00:00:49,430 you know, have, have, have very high revenue. 15 00:00:49,430 --> 00:00:52,160 And, you know, let's say in the US, we talk about baseball, or you know, 16 00:00:52,160 --> 00:00:55,790 basketball, football, and hockey. You know, the countries, you know, you 17 00:00:55,790 --> 00:00:58,870 talk about footie and soccer and other things. 18 00:00:58,870 --> 00:01:01,840 But in all cases, it's a big business, okay? 19 00:01:01,840 --> 00:01:06,010 And so, what I'm gona talk about today is, is called the traveling tournament 20 00:01:06,010 --> 00:01:10,240 problem TTP for short. And it's an abstraction of Major League 21 00:01:10,240 --> 00:01:13,755 Baseball of the United States, which was proposed by Kelly Easton, George 22 00:01:13,755 --> 00:01:17,570 Nemhauser, and Mike Trick. And so you would see, it's kind of a 23 00:01:17,570 --> 00:01:20,100 beautiful problem. It's very simple to state. 24 00:01:20,100 --> 00:01:24,310 It's amazingly hard, okay. And it basically abstracts, you know, 25 00:01:24,310 --> 00:01:26,370 major league baseball, which is more complicated. 26 00:01:26,370 --> 00:01:29,490 But it's essentially the essence of major league baseball. 27 00:01:29,490 --> 00:01:31,860 Now, why is it complicated? Because you'll see two facts. 28 00:01:31,860 --> 00:01:35,230 You'll see very complex feasibility constraints and I'm going to explain them 29 00:01:35,230 --> 00:01:38,290 to you later on. [SOUND] Okay, but essentially home/away 30 00:01:38,290 --> 00:01:40,510 patterns. The fact that teams cannot play too many 31 00:01:40,510 --> 00:01:44,149 times at home or away. And then it does a very complex and 32 00:01:44,149 --> 00:01:48,260 global objective function. You want to minimize the total distance 33 00:01:48,260 --> 00:01:50,380 which is basically travelled by these teams. 34 00:01:50,380 --> 00:01:53,520 And, you know, baseball is like you know, it's a national sport in the Unites 35 00:01:53,520 --> 00:01:55,565 States. These teams are flying from Boston. 36 00:01:55,565 --> 00:01:59,000 To Auckland, back to New York and so on and so forth, okay. 37 00:01:59,000 --> 00:02:02,390 So, essentially what you do here is you minimize the home, you know, you have to 38 00:02:02,390 --> 00:02:06,380 find this feasibility to, this feasible solution which is, which are tough and at 39 00:02:06,380 --> 00:02:09,960 the same time you have to optimize a complex objective function which is 40 00:02:09,960 --> 00:02:12,510 global. And the tension between these two things 41 00:02:12,510 --> 00:02:14,530 is what makes this problem very hard, okay. 42 00:02:14,530 --> 00:02:18,150 So, the input is very simple. You have n teams, okay. 43 00:02:18,150 --> 00:02:22,100 And you have a matrix which basically express the distance between the, the 44 00:02:22,100 --> 00:02:26,540 travel distance between every two teams. Okay, so I can index that matrix. 45 00:02:26,540 --> 00:02:29,490 Okay, which I will call d in this, in this lecture. 46 00:02:29,490 --> 00:02:33,220 Which basically tells me the distance for traveling point from, you know, team a to 47 00:02:33,220 --> 00:02:38,060 team b. Okay, now what I want as the result is is 48 00:02:38,060 --> 00:02:42,510 the double round-robin schedule. Okay, and that means that every team. 49 00:02:42,510 --> 00:02:47,330 Has to meet every other team twice. Once at home and once away. 50 00:02:47,330 --> 00:02:52,440 Okay, so basically, double round-robin. Okay, and the, the other way to think 51 00:02:52,440 --> 00:02:57,280 about it is that the season is basically divided in a number of weeks. 52 00:02:57,280 --> 00:03:00,090 And every, and every week, every team has to play against another team. 53 00:03:00,090 --> 00:03:05,120 Okay, so we have essentially two, two difficult, two types of contrast. 54 00:03:05,120 --> 00:03:07,360 The first one being the most difficult, okay. 55 00:03:07,360 --> 00:03:09,880 Which is, essentially, the home in a way, potter, okay. 56 00:03:09,880 --> 00:03:15,200 So you don't want to play too many games at home or way, okay, if you. 57 00:03:15,200 --> 00:03:18,740 The team is away all the time the fans can, you know, lose interest. 58 00:03:18,740 --> 00:03:22,240 If the team is playing too many games at home, you know, the fans are losing 59 00:03:22,240 --> 00:03:25,230 interest as well because they don't want to go to the stadium three days in a row, 60 00:03:25,230 --> 00:03:27,750 right? So, after two day, you are, you, you 61 00:03:27,750 --> 00:03:31,520 know, you get enough of eating popcorns and hot dogs and things like this. 62 00:03:31,520 --> 00:03:35,170 Okay, so essentially, you want essentially to have a limit on the number 63 00:03:35,170 --> 00:03:37,510 of successive games that you can play at home. 64 00:03:37,510 --> 00:03:41,610 The number of successive. You know, games that you play away, okay? 65 00:03:41,610 --> 00:03:44,470 So that's the first constraint. The second constraint is the no-repeat 66 00:03:44,470 --> 00:03:49,670 constraint. If you, if a plays against b, you know on 67 00:03:49,670 --> 00:03:53,970 a particular week, you don't want a playings against b even you know, at b 68 00:03:53,970 --> 00:03:56,620 stadiums on the next week. You don't want these two team to play 69 00:03:56,620 --> 00:04:00,160 each other just next, you know, just two, two successive week. 70 00:04:00,160 --> 00:04:05,120 You want to spread that out such that you know you make the schedule more 71 00:04:05,120 --> 00:04:07,050 interesting. So these are the two feasibility 72 00:04:07,050 --> 00:04:10,120 constraints that we will deal with and then the objective function is going to 73 00:04:10,120 --> 00:04:13,550 minimize the travel distance, okay? So every week a team is going to play 74 00:04:13,550 --> 00:04:16,780 against another team, okay? And it has to, sometimes it doesn't 75 00:04:16,780 --> 00:04:19,080 travel. Sometimes a team has to travel, and 76 00:04:19,080 --> 00:04:21,030 therefore you want to minimize this travel. 77 00:04:21,030 --> 00:04:24,040 And I'm going to distribute that on the, on, on a, on a populous schedule. 78 00:04:24,040 --> 00:04:28,330 So this is essentially, everything you need to know to understand this problem. 79 00:04:28,330 --> 00:04:36,090 This is essentially the schedule. For a TTP with six teams and obviously, 80 00:04:36,090 --> 00:04:39,150 if we have six team, seems they have to play against each other twice. 81 00:04:39,150 --> 00:04:42,510 We will have ten weeks. So, you see the ten weeks, you know, on 82 00:04:42,510 --> 00:04:47,260 the top, you see the six team over there. Every one of these row is going to be the 83 00:04:47,260 --> 00:04:51,220 schedule of one team. And I want to go with you over, you know, 84 00:04:51,220 --> 00:04:53,480 the schedule of one of the teams. So, you see this team one here? 85 00:04:53,480 --> 00:04:56,810 Team one is going to first play at home against team 6. 86 00:04:56,810 --> 00:05:00,620 And then it's going to move away and play at the stadium of team two. 87 00:05:00,620 --> 00:05:04,940 So, the @2 over there is basically telling you that team one is playing at 88 00:05:04,940 --> 00:05:09,020 the stadium of two. Then team one is going to fly back home, 89 00:05:09,020 --> 00:05:12,910 okay, and plays against team four. It's going to stay at home and play 90 00:05:12,910 --> 00:05:15,620 against team three. And then he's going to take this 91 00:05:15,620 --> 00:05:20,780 completely crazy road trip, okay? So, first moving and playing at this at 92 00:05:20,780 --> 00:05:23,760 five. Then moving from you know the stadium of 93 00:05:23,760 --> 00:05:26,630 five to the stadium of four playing at four. 94 00:05:26,630 --> 00:05:30,830 Then flying and playing against three you know, that's you know, again away. 95 00:05:30,830 --> 00:05:34,120 So, you have a sequence here of three away games. 96 00:05:34,120 --> 00:05:37,870 Then you know team one is going to fly back at home and play five, and then two, 97 00:05:37,870 --> 00:05:42,710 and then conclude the season by playing at six, okay? 98 00:05:42,710 --> 00:05:46,460 So, essentially what you see there is that the team is playing sometimes home 99 00:05:46,460 --> 00:05:50,060 then fly to play you know, in some of the stadium, fly back home. 100 00:05:50,060 --> 00:05:52,860 You know, play a sequence of the game at home, flying back away, can play a 101 00:05:52,860 --> 00:05:55,930 sequence of game away. Which basically means that in those cases 102 00:05:55,930 --> 00:06:00,820 you fly from one away stadium to another away stadium and so on, okay. 103 00:06:00,820 --> 00:06:02,800 Now, that, that's essentially the schedule of one team. 104 00:06:02,800 --> 00:06:06,310 Obviously, you can look at this thing from the week standpoint. 105 00:06:06,310 --> 00:06:08,680 So, the first week here, you see all the games. 106 00:06:08,680 --> 00:06:12,050 So, we already know that one is playing against six, right. 107 00:06:12,050 --> 00:06:15,820 So obviously, we also want to make sure that six is playing against one, rhat's 108 00:06:15,820 --> 00:06:18,690 the game, right? So, if one plays against six at home, we 109 00:06:18,690 --> 00:06:22,400 have to make sure that six plays away at one, right? 110 00:06:22,400 --> 00:06:26,040 And that's what you see in this particular, in this particular column. 111 00:06:26,040 --> 00:06:29,030 We also see here that team two is playing five, okay. 112 00:06:29,030 --> 00:06:33,859 Which basically means that team five is going to play @2, you know, away at two. 113 00:06:33,859 --> 00:06:37,060 And of course there is only one game which is at left, which is three is 114 00:06:37,060 --> 00:06:41,250 playing @4 and obviously four is playing at home against three, okay. 115 00:06:41,250 --> 00:06:43,940 So, this is a double Round Robin problem, okay. 116 00:06:43,940 --> 00:06:46,670 So, every team is going to play every other team twice. 117 00:06:46,670 --> 00:06:51,010 You see the schedule of one team here. You see one every, all the games that 118 00:06:51,010 --> 00:06:53,790 you're playing every week of the, the season, okay. 119 00:06:53,790 --> 00:06:57,390 Know, you have seen also the various constraints that I have shown you, right. 120 00:06:57,390 --> 00:07:01,600 So in this part of the case here, we see a sequence of three a we game, we comp at 121 00:07:01,600 --> 00:07:04,300 four. So, this particular, this particular 122 00:07:04,300 --> 00:07:08,170 schedule for team one is, basically, sunny flying all the physical 123 00:07:08,170 --> 00:07:11,300 constraints, okay. We never go away from and play three 124 00:07:11,300 --> 00:07:15,010 more, three games, you know, away. More than three games away and we never 125 00:07:15,010 --> 00:07:18,410 stay home and play more than three games at home. 126 00:07:18,410 --> 00:07:21,060 We also never play against a team just next to each other. 127 00:07:21,060 --> 00:07:24,161 You know, we play six at the beginning of the season and then at the end of The 128 00:07:24,161 --> 00:07:27,200 season, okay? So that's basically what the TTP is 129 00:07:27,200 --> 00:07:32,070 about, from a feasibility standpoint. Okay, so, this is one of the aspects. 130 00:07:32,070 --> 00:07:35,460 We saw the feasibility aspect. What we have to take into account as 131 00:07:35,460 --> 00:07:38,920 well, is the objective function. What you see here, is essentially the 132 00:07:38,920 --> 00:07:41,275 total distance which is traveled by team one. 133 00:07:41,275 --> 00:07:45,810 Okay, so when you look at the schedule, team one, the first, so bring it home 134 00:07:45,810 --> 00:07:47,680 again, six in the beginning then moving a two. 135 00:07:47,680 --> 00:07:51,990 So you see that the third travel that this team has to do is moving from one to 136 00:07:51,990 --> 00:07:55,390 two, okay. Then of usually, the team, is playing at 137 00:07:55,390 --> 00:07:58,350 home again, is four. So the team has to fly back home, and 138 00:07:58,350 --> 00:08:03,040 what you see there is the distance from two to one, we have to sum that, okay. 139 00:08:03,040 --> 00:08:06,930 So, the team is playing then at home against four, at home against three. 140 00:08:06,930 --> 00:08:11,900 So, nothing happens there, no travel. Then the team has to play, has to play at 141 00:08:11,900 --> 00:08:13,850 five. So, which basically means that the term, 142 00:08:13,850 --> 00:08:18,700 term that you see there is the travel between one, the stadium of, of team one, 143 00:08:18,700 --> 00:08:21,430 to five and that's the distance that you have there, okay? 144 00:08:21,430 --> 00:08:26,500 And that corresponds to the schedule. where the team is traveling, is traveling 145 00:08:26,500 --> 00:08:30,040 to five. Now from five the team is, is playing 146 00:08:30,040 --> 00:08:33,780 away after that at four. So you have a travel which is between 147 00:08:33,780 --> 00:08:38,400 five and four, and that's the next thing that you see in this particular sum, 148 00:08:38,400 --> 00:08:40,860 okay? So that's how you compute this objective 149 00:08:40,860 --> 00:08:44,040 function, okay? And this is only for the first team, but 150 00:08:44,040 --> 00:08:46,820 what you have to do is essentially compute that for every team. 151 00:08:46,820 --> 00:08:49,790 So you get this gigantic objective function. 152 00:08:49,790 --> 00:08:53,540 Summing all this travel distance for all the team, every time they move from home 153 00:08:53,540 --> 00:08:59,080 to away or from away stadium to another away stadium or away to home, okay. 154 00:08:59,080 --> 00:09:02,420 And so, we have to sum all these. And this is essentially the objective 155 00:09:02,420 --> 00:09:05,600 function that we are trying to optimize. So, to summarize, we have these 156 00:09:05,600 --> 00:09:08,920 feasibility constraints on the schedule, then we have this basic objective 157 00:09:08,920 --> 00:09:11,700 function that we have to satisfy. And we have to solve this problem. 158 00:09:11,700 --> 00:09:15,400 So, now you can get a feel why this is so complex, right? 159 00:09:15,400 --> 00:09:18,710 So, you have this crazy you know, visibility constraints and we have this 160 00:09:18,710 --> 00:09:22,090 gigantic objective function, okay? Now you can solve this. 161 00:09:22,090 --> 00:09:23,950 You can try to solve this with constraint programming. 162 00:09:23,950 --> 00:09:28,370 It's a good exercise. So, try it but what we're going to do now 163 00:09:28,370 --> 00:09:31,230 is trying to see how we can solve this with local search. 164 00:09:31,230 --> 00:09:34,780 [INAUDIBLE] And one of the things that I want you to think about is what kind of 165 00:09:34,780 --> 00:09:38,100 neighborhood should we use? Okay, so it's kind of crazy, right? 166 00:09:38,100 --> 00:09:41,940 So, you can't just pick up a particular slot there and change the value. 167 00:09:41,940 --> 00:09:45,560 Or it's kind of funny, you, you know, swapping these two things here doesn't 168 00:09:45,560 --> 00:09:48,950 mean very much because there are a lot of complications here, right? 169 00:09:48,950 --> 00:09:52,540 So when we are trying to design this neighborhood, we need a little bit to 170 00:09:52,540 --> 00:09:55,590 think about what this whole thing means, right? 171 00:09:55,590 --> 00:09:58,300 And so what I'm going to show is actually a complex neighborhood, which has 172 00:09:58,300 --> 00:10:02,120 multiple moves, okay? Not a single move but many moves and 173 00:10:02,120 --> 00:10:03,820 that's what makes this problem really interesting. 174 00:10:03,820 --> 00:10:07,710 So, I'm going to show you. You know, six essentially five types of 175 00:10:07,710 --> 00:10:11,480 move. So you can swap homes, swap rounds, swap 176 00:10:11,480 --> 00:10:15,989 teams And then swap partial rounds and swap partial teams. 177 00:10:15,989 --> 00:10:19,220 And I'm going to go over every one of them to show you the beautiful 178 00:10:19,220 --> 00:10:22,570 neighborhood that we are, kind of, that we are defining for this problem, okay. 179 00:10:22,570 --> 00:10:27,510 The first one is the easiest one, right? So, what we want to do is that we see 180 00:10:27,510 --> 00:10:31,660 here that team two is playing at four and obviously team four is playing against 181 00:10:31,660 --> 00:10:34,930 two. And does, does, you know, inside week 182 00:10:34,930 --> 00:10:38,820 five of the schedule, and in the week eight of the schedule, this team meets 183 00:10:38,820 --> 00:10:40,760 again. We know that they have to meet twice once 184 00:10:40,760 --> 00:10:42,250 at home, once away. Okay? 185 00:10:42,250 --> 00:10:45,260 For one of the teams, for both of the team actually. 186 00:10:45,260 --> 00:10:50,686 And so the during week, week eight what we know is that team two is playing 187 00:10:50,686 --> 00:10:55,540 against for away and obviously, team four is playing two at home, okay? 188 00:10:55,540 --> 00:10:59,580 And so this particular swap. Means that what this particular 189 00:10:59,580 --> 00:11:03,720 neighborhood means that we want to change essentially the home/away pattern, okay? 190 00:11:03,720 --> 00:11:08,300 So, instead at the beginning of the season of having team four, team two 191 00:11:08,300 --> 00:11:13,880 playing at four, we want to have team two playing at home against team four, right? 192 00:11:13,880 --> 00:11:17,490 And so, we are basically changing these things and we get this beautiful schedule 193 00:11:17,490 --> 00:11:21,990 now where you know team, team two plays at home first and then away against team 194 00:11:21,990 --> 00:11:24,130 four, okay? So, that's the basic idea. 195 00:11:24,130 --> 00:11:28,222 right, yeah. So, so that's a very simple move because 196 00:11:28,222 --> 00:11:33,709 it's essentially very local, right. So, you only move, you only basically 197 00:11:33,709 --> 00:11:38,390 affect these particular four slots, okay. So, we're going to do a much more radical 198 00:11:38,390 --> 00:11:42,110 move, which is swap rounds here, okay? So, you look at the particular week and 199 00:11:42,110 --> 00:11:46,420 you look at another week, okay? So, in a, in, in this particular case it 200 00:11:46,420 --> 00:11:49,440 doesn't really matter when. So, you can to it, take these two things 201 00:11:49,440 --> 00:11:53,000 and swap them entirely, okay? So, you may evaluate some of the 202 00:11:53,000 --> 00:11:57,550 constraints or you may change, now the objective function, but you can swap them 203 00:11:57,550 --> 00:11:59,660 and still have a round robin schedule, okay. 204 00:11:59,660 --> 00:12:03,170 So you still preserve the round robin schedule, and that's good, okay? 205 00:12:03,170 --> 00:12:06,740 So in a sense, you know, when you think about this neighborhood, the moves are 206 00:12:06,740 --> 00:12:11,830 always going to keep, you know, the round robin schedule satisfied, but all, all 207 00:12:11,830 --> 00:12:14,745 the time, okay? So what we might violate are the 208 00:12:14,745 --> 00:12:16,740 home/away pattern. And obviously we, we change the 209 00:12:16,740 --> 00:12:19,400 evaluation function. Because every time we swap two rounds 210 00:12:19,400 --> 00:12:22,750 like this the, the traveling patterns may change as well, okay? 211 00:12:22,750 --> 00:12:27,000 So, this is a very simple move as well. We take one particular round, we take 212 00:12:27,000 --> 00:12:30,882 another round, we just swap them, okay? Now, the next thing, the next move is 213 00:12:30,882 --> 00:12:34,770 actually pretty interesting. We looked at team two, we look, we look 214 00:12:34,770 --> 00:12:39,162 at team five and we say well you know, why don't we just swap the schedule of 215 00:12:39,162 --> 00:12:41,440 this team. It's a radical move, right? 216 00:12:41,440 --> 00:12:45,120 So, instead of having two you know plate schedule, we're going to change the 217 00:12:45,120 --> 00:12:48,780 schedule and, and use the schedule of six, okay? 218 00:12:48,780 --> 00:12:52,440 Or five in this particular case and four the same thing for five we use the 219 00:12:52,440 --> 00:12:55,060 schedule of two, okay? So, we basically look at the schedule of 220 00:12:55,060 --> 00:12:57,690 one team. The scaling of it on a team and then we 221 00:12:57,690 --> 00:13:01,740 swap them okay. Now there's a little bit you have you 222 00:13:01,740 --> 00:13:06,100 can't stop the whole thing completely because 2 and 5 are going to play shorter 223 00:13:06,100 --> 00:13:09,325 so keep these games okay. So in this particular case, it's very 224 00:13:09,325 --> 00:13:11,720 convenient because the game between the two of them. 225 00:13:11,720 --> 00:13:15,440 Is the first day of the, the first week of the season and the last, the la, the 226 00:13:15,440 --> 00:13:18,790 first week of the, the first week of the season and the last week of the season 227 00:13:18,790 --> 00:13:22,660 so, you can essentially you have these big blocks that you can just swap, okay? 228 00:13:22,660 --> 00:13:25,380 But the [INAUDIBLE] you know, the, the, the game between these two team could be 229 00:13:25,380 --> 00:13:28,180 the middle so you would swap everything else, okay? 230 00:13:28,180 --> 00:13:31,490 Now when we do that, okay? So, if we apply this thing, okay? 231 00:13:31,490 --> 00:13:35,710 So, we get this beautiful schedule at the bottom, but now there is something 232 00:13:35,710 --> 00:13:37,890 actually very interesting happening, right? 233 00:13:37,890 --> 00:13:44,490 So, you see two here which is playing at three, right? 234 00:13:44,490 --> 00:13:48,150 And, obviously what we would like to and before, okay? 235 00:13:48,150 --> 00:13:52,450 So, two was playing at one. Okay, so, when you look at this new 236 00:13:52,450 --> 00:13:56,630 schedule we also see that one, you know, is still playing @2. 237 00:13:56,630 --> 00:14:00,380 So, we have one, we have two playing @3 but we have one playing @2. 238 00:14:00,380 --> 00:14:03,750 And that's not a game, right. So what ha, what is happening here is 239 00:14:03,750 --> 00:14:05,820 that we switch the games of these two team. 240 00:14:05,820 --> 00:14:10,300 But there were the opponent of these two teams and those have to be fixed as well. 241 00:14:10,300 --> 00:14:13,300 So, you have a bunch of other entries in this stable. 242 00:14:13,300 --> 00:14:15,990 That needs to be fixed. We have to make sure that when we swap 243 00:14:15,990 --> 00:14:20,870 the schedules, we are also swapping the opponents of these two teams. 244 00:14:20,870 --> 00:14:23,580 The teams that they were playing against. Okay. 245 00:14:23,580 --> 00:14:26,270 So, in a sense, that's what you do here. You fix all these guys. 246 00:14:26,270 --> 00:14:28,960 You swap them. And you get this beautiful table. 247 00:14:28,960 --> 00:14:33,690 Where essentially you swap these two, you know, these, these, these two teams. 248 00:14:33,690 --> 00:14:36,120 The schedule of these two teams. And you fix. 249 00:14:36,120 --> 00:14:40,360 And these are the blue entries there. Okay, you fix all the other opponent. 250 00:14:40,360 --> 00:14:44,420 So, it's kind of a complex move in the sense because you not only swap these 251 00:14:44,420 --> 00:14:48,280 two, the schedule of these two teams. But you have also to adjust the value of 252 00:14:48,280 --> 00:14:51,040 the opponent. Okay, so what [SOUND] you can see here is 253 00:14:51,040 --> 00:14:55,360 that it affects a huge part of the accurate schedule, right. 254 00:14:55,360 --> 00:15:00,610 So, so it's a, it's a big move. Okay, so one of the things that, that, 255 00:15:00,610 --> 00:15:04,630 that we're going to do now is look at this move especially the, the swap rounds 256 00:15:04,630 --> 00:15:08,900 and the swap teams, okay? And try to make them a little bit more 257 00:15:08,900 --> 00:15:12,440 fine grain, okay? Such that, we can, we can do you know, 258 00:15:12,440 --> 00:15:16,260 smaller move instead of effecting the entire well, really large part of the 259 00:15:16,260 --> 00:15:18,430 schedule. And this is what you have seen here, 260 00:15:18,430 --> 00:15:21,780 okay? So, we want to swap you know a, a round 261 00:15:21,780 --> 00:15:25,409 but not the entire round. We want to swap a [INAUDIBLE] subset of 262 00:15:25,409 --> 00:15:27,860 that round, okay. For instance, you know, some of the 263 00:15:27,860 --> 00:15:31,550 constraints we need evaluated for these things, okay, are the distances very bad 264 00:15:31,550 --> 00:15:34,000 for these two things. And we just want to swap these two, 265 00:15:34,000 --> 00:15:35,990 right? So we don't want to swap the rest of the 266 00:15:35,990 --> 00:15:39,630 round, okay? So here we say okay, so I want to swap, 267 00:15:39,630 --> 00:15:43,850 you know, the fact that team two is playing at one in week two, okay? 268 00:15:43,850 --> 00:15:47,160 And the fact that it's playing at, at six in week nine. 269 00:15:47,160 --> 00:15:49,490 So I want to really to swap these two things. 270 00:15:49,490 --> 00:15:54,170 Because that would give me, let's say, a distance which is much better, okay? 271 00:15:54,170 --> 00:15:57,830 So I want to do that, okay? And so, if I do that, what I, what's 272 00:15:57,830 --> 00:16:00,080 happening? If I actually swap these two things, 273 00:16:00,080 --> 00:16:04,800 okay, so I would have essentially, you know, the value here, which is one. 274 00:16:04,800 --> 00:16:07,900 I would have it on this particular week, on the week nine. 275 00:16:07,900 --> 00:16:11,980 But of course on week nine I'm already, I already have a game with one, right? 276 00:16:11,980 --> 00:16:16,320 So, we have to fix that as well, okay? So, we have to make sure that I'm not 277 00:16:16,320 --> 00:16:20,070 only swapping these two guys, but I'm constrained also to swap these two guys 278 00:16:20,070 --> 00:16:23,900 otherwise I would be having two ones on this particular week and that's not good, 279 00:16:23,900 --> 00:16:26,190 okay? So, one would be playing at home and away 280 00:16:26,190 --> 00:16:28,840 in this particular case. So, I have to swap that and obviously I'm 281 00:16:28,840 --> 00:16:32,520 changing the opponent of these guys so, I actually have to fix those guys as well 282 00:16:32,520 --> 00:16:35,450 as swap those guys as well. So the way to view this is that, in a 283 00:16:35,450 --> 00:16:42,710 sense, if I want to swap one and six, I have to look at the connected component 284 00:16:42,710 --> 00:16:45,640 between these things. I'm looking at how they are connecting 285 00:16:45,640 --> 00:16:49,560 with each other, in terms of the teams that they are already playing. 286 00:16:49,560 --> 00:16:53,680 And what you see here is, essentially, this round can be decomposed in several 287 00:16:53,680 --> 00:16:56,760 component. One of them is involving team one, two, 288 00:16:56,760 --> 00:17:00,320 six, and four. And the other one is involving team five 289 00:17:00,320 --> 00:17:02,620 and three. So what I'm basically swapping are all 290 00:17:02,620 --> 00:17:06,060 the games involving, you know, six, one, two, and four. 291 00:17:06,060 --> 00:17:09,650 And I"m basically keeping the games between five and three, this particular 292 00:17:09,650 --> 00:17:12,300 case, constant. And that's what you see here, okay? 293 00:17:12,300 --> 00:17:17,110 So, you see that team three and team five are not effected by this move, because 294 00:17:17,110 --> 00:17:20,220 they are not connected to six and one which were the two variables that I 295 00:17:20,220 --> 00:17:23,550 wanted to keep, okay? So, this is, this is this move. 296 00:17:23,550 --> 00:17:27,840 So it's a more interesting move, right? So, it's [UNKNOWN] it's only you know, 297 00:17:27,840 --> 00:17:31,740 basically swap partial parts of these rounds and so it's more flexible. 298 00:17:31,740 --> 00:17:36,120 You can actually select a little bit more carefully, you know, how, how you effect 299 00:17:36,120 --> 00:17:39,520 the schedule, okay? Now the last move is actually the most 300 00:17:39,520 --> 00:17:43,020 beautiful one. This is, this is swap partial team, okay? 301 00:17:43,020 --> 00:17:46,660 And once again what you see here is that I want to swap some part of the schedule 302 00:17:46,660 --> 00:17:50,910 between one and six, okay? So, I want to say oh, between team two 303 00:17:50,910 --> 00:17:54,230 and four, sorry. And team two on week nine is playing 304 00:17:54,230 --> 00:17:58,090 against one. And team four is playing against six. 305 00:17:58,090 --> 00:18:02,710 And what I want is that I want you know, I, I really want team one to play against 306 00:18:02,710 --> 00:18:06,400 six at that part and team one and team four to play against one. 307 00:18:06,400 --> 00:18:10,386 So, I want to swap these two guys. But if I do that, what's going to happen? 308 00:18:10,386 --> 00:18:15,390 So,you know that I, [UNKNOWN] you know you see six over there and you see a you 309 00:18:15,390 --> 00:18:18,350 know, one over there. So, if I put the six on top here. 310 00:18:18,350 --> 00:18:22,710 You know, you, you can already see that six is already on week four, you know I 311 00:18:22,710 --> 00:18:25,800 have already a six on week four. So, which basically means that, I would 312 00:18:25,800 --> 00:18:31,260 be playing at six twice, okay? So in a sense if I do that, I know that I 313 00:18:31,260 --> 00:18:34,490 will have to change this guy and also the same thing for the, for team four. 314 00:18:34,490 --> 00:18:37,300 You know I would have, I would have playing at once, twice. 315 00:18:37,300 --> 00:18:41,960 So, I need to also take care of this move and swap them between the two team, okay? 316 00:18:41,960 --> 00:18:44,570 So, that's what I'm going to do. I'm going to say, okay, I have to swap 317 00:18:44,570 --> 00:18:48,280 these guys as well. But now you see that I am introducing, 318 00:18:48,280 --> 00:18:51,570 you know five over there. I am touching to team five over there and 319 00:18:51,570 --> 00:18:55,020 also touching teams one, teams three over there, okay. 320 00:18:55,020 --> 00:18:59,950 So, that means that once again, you know, I, I have two, I have two teams that are 321 00:18:59,950 --> 00:19:02,960 affected by this thing. So, I will have to deal with those guys 322 00:19:02,960 --> 00:19:04,990 as well. And that's what you see that I'm doing 323 00:19:04,990 --> 00:19:07,670 here. So, I have more swaps to do, okay. 324 00:19:07,670 --> 00:19:10,720 And so I keep doing this and now at this point this is isolated. 325 00:19:10,720 --> 00:19:14,790 I have done all the swap and restored the fact that every team is playing against 326 00:19:14,790 --> 00:19:17,660 you know, every other team twice, once at home and once away. 327 00:19:17,660 --> 00:19:22,070 So, in a sense by propagating the information, I'm basically making sure 328 00:19:22,070 --> 00:19:25,080 that I'm restoring a round robin schedule, okay? 329 00:19:25,080 --> 00:19:29,360 Now, we have the same difficulty that I've shown you when we did the complete 330 00:19:29,360 --> 00:19:34,000 You know swap teams, which basically means that, I still have to fix the 331 00:19:34,000 --> 00:19:38,730 opponents of these teams, okay? So, all these cells here are not correct, 332 00:19:38,730 --> 00:19:41,660 but I'm going to fix them in the same way we fixed them before. 333 00:19:41,660 --> 00:19:45,160 And now I get this beautiful thing here, which is the final schedule. 334 00:19:45,160 --> 00:19:50,370 So, what is interesting here is that when you look at this move, this move is much, 335 00:19:50,370 --> 00:19:56,130 is much less drastic than, you know, just swapping The, the, the, the entire 336 00:19:56,130 --> 00:19:59,590 schedule of the two teams. I'm only swapping some part of the 337 00:19:59,590 --> 00:20:04,200 schedule and some part, of course, of the schedule of the opponents of this team, 338 00:20:04,200 --> 00:20:08,990 from these particular weeks, okay. And so that gives me a final grade, to 339 00:20:08,990 --> 00:20:13,080 actually modify the schedule. And this is really important when you try 340 00:20:13,080 --> 00:20:16,305 to solve these problems in practice and find very high quality solutions. 341 00:20:16,305 --> 00:20:21,090 Okay, so now I just want to tell you that this neighborhood is actually amazing, 342 00:20:21,090 --> 00:20:24,320 okay. So these are results of the TTP over 343 00:20:24,320 --> 00:20:26,900 time. I told you this is a very interesting and 344 00:20:26,900 --> 00:20:29,690 very difficult problem. So, people have been competing in trying 345 00:20:29,690 --> 00:20:32,730 to beat each other on this problem. And what you see, actually you probably 346 00:20:32,730 --> 00:20:36,530 cant see, but that's not a problem. So you see essentially people, you know, 347 00:20:36,530 --> 00:20:40,410 starting trying to beat each other on this particular, on this particular 348 00:20:40,410 --> 00:20:44,325 problem with starting from 2001. And on these three problems, which are 349 00:20:44,325 --> 00:20:49,470 the larger initial instance, 12 team, 14 team and 16 team, you see that the last 350 00:20:49,470 --> 00:20:53,600 solution that was produced was produced by an algorithm using the neighborhood 351 00:20:53,600 --> 00:20:56,180 that I've shown you. And it's not been beaten for, let's say, 352 00:20:56,180 --> 00:20:59,830 five or six years at this point, okay. So, it's really a very nice neighborhood. 353 00:20:59,830 --> 00:21:02,480 Of course you have to use all the techniques that I will talk about, you 354 00:21:02,480 --> 00:21:07,910 know, in two or three lectures. But essentially this neighborhood is 355 00:21:07,910 --> 00:21:11,450 really powerful and really a nice way of actually finding very high quality 356 00:21:11,450 --> 00:21:13,680 solution. For these problems the solution which 357 00:21:13,680 --> 00:21:19,450 have been produced by this neighborhood have never be, beaten so far, okay? 358 00:21:19,450 --> 00:21:22,690 So, I'll, so at this point what we have seen is a lot of different ways of 359 00:21:22,690 --> 00:21:26,250 actually defining neighborhoods. Very simple one, tiny one where we just 360 00:21:26,250 --> 00:21:29,890 modify the value of a variable. Swaps and then we see some really 361 00:21:29,890 --> 00:21:32,000 complicated moves like the one we saw today. 362 00:21:32,000 --> 00:21:35,620 Where we effect large part of the schedules but not completely large part 363 00:21:35,620 --> 00:21:37,960 but also something which are intermediary. 364 00:21:37,960 --> 00:21:40,390 And this is the key for solving some particular problems. 365 00:21:40,390 --> 00:21:43,540 So, what we're going to see in the next couple of lecture is how we can actually 366 00:21:43,540 --> 00:21:47,590 escape local minimum, okay? Local minimum, because so far the only 367 00:21:47,590 --> 00:21:50,480 thing that we have done is essentially applying these move greedily. 368 00:21:50,480 --> 00:21:53,560 But if you want to find really high quality solution, you will have to be a 369 00:21:53,560 --> 00:21:56,040 little bit more careful. Okay, see you next time.