0:01

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.

Â 16:44

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.

Â