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.