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.