Hello, I'm Indiana Jones. I am in the middle of this fabulous temple. But this temple is collapsing, the enemy is destroying it. And I have this knapsack, and this knapsack is full of very valuable things. And I'm going to show them to you, right? So, we have this fantastic book, Indiana Jones is reading about computational complexity. Indiana Jones loved physics, quantum theory. Now, this is ginger beer, Australia's best secret. This is the first computer, okay? So, the only stalk of this beautiful computer is actually a [UNKNOWN] at this point. Let's see, what else. Oh, I have this beautiful Chinese artifact, coming directly from Tsinghua University. And then I have the best of all here, I have this very, very valuable Japanese artifact, very heavy. And so Indiana Jones, has to decide which of these items he's going to be putting inside his knapsack. So, that he can escape the temple before it collapses. Okay, and of course, Indiana Jones is lucky, you know, he has this beautiful, beautiful textbook about computer science. So he's looking, you know, knapsack problem, okay? And then this textbook is saying oh, the knapsack problem is NP hard. What does that mean? That means this problem is intractable. Oh, but there is hope, there is hope. Approximation algorithm. ooh, but the knapsack problem, the multi-knapsack problem cannot be approximated. Okay so let's look, let's look, P space hard. Oh, that's even worse, Intractability. So, Indiana Jones is completely lost, he doesn't know what to do. But, but you remember, that when he was young he took this Coursera class of optimization. And he knew exactly how to pack this knapsack, so he packs the right item, and escape and, everything is fine afterwards. Well, this is what this class is about, okay? So this, what we're going to talk about in this class are optimization products, like filling up multi knapsack, or like filling a knapsack. And these problems are called optimization problems, okay? So, these are, as I just said, very, very hard problems. They are among the hardest problems in computer science. And we'll talk about it, and this is a very, very well-defined class, they are called NP complete, okay? And what is an NP-complete problem? So, you know, I'm going to define that in the next slide. But essentially these problems are everywhere. They are running the supply chains everywhere in the world. They are scheduling the sports leagues, that's really important, right? They are scheduling logistic systems, and, you know, a country like Australia spends 10 to 20% of its GDP just on logistics. You know the basically running the electrical power system. Okay, and many of the manufacturing firms, firms all along the world, okay. So, I told you that they were in, you know they belong to a complexity class which is NP hard . And that complexity class is basically dealing with decision problem. So, the question that this class is looking at are problems like, can I fill this knapsack that I have here, okay, for a value which is above K, okay? And so, informally, these NP-Complete problems will have two properties. Okay, the first one is very interesting. If I give you a solution, you will be able to verify that this actually indeed a solution very quickly. So, you have very efficient algorithms for checking if something is really a solution. If I tell you how to pack this knapsack, you will be able to very that you can actually do that. And it's the case for all the problems that I've shown you before. If I give you a sports schedule, you will be able to verify quickly if this is a real schedule or if two teams are actually playing twice on the same date, okay? So, you can do that, and the second property okay, is that if you can solve one of these problems okay, one of these NPR problems, then you can solve all of them, right? So, you can focus on one if you can solve it efficiently, okay, you will be able to solve all of them. So this is essentially what NP Completeness is about. These two properties, you can check very quickly, and if you can solve one of these hard problems, you can solve all of them. But as I told you they are, they are supposed to be very hard. So in, in, in theory, everybody believe that solving these problems is going to require exponential case. An exponential case is an exponential time in the worse case. An exponential time is kind of a, is kind of a nightmare. It basically means that if you increase the size of the problem by one, you build a time, and so you can only solve very, very, very tiny problems. So, you know what, what I told you is that they are very, very hard problems, but I also told you that they were everywhere, okay. So, this is logistics right? So, if you look at the country like Australia, which has, which is importing a lot of goods. They come to the harbor, let's say container, this container is to be offloaded from this ship, you know, cranes are going to take them, straddle carriers or RTG's are going to move them inside the port. So, that you can put them on the rails, on the rail, or on trucks, okay. These, this is full of optimization problems. Once you have these container that are in a yard, you have to schedule all these trucks to start to deliver, these containers to the customers, as quickly as possible. Another optimization problems, and these problems are usually solved everyday, okay? Energy, energy is an area which is full of optimization problem. Because wha-, energy is about meeting the load. Making sure that the load, the, the demand, and the generation agree. So, every day, many companies around the world are making sure that these two things are matched. You know, every, an you know, at every minute at every hour an so on, okay? An that requires something actually very complex, in an optimization problem. Just use Google, you know, Google unit commitment, you will see a huge number of papers. They are just trying to solve some of these problems. Okay, and then of use, this sport scheduling, we all love sports, we can't live without it, so this is essentially an NFL schedule for one of the seasons. Okay so you see Tennessee over here, which is playing first at Jacksonville, then about in, at Jacksonville then at home against Baltimore, Denver and so on. As you be producing these schedules, it is very hard, why, because you have a lot of constraints. OK, so you don't want, a team, sometimes some of these teams are actually sharing the same stadiums, so they can't, so unless they play against each other, they can't use the same stadium. All the stadium are actually shared by baseball and, and football teams. So, you can't schedule a baseball game on a, and an NFL game at the same time. Then you've all kinds of constraints on the, on the kind of schedules that you want. You don't want a team to play three times at home or three times a week. Fans would actually lose interest, if the team never comes back home, if it's always, you know, away, fans are actually losing interest. And also the skill is too hard for these teams. So, you need to balance the pattern of these games. And then finally, you know you want to have the schedule so that the television network are happy, okay? So, you want the nice scheduled on Sunday night on Monday night. And you have to balance that across the season, so that you don't always show the same team, okay? So scheduling all these all these things and optimizing this function is really, really hard as well, okay? So, what I've shown you is essentially a set of problems that we have. We know that they are very, very difficult to, to solve. They are very important, but they have this exponential behavior that you see here, right? So, this is the size of the problem that you see on the x-axis, and this is exponential run time. At some point, it becomes really really bad, okay? So, in the particular case that you see here, essentially, you know, in between 100 and 150. Let's say it's a logistic problem, these are trucks, okay? Between 100 and 150 trucks. The run time is taking so long, that there is no hope of solving this, the problem. So, what are we going to do? We know that in the worst case we will have this exponential behavior. So, one of the rules of this game, one of the games here that we are playing in optimization, is to try to push this exponential. We try to make sure that we can actually solve the real practical problems. And in this particular case there may be around 200, 300 tracks, or maybe you know, 2000. We try to push, push this exponential, so that we can actually solve practical problems, okay? Now this is very difficult to do and that's why we are teaching this class obviously, okay? But sometimes it's so hard that we can't actually do it, so what we have to do in those cases is to say, well, this is really too tough. But we still have to find a solution in practice. So, what we can do is actually lower our standards. We are going to say, you know, finding the best possible solution is this humongous set of possibilities. It's just not possible, and what we're going to do is simply say, okay, we'll find a very, very high quality solution. It's not going to be the best, but it's going to be really close to that. Okay, so that's the other kind of techniques that we will see in this class, okay? So, two things we push this exponential or we will. [COUGH] Excuse me. Or we will actually try to lower the standard and find high quality solution easily. So, let me try to summarize what we have said so far, okay. So, optimization problems are everywhere, okay? Now we know, we know from theory, that they are incredibly hard to solve. But we know also that we need to solve them, and we'll see techniques to actually trying to push this exponential or lowering our standards as little as possible, okay? So, one of the things which is really interesting here, is that these problems are really fun. Okay, so you'll see it's like playing a game, it's man against the machine. And we want to win, okay? So, this is, this is a very fun classes of problems, because you have to think about ways of actually defeating this complexity. And then one of the things that I want to focus on in the last couple of slides here, is to tell you that for some problems, they are really really important to solve. You really want to solve them, because they make a big difference in the lives of people. And I'm going to give you two examples, okay? So, the first one is about kidney exchanges. And so as, so the basic fact here, medically, is that we can live everyone can live with one kidney, okay? But every year, there are about 80,000 patients let's say in the US. Who are requiring a kidney you know, transplant. No four, about 4000 of them every year are going to die because you know, the kidney, the kidney transplant is not ready. And the reason why that happens is that there are compatibility issues, and I'm going to explain them to you. So, essentially what you see over there okay, is a mother and a son and the son needs a kidney, okay? And the mother obviously, being a mother is going to be willing to actually give one of her kidneys to the son. But the problem here is that she may not be compatible with her son. She may not be able to give, you know, her kidneys such that the son is going to accept it, okay? The son would reject it, okay? On the other end, you know I may have, you know, I maybe, my wife may need a kidney. And I may be willing to give my, one of my kidneys to my wife, but once again, and I may not be compatible with my wife, at least from a kidney standpoint, okay? So, what can we do? Well, maybe I am compatible with the son of that, you know, lady, and that lady's actually compatible with my wife. So, instead of doing, you know, these transplanting and vertical fashion, we can just do an exchange. And give my kidney to the son, and this mother gives a kidney to my daughter, and everybody's happy, okay? So, that's the key idea here, okay? And obviously in practice, you know, I told you we have 80,000 people who are in need of a transplant. So, what we are going to look at is a big graph of all these people, these pairs of donors receivers. And so what you see on this screen here is essentially all the pairs, you know it's, it's a small graph, but you see all the pairs of donor and receiver. So, you see here a donor and receiver, you know this person is willing to donate a kidney, this one, this person here needs a kidney. And when I have an arrow here, it basically means that this donor, is compatible with that receiver, so this donor can actually give you know, her kidney to this person, okay? And so you're going to see another set of arrows here, for this particular donor here can give also a kidney to this receiver. Now this is a good situation, because at this point we can do an exchange. And of course we have, we may have a really huge graph like this. Here you see that this particular donor can give to this receiver. But this donor is compatible with only that receiver, and that particular donor is compatible with that receiver. We have another cycle, It's a longer cycle, it's threes. You know is three edges in this particular case, okay? And you of course know we have cycles all over the place here. And the, the, the, the goal here, is to try to cover all these pairs with these cycles, okay. Now we can take this graph and simplify it, okay? Because it really doesn't matter that we have pairs here. We will have an arrow when you know there is compatibility between the donor and the receiver. And when another arrow is the donor for this one, compatible with the receiver over there. And now we are looking at this graph, right? So, you see this graph, and we what we want to do is essentially cover it with cycles, okay? So, that we cover as many, as many, as many of the, of the pairs the nose that you see in that graph, okay. Of course the nose can only happen in two, you know, cycles because otherwise it would mean that you would be donating your kidney twice. Okay, so what we are trying to do is to cover this graph with cycles such that every node belongs to one cycle, okay? So this is one of them, okay? So, you see this beautiful blue, you know, blue cycle here moving to from, to from these donor person to other donor person so on. And if you apply this we are basically saving four people. And there are you know, four more peoples that are left without kidney at this point. They may receive a kidney later but at this point they don't have one, okay? So, this is another way of covering this graph here, okay? So, you see one of the cycle here, okay? Chook, chook, chook, chook. And you see another one here. Chook, chook, chook, chook, okay? I'm showing it to you now, okay? And so in this particular case, if we applied this covering, okay? So, we save six people, and only two are left waiting for a transplant, at this point, okay? So, now you have to imagine, okay? So, this is tiny, right, this is easy, we can do that by hand, okay? But in practice I told we've got this gigantic graph with about 80,000 notes, okay? And now finding the best covering with cycles of these notes is really becoming a very interesting problem. So, if you take this class you will learn the techniques to actually do that, okay? So, let me talk about something completely different, but which is also very close to my heart. Which is a problem that we have been working on, you know for a, for about five years now, and this is called, disaster management. So, this is an example where you see, this is a hurricane of category 3, it's actually Irene, that hit the United States in August 2011. They are, they were about 56 you know, people who died in that particular due, due to the particular hurricane. And essentially the cost of that hurricane is estimated to be about 50 billion dollars at this point. So, you see the picture of this hurricane over here. this is another picture, this is really a scary hurricane. So, one of the things that we have in this area, is that we have very good prediction algorithms to actually predict what the hurricane is going to do. You see that here, you see the prediction and you see the cone over there, you see one path and the cone. The cone is typically about 80% of the paths, okay? And so in a sense you have a lot of information about what this path can do, okay? And so one of the things that this hurricane is going to do is basically create blackout. And so what you see here on this picture, okay, basically all the blackouts on the East Coast, on the East Coast of the United States, which were created by hurricane Irene. So, I was living at the time in this particular, in this particular, circle over there. You know, I was teaching fabulous in the graduated Brown University. Okay, [UNKNOWN] you know this is for you. And, and essentially these places had a, had a basically, a blackout of about five days. Now, can you imagine what it means to be in a blackout for five days. So, this is what is happening to you. Okay? So, no electricity, no refrigeration, no air conditioning, no more [UNKNOWN] phones after a while, no Facebook, nothing, right? It's really boring and after five days you are ready to, you know, do something radical, okay? So and so, this is another example which, which actually created exactly same thing. This is Hurricane Sandy, actually much more damaging, even. Okay, so once again, you know, what we had were very good prediction, you see the path of the hurricane and they predicted that it going to turn and it actually turn exactly, almost exactly what they said it would turn, okay? And it created massive floods that you see there, and massive blackouts, okay? So this is a picture of New York City during, you know, during Sandy, okay, so it's beautiful pictures, of course blackout everywhere, okay? And so essentially what we try to do in this particular area is trying to restore electricity as quickly as possible. We try to reduce the size of such a blackout. So, you want to repair the grid as quickly as possible and the way you have to do that is essentially sending crews to repair various parts of the grid, okay? So, that's to minimize the size of the blackout. You know, you restore the line, your restore the generator, and things like this. And what you want to minimize is the size of the blackout on this red area that you see over there, okay? So, what you see in this graph, you know the x axis is essentially time. The y axis is the power that is flowing inside your network. Of usually you want to be restoring the maximum power, and every point that you see there is a restoration action. It means that a repair crew came and fixed a power line and now the current, you know, is flowing again, okay? And so sometimes you restore enough that the power flows a bit more. You restore more, more power flows in your network. And so what you want to do is schedule all these repairs so that you minimize the size of this blackout, okay? So this this is basically combining two problems, Okay? So, the first problems here is, you know, basically a logistic problem. You have to have these trucks pick up some parts, okay, so that you can actually go to the particular sites where a line needs or a generator needs to be fixed, and you actually fix it. That's the pluses that you see there, the minus that you see over there. I'll basically place this where you pick up some parts, okay? Now every one of these restoration action correspond to something that you see on this power graph here, okay? So, it basically means that when I repair that particular, that particular component, no more power is flowing inside my network. Now you have to synchronize these two things, okay? This is a pluralistic problem, this is a power restoration problem. Know the difficulty that you have is essentially that this thing here, okay? The power system, is regulated by this power flow of equations, okay? So Carlton and I, you know Carlton is the head T of this class. Basically spending four or five years looking at this thing to try to solve them better. It's really really complicated, but you have to combine that with the logistic problem, okay? And so this is amazingly complex, okay? But once again, if you take this class, you will learn the techniques to actually do that. And what are the kinds of reasons that you will have, look at this graph again. I told you time, you know, I told you power flow. This is essentially what this is the state of the art in practice. That's the restoration if you use the techniques, let's say, like, four or five years ago. And this is what you can do with the algorithm that we have designed you reduced substantially the size of the blackout, okay? Once again if you take this class this is the kind of reduction, this is the kind of results that you will be able to produce, okay? So, welcome to Discreet Optimization. This is an amazingly interesting class. It is an introductory to Discrete Optimization, right? So, we start from almost nothing and build up all the all the tools to actually sum solve all, some of these problems. But it's an interaction, It's also a very, very difficult class, okay? So, you will have to work very, very hard. So, think twice before taking the class. Thank you.