1 00:00:01,640 --> 00:00:05,646 Hello, I'm Indiana Jones. I am in the middle of this fabulous 2 00:00:05,646 --> 00:00:08,779 temple. But this temple is collapsing, the enemy 3 00:00:08,779 --> 00:00:12,250 is destroying it. And I have this knapsack, and this 4 00:00:12,250 --> 00:00:17,930 knapsack is full of very valuable things. And I'm going to show them to you, right? 5 00:00:17,930 --> 00:00:21,560 So, we have this fantastic book, Indiana Jones is reading about computational 6 00:00:21,560 --> 00:00:27,230 complexity. Indiana Jones loved physics, quantum 7 00:00:27,230 --> 00:00:30,926 theory. Now, this is ginger beer, Australia's 8 00:00:30,926 --> 00:00:37,540 best secret. This is the first computer, okay? 9 00:00:37,540 --> 00:00:42,340 So, the only stalk of this beautiful computer is actually a [UNKNOWN] at this 10 00:00:42,340 --> 00:00:46,075 point. Let's see, what else. 11 00:00:46,075 --> 00:00:52,627 Oh, I have this beautiful Chinese artifact, coming directly from Tsinghua 12 00:00:52,627 --> 00:00:56,870 University. And then I have the best of all here, I 13 00:00:56,870 --> 00:01:01,433 have this very, very valuable Japanese artifact, very heavy. 14 00:01:01,433 --> 00:01:05,525 And so Indiana Jones, has to decide which of these items he's going to be putting 15 00:01:05,525 --> 00:01:10,501 inside his knapsack. So, that he can escape the temple before 16 00:01:10,501 --> 00:01:13,673 it collapses. Okay, and of course, Indiana Jones is 17 00:01:13,673 --> 00:01:17,642 lucky, you know, he has this beautiful, beautiful textbook about computer 18 00:01:17,642 --> 00:01:21,530 science. So he's looking, you know, knapsack 19 00:01:21,530 --> 00:01:25,083 problem, okay? And then this textbook is saying oh, the 20 00:01:25,083 --> 00:01:28,010 knapsack problem is NP hard. What does that mean? 21 00:01:28,010 --> 00:01:33,680 That means this problem is intractable. Oh, but there is hope, there is hope. 22 00:01:33,680 --> 00:01:38,287 Approximation algorithm. ooh, but the knapsack problem, the 23 00:01:38,287 --> 00:01:42,230 multi-knapsack problem cannot be approximated. 24 00:01:42,230 --> 00:01:45,670 Okay so let's look, let's look, P space hard. 25 00:01:45,670 --> 00:01:50,198 Oh, that's even worse, Intractability. So, Indiana Jones is completely lost, he 26 00:01:50,198 --> 00:01:53,915 doesn't know what to do. But, but you remember, that when he was 27 00:01:53,915 --> 00:01:58,030 young he took this Coursera class of optimization. 28 00:01:58,030 --> 00:02:02,440 And he knew exactly how to pack this knapsack, so he packs the right item, and 29 00:02:02,440 --> 00:02:06,600 escape and, everything is fine afterwards. 30 00:02:06,600 --> 00:02:09,830 Well, this is what this class is about, okay? 31 00:02:09,830 --> 00:02:12,885 So this, what we're going to talk about in this class are optimization products, 32 00:02:12,885 --> 00:02:16,810 like filling up multi knapsack, or like filling a knapsack. 33 00:02:16,810 --> 00:02:20,610 And these problems are called optimization problems, okay? 34 00:02:20,610 --> 00:02:24,620 So, these are, as I just said, very, very hard problems. 35 00:02:24,620 --> 00:02:27,330 They are among the hardest problems in computer science. 36 00:02:27,330 --> 00:02:30,146 And we'll talk about it, and this is a very, very well-defined class, they are 37 00:02:30,146 --> 00:02:33,710 called NP complete, okay? And what is an NP-complete problem? 38 00:02:33,710 --> 00:02:35,700 So, you know, I'm going to define that in the next slide. 39 00:02:35,700 --> 00:02:37,430 But essentially these problems are everywhere. 40 00:02:37,430 --> 00:02:40,740 They are running the supply chains everywhere in the world. 41 00:02:40,740 --> 00:02:43,470 They are scheduling the sports leagues, that's really important, right? 42 00:02:43,470 --> 00:02:47,034 They are scheduling logistic systems, and, you know, a country like Australia 43 00:02:47,034 --> 00:02:50,760 spends 10 to 20% of its GDP just on logistics. 44 00:02:50,760 --> 00:02:54,970 You know the basically running the electrical power system. 45 00:02:54,970 --> 00:02:59,730 Okay, and many of the manufacturing firms, firms all along the world, okay. 46 00:02:59,730 --> 00:03:02,674 So, I told you that they were in, you know they belong to a complexity class 47 00:03:02,674 --> 00:03:07,234 which is NP hard . And that complexity class is basically 48 00:03:07,234 --> 00:03:11,896 dealing with decision problem. So, the question that this class is 49 00:03:11,896 --> 00:03:16,854 looking at are problems like, can I fill this knapsack that I have here, okay, for 50 00:03:16,854 --> 00:03:22,811 a value which is above K, okay? And so, informally, these NP-Complete 51 00:03:22,811 --> 00:03:27,290 problems will have two properties. Okay, the first one is very interesting. 52 00:03:27,290 --> 00:03:30,755 If I give you a solution, you will be able to verify that this actually indeed 53 00:03:30,755 --> 00:03:34,811 a solution very quickly. So, you have very efficient algorithms 54 00:03:34,811 --> 00:03:37,310 for checking if something is really a solution. 55 00:03:37,310 --> 00:03:40,421 If I tell you how to pack this knapsack, you will be able to very that you can 56 00:03:40,421 --> 00:03:43,510 actually do that. And it's the case for all the problems 57 00:03:43,510 --> 00:03:47,280 that I've shown you before. If I give you a sports schedule, you will 58 00:03:47,280 --> 00:03:51,270 be able to verify quickly if this is a real schedule or if two teams are 59 00:03:51,270 --> 00:03:56,780 actually playing twice on the same date, okay? 60 00:03:56,780 --> 00:04:00,500 So, you can do that, and the second property okay, is that if you can solve 61 00:04:00,500 --> 00:04:04,530 one of these problems okay, one of these NPR problems, then you can solve all of 62 00:04:04,530 --> 00:04:08,956 them, right? So, you can focus on one if you can solve 63 00:04:08,956 --> 00:04:12,755 it efficiently, okay, you will be able to solve all of them. 64 00:04:12,755 --> 00:04:15,610 So this is essentially what NP Completeness is about. 65 00:04:15,610 --> 00:04:18,319 These two properties, you can check very quickly, and if you can solve one of 66 00:04:18,319 --> 00:04:22,070 these hard problems, you can solve all of them. 67 00:04:22,070 --> 00:04:24,590 But as I told you they are, they are supposed to be very hard. 68 00:04:24,590 --> 00:04:29,326 So in, in, in theory, everybody believe that solving these problems is going to 69 00:04:29,326 --> 00:04:34,174 require exponential case. An exponential case is an exponential 70 00:04:34,174 --> 00:04:38,020 time in the worse case. An exponential time is kind of a, is kind 71 00:04:38,020 --> 00:04:41,350 of a nightmare. It basically means that if you increase 72 00:04:41,350 --> 00:04:44,550 the size of the problem by one, you build a time, and so you can only solve very, 73 00:04:44,550 --> 00:04:49,659 very, very tiny problems. So, you know what, what I told you is 74 00:04:49,659 --> 00:04:53,319 that they are very, very hard problems, but I also told you that they were 75 00:04:53,319 --> 00:04:57,610 everywhere, okay. So, this is logistics right? 76 00:04:57,610 --> 00:05:01,201 So, if you look at the country like Australia, which has, which is importing 77 00:05:01,201 --> 00:05:04,557 a lot of goods. They come to the harbor, let's say 78 00:05:04,557 --> 00:05:08,038 container, this container is to be offloaded from this ship, you know, 79 00:05:08,038 --> 00:05:11,814 cranes are going to take them, straddle carriers or RTG's are going to move them 80 00:05:11,814 --> 00:05:16,372 inside the port. So, that you can put them on the rails, 81 00:05:16,372 --> 00:05:20,590 on the rail, or on trucks, okay. These, this is full of optimization 82 00:05:20,590 --> 00:05:23,760 problems. Once you have these container that are in 83 00:05:23,760 --> 00:05:26,710 a yard, you have to schedule all these trucks to start to deliver, these 84 00:05:26,710 --> 00:05:30,490 containers to the customers, as quickly as possible. 85 00:05:30,490 --> 00:05:34,837 Another optimization problems, and these problems are usually solved everyday, 86 00:05:34,837 --> 00:05:38,093 okay? Energy, energy is an area which is full 87 00:05:38,093 --> 00:05:42,275 of optimization problem. Because wha-, energy is about meeting the 88 00:05:42,275 --> 00:05:44,894 load. Making sure that the load, the, the 89 00:05:44,894 --> 00:05:49,246 demand, and the generation agree. So, every day, many companies around the 90 00:05:49,246 --> 00:05:52,428 world are making sure that these two things are matched. 91 00:05:52,428 --> 00:05:57,260 You know, every, an you know, at every minute at every hour an so on, okay? 92 00:05:57,260 --> 00:06:01,800 An that requires something actually very complex, in an optimization problem. 93 00:06:01,800 --> 00:06:05,760 Just use Google, you know, Google unit commitment, you will see a huge number of 94 00:06:05,760 --> 00:06:08,150 papers. They are just trying to solve some of 95 00:06:08,150 --> 00:06:10,669 these problems. Okay, and then of use, this sport 96 00:06:10,669 --> 00:06:14,823 scheduling, we all love sports, we can't live without it, so this is essentially 97 00:06:14,823 --> 00:06:20,390 an NFL schedule for one of the seasons. Okay so you see Tennessee over here, 98 00:06:20,390 --> 00:06:23,822 which is playing first at Jacksonville, then about in, at Jacksonville then at 99 00:06:23,822 --> 00:06:29,469 home against Baltimore, Denver and so on. As you be producing these schedules, it 100 00:06:29,469 --> 00:06:32,870 is very hard, why, because you have a lot of constraints. 101 00:06:32,870 --> 00:06:36,153 OK, so you don't want, a team, sometimes some of these teams are actually sharing 102 00:06:36,153 --> 00:06:39,338 the same stadiums, so they can't, so unless they play against each other, they 103 00:06:39,338 --> 00:06:44,182 can't use the same stadium. All the stadium are actually shared by 104 00:06:44,182 --> 00:06:48,168 baseball and, and football teams. So, you can't schedule a baseball game on 105 00:06:48,168 --> 00:06:53,067 a, and an NFL game at the same time. Then you've all kinds of constraints on 106 00:06:53,067 --> 00:06:56,030 the, on the kind of schedules that you want. 107 00:06:56,030 --> 00:06:59,660 You don't want a team to play three times at home or three times a week. 108 00:06:59,660 --> 00:07:03,180 Fans would actually lose interest, if the team never comes back home, if it's 109 00:07:03,180 --> 00:07:07,670 always, you know, away, fans are actually losing interest. 110 00:07:07,670 --> 00:07:09,680 And also the skill is too hard for these teams. 111 00:07:09,680 --> 00:07:12,340 So, you need to balance the pattern of these games. 112 00:07:12,340 --> 00:07:17,215 And then finally, you know you want to have the schedule so that the television 113 00:07:17,215 --> 00:07:22,295 network are happy, okay? So, you want the nice scheduled on Sunday 114 00:07:22,295 --> 00:07:26,189 night on Monday night. And you have to balance that across the 115 00:07:26,189 --> 00:07:30,410 season, so that you don't always show the same team, okay? 116 00:07:30,410 --> 00:07:33,674 So scheduling all these all these things and optimizing this function is really, 117 00:07:33,674 --> 00:07:37,530 really hard as well, okay? So, what I've shown you is essentially a 118 00:07:37,530 --> 00:07:41,148 set of problems that we have. We know that they are very, very 119 00:07:41,148 --> 00:07:44,790 difficult to, to solve. They are very important, but they have 120 00:07:44,790 --> 00:07:47,690 this exponential behavior that you see here, right? 121 00:07:47,690 --> 00:07:50,758 So, this is the size of the problem that you see on the x-axis, and this is 122 00:07:50,758 --> 00:07:55,691 exponential run time. At some point, it becomes really really 123 00:07:55,691 --> 00:07:59,004 bad, okay? So, in the particular case that you see 124 00:07:59,004 --> 00:08:02,830 here, essentially, you know, in between 100 and 150. 125 00:08:02,830 --> 00:08:05,000 Let's say it's a logistic problem, these are trucks, okay? 126 00:08:05,000 --> 00:08:08,657 Between 100 and 150 trucks. The run time is taking so long, that 127 00:08:08,657 --> 00:08:11,840 there is no hope of solving this, the problem. 128 00:08:11,840 --> 00:08:14,270 So, what are we going to do? We know that in the worst case we will 129 00:08:14,270 --> 00:08:18,738 have this exponential behavior. So, one of the rules of this game, one of 130 00:08:18,738 --> 00:08:22,278 the games here that we are playing in optimization, is to try to push this 131 00:08:22,278 --> 00:08:26,576 exponential. We try to make sure that we can actually 132 00:08:26,576 --> 00:08:31,287 solve the real practical problems. And in this particular case there may be 133 00:08:31,287 --> 00:08:34,650 around 200, 300 tracks, or maybe you know, 2000. 134 00:08:34,650 --> 00:08:39,070 We try to push, push this exponential, so that we can actually solve practical 135 00:08:39,070 --> 00:08:42,473 problems, okay? Now this is very difficult to do and 136 00:08:42,473 --> 00:08:45,410 that's why we are teaching this class obviously, okay? 137 00:08:45,410 --> 00:08:48,418 But sometimes it's so hard that we can't actually do it, so what we have to do in 138 00:08:48,418 --> 00:08:52,320 those cases is to say, well, this is really too tough. 139 00:08:52,320 --> 00:08:54,550 But we still have to find a solution in practice. 140 00:08:54,550 --> 00:08:58,010 So, what we can do is actually lower our standards. 141 00:08:58,010 --> 00:09:01,026 We are going to say, you know, finding the best possible solution is this 142 00:09:01,026 --> 00:09:05,056 humongous set of possibilities. It's just not possible, and what we're 143 00:09:05,056 --> 00:09:09,470 going to do is simply say, okay, we'll find a very, very high quality solution. 144 00:09:09,470 --> 00:09:13,340 It's not going to be the best, but it's going to be really close to that. 145 00:09:13,340 --> 00:09:16,924 Okay, so that's the other kind of techniques that we will see in this 146 00:09:16,924 --> 00:09:20,937 class, okay? So, two things we push this exponential 147 00:09:20,937 --> 00:09:22,740 or we will. [COUGH] Excuse me. 148 00:09:22,740 --> 00:09:26,700 Or we will actually try to lower the standard and find high quality solution 149 00:09:26,700 --> 00:09:30,160 easily. So, let me try to summarize what we have 150 00:09:30,160 --> 00:09:34,418 said so far, okay. So, optimization problems are everywhere, 151 00:09:34,418 --> 00:09:37,189 okay? Now we know, we know from theory, that 152 00:09:37,189 --> 00:09:42,410 they are incredibly hard to solve. But we know also that we need to solve 153 00:09:42,410 --> 00:09:45,938 them, and we'll see techniques to actually trying to push this exponential 154 00:09:45,938 --> 00:09:50,870 or lowering our standards as little as possible, okay? 155 00:09:50,870 --> 00:09:53,730 So, one of the things which is really interesting here, is that these problems 156 00:09:53,730 --> 00:09:56,790 are really fun. Okay, so you'll see it's like playing a 157 00:09:56,790 --> 00:10:01,100 game, it's man against the machine. And we want to win, okay? 158 00:10:01,100 --> 00:10:05,384 So, this is, this is a very fun classes of problems, because you have to think 159 00:10:05,384 --> 00:10:09,940 about ways of actually defeating this complexity. 160 00:10:09,940 --> 00:10:13,600 And then one of the things that I want to focus on in the last couple of slides 161 00:10:13,600 --> 00:10:16,900 here, is to tell you that for some problems, they are really really 162 00:10:16,900 --> 00:10:21,542 important to solve. You really want to solve them, because 163 00:10:21,542 --> 00:10:24,520 they make a big difference in the lives of people. 164 00:10:24,520 --> 00:10:27,100 And I'm going to give you two examples, okay? 165 00:10:27,100 --> 00:10:29,340 So, the first one is about kidney exchanges. 166 00:10:29,340 --> 00:10:33,600 And so as, so the basic fact here, medically, is that we can live everyone 167 00:10:33,600 --> 00:10:38,806 can live with one kidney, okay? But every year, there are about 80,000 168 00:10:38,806 --> 00:10:43,320 patients let's say in the US. Who are requiring a kidney you know, 169 00:10:43,320 --> 00:10:46,871 transplant. No four, about 4000 of them every year 170 00:10:46,871 --> 00:10:50,531 are going to die because you know, the kidney, the kidney transplant is not 171 00:10:50,531 --> 00:10:54,008 ready. And the reason why that happens is that 172 00:10:54,008 --> 00:10:57,290 there are compatibility issues, and I'm going to explain them to you. 173 00:10:57,290 --> 00:11:01,196 So, essentially what you see over there okay, is a mother and a son and the son 174 00:11:01,196 --> 00:11:05,671 needs a kidney, okay? And the mother obviously, being a mother 175 00:11:05,671 --> 00:11:10,810 is going to be willing to actually give one of her kidneys to the son. 176 00:11:10,810 --> 00:11:14,740 But the problem here is that she may not be compatible with her son. 177 00:11:14,740 --> 00:11:18,034 She may not be able to give, you know, her kidneys such that the son is going to 178 00:11:18,034 --> 00:11:22,120 accept it, okay? The son would reject it, okay? 179 00:11:22,120 --> 00:11:25,719 On the other end, you know I may have, you know, I maybe, my wife may need a 180 00:11:25,719 --> 00:11:28,930 kidney. And I may be willing to give my, one of 181 00:11:28,930 --> 00:11:32,386 my kidneys to my wife, but once again, and I may not be compatible with my wife, 182 00:11:32,386 --> 00:11:37,190 at least from a kidney standpoint, okay? So, what can we do? 183 00:11:37,190 --> 00:11:40,820 Well, maybe I am compatible with the son of that, you know, lady, and that lady's 184 00:11:40,820 --> 00:11:45,514 actually compatible with my wife. So, instead of doing, you know, these 185 00:11:45,514 --> 00:11:49,330 transplanting and vertical fashion, we can just do an exchange. 186 00:11:49,330 --> 00:11:52,905 And give my kidney to the son, and this mother gives a kidney to my daughter, and 187 00:11:52,905 --> 00:11:57,320 everybody's happy, okay? So, that's the key idea here, okay? 188 00:11:57,320 --> 00:12:01,675 And obviously in practice, you know, I told you we have 80,000 people who are in 189 00:12:01,675 --> 00:12:05,891 need of a transplant. So, what we are going to look at is a big 190 00:12:05,891 --> 00:12:10,630 graph of all these people, these pairs of donors receivers. 191 00:12:10,630 --> 00:12:13,906 And so what you see on this screen here is essentially all the pairs, you know 192 00:12:13,906 --> 00:12:18,880 it's, it's a small graph, but you see all the pairs of donor and receiver. 193 00:12:18,880 --> 00:12:22,715 So, you see here a donor and receiver, you know this person is willing to donate 194 00:12:22,715 --> 00:12:26,838 a kidney, this one, this person here needs a kidney. 195 00:12:26,838 --> 00:12:30,310 And when I have an arrow here, it basically means that this donor, is 196 00:12:30,310 --> 00:12:34,278 compatible with that receiver, so this donor can actually give you know, her 197 00:12:34,278 --> 00:12:39,854 kidney to this person, okay? And so you're going to see another set of 198 00:12:39,854 --> 00:12:43,148 arrows here, for this particular donor here can give also a kidney to this 199 00:12:43,148 --> 00:12:46,326 receiver. Now this is a good situation, because at 200 00:12:46,326 --> 00:12:49,884 this point we can do an exchange. And of course we have, we may have a 201 00:12:49,884 --> 00:12:53,376 really huge graph like this. Here you see that this particular donor 202 00:12:53,376 --> 00:12:56,688 can give to this receiver. But this donor is compatible with only 203 00:12:56,688 --> 00:13:00,710 that receiver, and that particular donor is compatible with that receiver. 204 00:13:00,710 --> 00:13:03,750 We have another cycle, It's a longer cycle, it's threes. 205 00:13:03,750 --> 00:13:06,110 You know is three edges in this particular case, okay? 206 00:13:06,110 --> 00:13:09,052 And you of course know we have cycles all over the place here. 207 00:13:09,052 --> 00:13:13,147 And the, the, the, the goal here, is to try to cover all these pairs with these 208 00:13:13,147 --> 00:13:17,018 cycles, okay. Now we can take this graph and simplify 209 00:13:17,018 --> 00:13:19,502 it, okay? Because it really doesn't matter that we 210 00:13:19,502 --> 00:13:21,985 have pairs here. We will have an arrow when you know there 211 00:13:21,985 --> 00:13:24,745 is compatibility between the donor and the receiver. 212 00:13:24,745 --> 00:13:27,670 And when another arrow is the donor for this one, compatible with the receiver 213 00:13:27,670 --> 00:13:30,080 over there. And now we are looking at this graph, 214 00:13:30,080 --> 00:13:32,480 right? So, you see this graph, and we what we 215 00:13:32,480 --> 00:13:36,460 want to do is essentially cover it with cycles, okay? 216 00:13:36,460 --> 00:13:40,852 So, that we cover as many, as many, as many of the, of the pairs the nose that 217 00:13:40,852 --> 00:13:45,520 you see in that graph, okay. Of course the nose can only happen in 218 00:13:45,520 --> 00:13:48,401 two, you know, cycles because otherwise it would mean that you would be donating 219 00:13:48,401 --> 00:13:52,115 your kidney twice. Okay, so what we are trying to do is to 220 00:13:52,115 --> 00:13:57,756 cover this graph with cycles such that every node belongs to one cycle, okay? 221 00:13:57,756 --> 00:14:01,315 So this is one of them, okay? So, you see this beautiful blue, you 222 00:14:01,315 --> 00:14:05,215 know, blue cycle here moving to from, to from these donor person to other donor 223 00:14:05,215 --> 00:14:09,591 person so on. And if you apply this we are basically 224 00:14:09,591 --> 00:14:13,184 saving four people. And there are you know, four more peoples 225 00:14:13,184 --> 00:14:15,920 that are left without kidney at this point. 226 00:14:15,920 --> 00:14:19,690 They may receive a kidney later but at this point they don't have one, okay? 227 00:14:19,690 --> 00:14:22,570 So, this is another way of covering this graph here, okay? 228 00:14:22,570 --> 00:14:25,990 So, you see one of the cycle here, okay? Chook, chook, chook, chook. 229 00:14:25,990 --> 00:14:28,690 And you see another one here. Chook, chook, chook, chook, okay? 230 00:14:28,690 --> 00:14:32,210 I'm showing it to you now, okay? And so in this particular case, if we 231 00:14:32,210 --> 00:14:35,894 applied this covering, okay? So, we save six people, and only two are 232 00:14:35,894 --> 00:14:39,390 left waiting for a transplant, at this point, okay? 233 00:14:39,390 --> 00:14:43,234 So, now you have to imagine, okay? So, this is tiny, right, this is easy, we 234 00:14:43,234 --> 00:14:47,199 can do that by hand, okay? But in practice I told we've got this 235 00:14:47,199 --> 00:14:50,290 gigantic graph with about 80,000 notes, okay? 236 00:14:50,290 --> 00:14:54,052 And now finding the best covering with cycles of these notes is really becoming 237 00:14:54,052 --> 00:14:58,328 a very interesting problem. So, if you take this class you will learn 238 00:14:58,328 --> 00:15:02,326 the techniques to actually do that, okay? So, let me talk about something 239 00:15:02,326 --> 00:15:05,544 completely different, but which is also very close to my heart. 240 00:15:05,544 --> 00:15:08,334 Which is a problem that we have been working on, you know for a, for about 241 00:15:08,334 --> 00:15:11,630 five years now, and this is called, disaster management. 242 00:15:11,630 --> 00:15:14,916 So, this is an example where you see, this is a hurricane of category 3, it's 243 00:15:14,916 --> 00:15:19,190 actually Irene, that hit the United States in August 2011. 244 00:15:19,190 --> 00:15:24,154 They are, they were about 56 you know, people who died in that particular due, 245 00:15:24,154 --> 00:15:29,488 due to the particular hurricane. And essentially the cost of that 246 00:15:29,488 --> 00:15:34,970 hurricane is estimated to be about 50 billion dollars at this point. 247 00:15:34,970 --> 00:15:37,590 So, you see the picture of this hurricane over here. 248 00:15:37,590 --> 00:15:40,440 this is another picture, this is really a scary hurricane. 249 00:15:40,440 --> 00:15:43,166 So, one of the things that we have in this area, is that we have very good 250 00:15:43,166 --> 00:15:47,510 prediction algorithms to actually predict what the hurricane is going to do. 251 00:15:47,510 --> 00:15:50,150 You see that here, you see the prediction and you see the cone over there, you see 252 00:15:50,150 --> 00:15:53,515 one path and the cone. The cone is typically about 80% of the 253 00:15:53,515 --> 00:15:56,273 paths, okay? And so in a sense you have a lot of 254 00:15:56,273 --> 00:16:00,470 information about what this path can do, okay? 255 00:16:00,470 --> 00:16:03,662 And so one of the things that this hurricane is going to do is basically 256 00:16:03,662 --> 00:16:07,231 create blackout. And so what you see here on this picture, 257 00:16:07,231 --> 00:16:10,927 okay, basically all the blackouts on the East Coast, on the East Coast of the 258 00:16:10,927 --> 00:16:15,870 United States, which were created by hurricane Irene. 259 00:16:15,870 --> 00:16:19,445 So, I was living at the time in this particular, in this particular, circle 260 00:16:19,445 --> 00:16:22,733 over there. You know, I was teaching fabulous in the 261 00:16:22,733 --> 00:16:26,150 graduated Brown University. Okay, [UNKNOWN] you know this is for you. 262 00:16:26,150 --> 00:16:31,930 And, and essentially these places had a, had a basically, a blackout of about five 263 00:16:31,930 --> 00:16:35,516 days. Now, can you imagine what it means to be 264 00:16:35,516 --> 00:16:40,360 in a blackout for five days. So, this is what is happening to you. 265 00:16:44,080 --> 00:16:46,835 Okay? So, no electricity, no refrigeration, no 266 00:16:46,835 --> 00:16:50,975 air conditioning, no more [UNKNOWN] phones after a while, no Facebook, 267 00:16:50,975 --> 00:16:54,836 nothing, right? It's really boring and after five days 268 00:16:54,836 --> 00:16:57,890 you are ready to, you know, do something radical, okay? 269 00:16:57,890 --> 00:17:01,855 So and so, this is another example which, which actually created exactly same 270 00:17:01,855 --> 00:17:04,868 thing. This is Hurricane Sandy, actually much 271 00:17:04,868 --> 00:17:07,890 more damaging, even. Okay, so once again, you know, what we 272 00:17:07,890 --> 00:17:10,890 had were very good prediction, you see the path of the hurricane and they 273 00:17:10,890 --> 00:17:13,990 predicted that it going to turn and it actually turn exactly, almost exactly 274 00:17:13,990 --> 00:17:19,402 what they said it would turn, okay? And it created massive floods that you 275 00:17:19,402 --> 00:17:23,864 see there, and massive blackouts, okay? So this is a picture of New York City 276 00:17:23,864 --> 00:17:27,640 during, you know, during Sandy, okay, so it's beautiful pictures, of course 277 00:17:27,640 --> 00:17:32,266 blackout everywhere, okay? And so essentially what we try to do in 278 00:17:32,266 --> 00:17:37,360 this particular area is trying to restore electricity as quickly as possible. 279 00:17:37,360 --> 00:17:40,570 We try to reduce the size of such a blackout. 280 00:17:40,570 --> 00:17:43,270 So, you want to repair the grid as quickly as possible and the way you have 281 00:17:43,270 --> 00:17:46,105 to do that is essentially sending crews to repair various parts of the grid, 282 00:17:46,105 --> 00:17:49,048 okay? So, that's to minimize the size of the 283 00:17:49,048 --> 00:17:51,030 blackout. You know, you restore the line, your 284 00:17:51,030 --> 00:17:53,200 restore the generator, and things like this. 285 00:17:53,200 --> 00:17:56,764 And what you want to minimize is the size of the blackout on this red area that you 286 00:17:56,764 --> 00:18:00,661 see over there, okay? So, what you see in this graph, you know 287 00:18:00,661 --> 00:18:04,843 the x axis is essentially time. The y axis is the power that is flowing 288 00:18:04,843 --> 00:18:08,612 inside your network. Of usually you want to be restoring the 289 00:18:08,612 --> 00:18:13,710 maximum power, and every point that you see there is a restoration action. 290 00:18:13,710 --> 00:18:17,126 It means that a repair crew came and fixed a power line and now the current, 291 00:18:17,126 --> 00:18:21,807 you know, is flowing again, okay? And so sometimes you restore enough that 292 00:18:21,807 --> 00:18:25,344 the power flows a bit more. You restore more, more power flows in 293 00:18:25,344 --> 00:18:28,200 your network. And so what you want to do is schedule 294 00:18:28,200 --> 00:18:32,330 all these repairs so that you minimize the size of this blackout, okay? 295 00:18:32,330 --> 00:18:35,410 So this this is basically combining two problems, Okay? 296 00:18:35,410 --> 00:18:39,190 So, the first problems here is, you know, basically a logistic problem. 297 00:18:39,190 --> 00:18:42,097 You have to have these trucks pick up some parts, okay, so that you can 298 00:18:42,097 --> 00:18:45,463 actually go to the particular sites where a line needs or a generator needs to be 299 00:18:45,463 --> 00:18:50,110 fixed, and you actually fix it. That's the pluses that you see there, the 300 00:18:50,110 --> 00:18:53,380 minus that you see over there. I'll basically place this where you pick 301 00:18:53,380 --> 00:18:56,626 up some parts, okay? Now every one of these restoration action 302 00:18:56,626 --> 00:19:00,703 correspond to something that you see on this power graph here, okay? 303 00:19:00,703 --> 00:19:04,042 So, it basically means that when I repair that particular, that particular 304 00:19:04,042 --> 00:19:07,660 component, no more power is flowing inside my network. 305 00:19:07,660 --> 00:19:10,116 Now you have to synchronize these two things, okay? 306 00:19:10,116 --> 00:19:13,700 This is a pluralistic problem, this is a power restoration problem. 307 00:19:13,700 --> 00:19:19,179 Know the difficulty that you have is essentially that this thing here, okay? 308 00:19:19,179 --> 00:19:24,341 The power system, is regulated by this power flow of equations, okay? 309 00:19:24,341 --> 00:19:28,980 So Carlton and I, you know Carlton is the head T of this class. 310 00:19:28,980 --> 00:19:31,832 Basically spending four or five years looking at this thing to try to solve 311 00:19:31,832 --> 00:19:35,392 them better. It's really really complicated, but you 312 00:19:35,392 --> 00:19:39,413 have to combine that with the logistic problem, okay? 313 00:19:39,413 --> 00:19:42,989 And so this is amazingly complex, okay? But once again, if you take this class, 314 00:19:42,989 --> 00:19:46,430 you will learn the techniques to actually do that. 315 00:19:46,430 --> 00:19:49,510 And what are the kinds of reasons that you will have, look at this graph again. 316 00:19:49,510 --> 00:19:52,330 I told you time, you know, I told you power flow. 317 00:19:52,330 --> 00:19:56,010 This is essentially what this is the state of the art in practice. 318 00:19:56,010 --> 00:19:58,716 That's the restoration if you use the techniques, let's say, like, four or five 319 00:19:58,716 --> 00:20:01,610 years ago. And this is what you can do with the 320 00:20:01,610 --> 00:20:05,020 algorithm that we have designed you reduced substantially the size of the 321 00:20:05,020 --> 00:20:08,981 blackout, okay? Once again if you take this class this is 322 00:20:08,981 --> 00:20:12,401 the kind of reduction, this is the kind of results that you will be able to 323 00:20:12,401 --> 00:20:16,800 produce, okay? So, welcome to Discreet Optimization. 324 00:20:16,800 --> 00:20:20,394 This is an amazingly interesting class. It is an introductory to Discrete 325 00:20:20,394 --> 00:20:23,650 Optimization, right? So, we start from almost nothing and 326 00:20:23,650 --> 00:20:26,956 build up all the all the tools to actually sum solve all, some of these 327 00:20:26,956 --> 00:20:30,300 problems. But it's an interaction, It's also a 328 00:20:30,300 --> 00:20:33,879 very, very difficult class, okay? So, you will have to work very, very 329 00:20:33,879 --> 00:20:36,620 hard. So, think twice before taking the class. 330 00:20:36,620 --> 00:20:37,840 Thank you.