Okay, guys, this is Discrete Optimization Assignments: Getting Started.
So, this is essentially giving you a kind of a philosophical way of how to start
these assignments, if you don't know where to start from.
You get this thing in the face, and you don't know where to start, okay?
That's what we want to address here, okay, and so you can see that you know we
want to, we want to give you some hints on how to get started.
And then we also want to see that in this class there are basically 2 approaches
that you can follow and both of them are rewarded equally, you know because you
get a lot of points when you have a high quality but you'll also get you know
there are also many pause and they are different, okay.
And therefore if you get good great average grade, let's see on everyone of
them that, that can actually bring you up as well, okay?
So, the assignments are intended for modeling, what happens in real life.
You have your boss right? So your big boss coming and saying, you
know, we want you to solve this problem. Okay?
And the boss doesn't care how you're going to do it.
Okay? Just wants results, he just wants to look
good, and the company to be profitable, and so on.
Okay? Think, you know, Kennedy when he decided
here that America needed to go to the moon.
he didn't say, okay so to go to the moon you have to build this rocket.
To build this rocket you have to understand this, and you have to
understand that. And so on, he said, just get me to the
moon, that's what I want. So this is the same thing.
You have your boss, the boss is coming to you.
He's basically telling you, you have to actually solve these problems.
And its actually your responsability, and you don't expect the boss to tell you how
to do this exactly. Right?
But of course we give you a lot of material to actually get there, okay?
It's not like you know nothing about the rockets, right?
So we have given you a variety of techniques, but once again you don't
really know what's going to work or not and I really don't know how, you know,
which one is going to work either. When I see a new problem, for instance,
in that field, that's the, that, that's the nature of the beast.
This is a field where you look at this problem, you say whoo what is going to
work on this, right. And, and so really, you know, one of the
things here is that we're trying to build your intuition your experience, okay.
And so, basically the assignments are like this creativity where you have to
use the various techniques sometimes 2 of them on different parts of the assignment
to get, you know, the result that you want.
Okay? Now one of the big things in optimization
is that when you get a problem, you know, in, in optimization.
Okay? So you have the state of the art, you
know what your company, let's say, is doing.
Okay? So, so let's say they are doing things
manually. You know where they are.
And so the first thing that you do is, you're going to, program something using
optimization. And it's going to give you better results
than what they do in practice. Hopefully.
Okay? And then you can come back to your boss
and say hey boss, you know, I can improve this thing by 20%.
And your boss is going to say, oh that's good.
And he can stop there. And if, if, if, it stops there, it's
fine. You'll have nothing else to do.
Now your boss may be very clever and say, can you actually do better than that?
That's where the problem starts getting interesting.
If your boss is really smart, he's going to say, oh, can you tell me how much you
can improve this? Or, can you actually improve it further?
Okay? And that's where you start looking at
your first solution and try to improve it.
You want to say, oh, can I do a smarter greedy algorithm?
Or, can I use some of the other techniques to actually prove that...
I can't do better or I can only win in another you know .0001% and then you
really don't care, right you can come to your boss and say, yeah you can do better
but probably .0001%. So it's not worthy effort, okay so in a
sense we give you the tool to go beyond the first algorithm and to argue with
your boss in a very intelligent fashion, okay.
So, the baseline, okay, so typically you know, if we have an advice on how to
start you know, look at the problem, start to implement a simple solution.
Okay? A simple Greedy Algorithm.
You know, a simple you know, heuristic for looking at the problem and seeing how
good you are. And then you can take these 2 approaches:
The quality based approach, or let's say the scalability approach.
The scalability approach, the idea is that it's probably going to work on all
of the parts, okay?. It may not be the best on all of the
parts, but it's going to scale naturally, okay?
The quality approach okay, is essentially you know, you will be able to come to
your boss and say, I have the best solution,or I can prove that I.
0.001% of the optimal solution, okay? And there typically you would use
constraint programming or mixed integer programming.
It may not scale to the really large problems, okay?
And some of you have experienced that in graph coloring already.
Okay? And so in a sense these two approaches
are complementary. You can use one of the other in part and
you'll succeed very well in this class. Okay?
Then of course if you're really clever, you can say, hey hey, you know, I can
actually combine these 2. And some of the advanced material in this
class. I'm, telling you how to do that, okay.
So, and that's you know, that's kind of the cherry on the cake, at the end you
can do something like that. Okay, so once again, you can start with
this and then depending upon your standards or you know, where you want to
get in this class you can use one of these 2, and then if you really want to
get to the real top of the leader board you can think about using things like
this. Okay?
So, in a sense you know, one of the things that I will, you know.
You know, keep on telling people is that there is not a single approach that is
going to be successful for every problems in optimization, okay?
And for even, for instances of some of the problem, it's not the case.
You have seen that for the knapsack problem.
You have seen that for, you know, for graph coloring, okay?
So in a sense, the 2 approach that we have here, the scalability and and the
quality approach will give you a way to succeed in this class.
Okay? So, and once again you know I've, you
know, these, these were actually covering the mailbox for the, for the second week,
but the average, the average quality let's say you know if you want a 7 on all
the parts. You can get it let's say from the
scalability approach okay? Or you can get it from a high quality
approach where some of the problems are going to be nicely solved.
Some of them are not going to be but in average you are going to be good, okay so
in a sense and that obviously if you want to really be clever you are going to use
some of these in conjunction with some of the other ones and get essentially 7 and
10 or most of the on most of the assignments, okay so both approach are
viable you can combine them but this is the ID right so you start from [UNKNOWN]
then you take one of these two approaches see how far it gets you and then you can
start combining Okay? now, moving on.
So, it's very important here that you don't get stuck to one particular
assignment. You have this coloring, [INAUDIBLE] you
have 5 types, and then you have these seven, and you are really bothered by
that 7, and you agonize over it. You only think about this.
You know talk to your girlfriend or your boyfriend or your wife or whatever you
just focus on this its obsessed you completely.
Just don't do that, right, so the key idea is that you move on you move to the
next assignment. At some point in the class you may say.
Oh but this technique is really nice I could apply it to that particular problem
you come back to it you solve it in 30 seconds, I'm exaggerating right, but you
solve it and know you're already happy. So don't get stuck to the problem.
move on okay and come back to the problem later you will have the opportunity to do
that., Okay? Now, this is so there is a one week at
the end of the class. If, you know, you have a lot of people
which are just, you know, on the left of this curve, you, you, we will consider
extending, you know, and giving you another week to touch up at the end.
Okay? But we are not in the, we are not in the
position that we need to do that. You know, people are doing well right
now. So, you know, there is just a little bit
push, you know, we just need to push a little bit more people to move.
To move, across the curve. Okay?
Now, this is something, that, you know, I'm always, you know, I, I've always, you
know, mentioned, when, you know, I teach. And I have, you know, most of the class
have big programming assignment. And I always, you know, tell people, this
is not the way you want to do. So, so let me give you an analogy.
So, so Rafael Nadal the great tennis player, right.
So he was basically saying oh yea, when you win a grand slam, you are happy for
15 days. And I was saying, this poor guy is
training the entire year, he spent 15, you know, 50 weeks training, and then he
has these 15 days where he is happy. Wow, that's not a life.
Right? So, and this is the same thing here.
Right? So, you don't want to be unhappy the
entire time and then be ha, happy at the end.
So, what I want, what I don't want you to do is to think about this beautiful
amazingly perfect algorithm. Okay?
And you spec it. Okay?
So, you know what you want and implement. Okay?
And then you start free and then you start implementing, and this is your
degree of happiness or confidence. Is going to decrease, decrease over time
and you become you know more and more happy now you can't see any result you
are coding, coding, coding, coding, coding and then at the end of the, the
assignment period wow! You have a boost you know of happiness
because you just solved the problem, but for all the time here you have been
completely unhappy your confidence has been going, going, going down.
And then you have this rush of blood to the head, for you know 2 weeks or well,
actually in here it's going to be like 1 day right.
So in a sense you don't want that because most of your time is going to be you know
decreasing happiness and then one big rush at the end.
Okay, 1 high period, okay? So this is the way to do it right.
So you start with a reasonable degree of happiness, okay, and then essentially
you'll, you, you start coding and your confidence is going to decrease and then
you know wow! You have a, you know you have a first
high here because you completed the greedy algorithm, it gives you 7 on that
you know a couple of instances so you say oh, okay I feel good you know and I am
just to the beginning of this thing, right?
And then you say oh, you look at this greedy and you say oh, this problem I can
see why it's so bad, and though you start saying oh, this is what I wanted to do, I
want to implement a local search algorithm, okay?
Now, you, happiness decrease a little bit, you could, but then, wow, another
big boost because now you can solve, let's say, 4 or 5, or let's say 6 of the
instances. And so you have a seven on all these
things and you think well I feel pretty good, but you know I would like have some
10. Okay?
And then now you start, you know using MIP, you know, let's say a MIP approach,
okay, and once again, you know, your, your happiness and your confidence are
going to decrease. But then wow another big high because you
are basically, you know completed that assignment.
It may work or it may not work but at this point you say wow, at least I have
something and I can talk about it, okay. And then afterwards you say oh, but you
know really I should have used CP on this thing, you know, you start coding this
thing you know once again your happiness you know decreases but then you have
another big rush at the end because you completed all the approach and then you
have a 10 on everyone of these assignment.
That's what we want you to do, okay? [INAUDIBLE] one part, you know, get a
high for a couple of days, you know, then basically go down and, you know, get
another solution and so on. So, the average happiness here is much
higher than in the previous curve, okay, and you are basically stable, right.
It's not like a decreasing curve. Where your happiness is always
decreasing, decreasing, okay, so this is what we what you to do in a sense, okay,
so try to put these thinks in, you know, in a bottom of fashion in an agile way
[UNKNOWN] results early you are not getting depressed you don't try to build
this thing in one big stack, okay. So this is basically the advice that we
have for you, you know, try to have fun during the journey otherwise it's like
you know, spending 15 weeks, 50 weeks just training and then getting these 2
weeks where you're happy. We want you to be happy 50 weeks and then
have these 2 you know, weeks period where you work really hard.
Okay? Great, thank you guys.