0:00

Okay, guys, this is discrete, discrete optimization.

And this lecture is actually as important as, as the material itself.

It's basically about how you should look at these

assignments and what are the various way of approaching them.

Right?

So in a sense what you're going to do is what, what's going to happen to you is

going to do, you're going to get problems that are

basically thrown to you in your face, right.

And you're going to get them.

Boom!

And you're going to say, why is happening to me,

right? And you're going to say, how do I do this?

How, and, and, and the more you look at these

problems initially, you're going to say, wow, this is completely insane.

Okay, and so, so, I want to tell you basically in this

lecture how you can actually approach this thing in a reasonable fashion.

And then I want to discuss the various way these approaches can be, can be applied

to get a good grade, a passing

grade, a certificate, or a certificate of distinction.

Giving you some advice on how you can do this.

Okay? So, so, the assignment design.

The assignments have been designed to emulate, you know, the real world.

So, okay, so, so you have learn, you think about it.

Your boss is going to tell you, okay, so we need to solve the problem.

And, and, you have to figure out how to do it.

It's not going to, tell you how to do it.

He's just going to tell you, this is the one I want

as a solution, this is what, the problems that I want to solve.

You know, get you're act together, solve it, okay?

So it's like Kennedy, you know in the 60s when

he told, you know, the, you know he told America okay so we want to send

a man on the moon, okay by the end of the decade, the decade, right?

So he said that, but he didn't say, okay we have to build a

rocket, we have to find this, you know, to solve this kinds of scientific problems.

We have to find people who are capable

of actually flying this rocket and thinks like this.

No, he didn't care, right?

The only thing that he wanted is solve me this

problem so I don't care if your rocket looks blue,

red, you know, it's wide or thin or whatever, right?

And so this is, this is what this class is about, okay.

We're going to throw problems at your face, and

we won't tell you how to solve them.

We'll give you the means to actually solve them.

We'll give you, you know, the equivalent of the physics, or the, you

know, engineering that you need to build the rocket for, for discrete optimization.

But we won't tell you which pieces you have

to assemble for, you know, for it to work.

Okay? So we basically give you the problems, and

you have to find a way to solve them, okay?

Now how you solve the problem?

Okay, so we have this hat, right?

So you use the first one, you see if it works.

Doesn't work?

Use another one, right?

So, but we won't tell you which one is to be used, right.

For one particular assignment, this one is actually tricky, right.

So for one particular assignment, it's not

very clear which hat is going to work Okay?

So you may have to try several of them before you actually find a solution.

Okay?

And what the goal of the class is, is about, you know, actually

finding which of these hat is actually good for which of these problems.

What is the real, you know, asset of these, the, these hats?

For what classes of problems are they good, and so on.

Okay?

So, this is really heavy so let me, you know, bring that down.

Okay, so, so to get started, you know, you have to imagine yourself

in a company, and your job, this is the only way to, to,

this is the only important part.

You have to imagine that your job, you know, your boss

is coming and saying, you know, you have to solve these problems.

Okay, get to work.

Okay?

So what we recommend is that the first thing you do, is

you implement something really simple, you know, kind of a greedy solution.

Get an understanding of the problem.

Know that you actually solve the problem, okay?

You understand it.

You, you have, you know, you know all the facets of these problems.

You know that you have a feasible solution, you know that you, you can solve

this problem.

Then you go to your boss and you say look you know, I have a solution

You know, and, and, look, this solution is

improving the practice in this company by 20%.

You know, this is great, you know, you come to your boss and

you get him excited, and your boss say wow, wow, this guy went fast.

Of course, your boss is probably not stupid.

He's going to say, hm, if he did that in a

week or in two days, he probably can do better.

So he's going to look at you and say, yeah yeah but can you do better than that?

Okay, and that's the second step.

And the second step is about looking at your

greedy algorithm, or whatever solution you came with first,

and trying to analyze it and trying to see,

to, to, to see if you can do better, right?

And typically you are going to move to more sophisticated solution when

you do that, CP MIP, you know dynamic programming, local search, whatever.

Okay, and so in this particular case, you will

try to improve, you know, what you had before,

but you have a baseline that you can compare

to at this point and see how best you can.

And so you can go back to your boss and

say, wow boss, you know, I have a 30% improvement now.

And so your boss is going to say, wow this is great.

And then of course he's not completely stupid you say, this guy improve

it by 20%, and now by 30% more, so when are we going to stop?

You know, how long, you know what do I know, okay?

And this is the part where it's probably,

you know very important for you to relax, okay?

And try to find, you know some quality guarantees that you can

give to your solution.

Okay so you want not only to find good solutions, but also

find, kind of a way to say, how good can I be?

Okay?

And so these are essentially the three phases that you can go through.

Start, you know, easy.

Okay?

Solve the problem, see how best you can solve the problem, then improve.

And then afterwards find optimal solution, or find you know something

that tells you, that can tell you how good you are.

Okay?

So start simple, you know, build on it, and

you know, make sure that you can

progress, you know into more sophisticated solution, okay?

But start easy, so that you know what you're doing.

Okay, so in a sense what we

are recommending, you always start with something easy,

and then you have two approach, either

a quality based approach or a scalability approach.

And I'll come back to this but some of the problems that

you will encounter are very difficult to solve for very large sizes.

So you would have to look at very scalable solution to get good solution

to, to some of these larger instances.

On the other hand, some of these techniques

may not give you the best quality solution.

So you may look at Constraint programming or

Mixed Integer Programming to actually get better solution.

And of course, what you al, we also

want is that you actually use both approaches, and

potentially combine them to get very high quality

solution on some, on all of the instances, okay?

So in a sense, once again, this is about starting

slow, and then building using the blocks that we do,

hats that we are giving you, and trying to

get to, you know, really high quality solution everywhere.

Okay?

So the grading, you know, once again.

6:02

The grading is going to be based on the

recognition that there is no silver bullet in optimization.

Even for us, when we are giving a new problem it's

not always obviously clear, you know, what is the best solution?

And what is going to scale and how we model

the problems and, you know, what we can expect, okay?

So in a sense, the assignments

that you are going to see here are intentionally insane, okay?

So they are going to make sure, that

one particular assignment, you know one technique is

not going to work for all part of the

assignments unless you are really, really really clever, okay.

But most of the time, some of the techniques will work on

some of the instances, other techniques will work on other ones, okay.

It's done on purpose.

So that to get a sense of not only exponential growth,

but also the fact that, wow the structure of the problem is

really important. Okay?

And so, so this is the insane part, but we are also very flexible, okay?

So we give you ways to succeed, and different ways to succeed, okay.

And you can for instance take a scalability or, you know

a quality approach, and they will be both fine in the class.

You can say okay, so I'm only focusing

on scalability, and trying to get solutions to everything.

Or I'm going to try to get the best solution

to some of the instance and, and you know,

kind of solutions, you know, maybe not high quality solution, on the other ones.

There are, these two ways are going to be

ways to actually be successful in this particular class.

Let me give you a little bit of a sense of this

of this, of these two ways of actually approaching the problem, okay?

So when you look at the particular problem and let's say,

so typically we six part in every one of these problems.

Let's say that four are reasonably small,

two are really large, okay?

So if you do a, you know a, qualitative, but if you do an approach which

is based on finding high quality solution, you

may get the top grade, like say ten, okay.

On four of them and then a low grade on, on, on two of them.

And that's going to give you an average a,

a value of 46 on that particular assignment.

And that's a, that's a number for which you can get a certificate of completion.

You can also do the opposite thing, which is okay, so I'm going to focus on

scalability, get good solutions, okay, like you

know seven, on all of these problems.

And you get 6 times 7, which is 42 Which is also enough to get you a certificate.

Okay, so these are the two ways to do this, okay.

An, and this is the two way you can actually get a certificate in the class.

If you want a certificate of distinction, you probably need to combine these two.

Now, one of the real thing that I wanted you

to focus on is that first get good grades, okay?

So don't

focus on getting tense everywhere.

You have plenty of opportunities, and I'm going to talk about how to

approach the class from a, you know, time optimization standpoint in a moment.

But try first to get good grades everywhere.

And then beef them up.

You'll see you have a lot of opportunities to do that.

Okay? So, and, this is the key point, okay?

So, so, if you take the first assignment, don't get obsessed, okay?

It's very easy to get obsessed in optimization.

You see this thing, and you want to get a ten.

You see another guy getting a ten and you say, oh, you know, I have to get a ten.

You know, you get, you know, completely frustrated.

Don't.

Okay?

Maybe the person knows more than you do, okay, at this point.

Okay, but this class will give you everything you need to get a ten.

Okay?

It's just going to come over time.

So you can go, do these assignments, get

sevens, so you'll, and be pretty happy, okay?

And then at the end, you say hm, but this techniques, I could apply to this first

problem that I actually solve.

And now I know exactly how to solve, you get back

to it, and in like two minutes, I mean, I'm exaggerating, right?

So you get a time, okay? So this is what this class is all about.

You're going to learn things, and then you can go back

in the past, fix your solution, and get much better grades.

Okay, so don't, don't get stuck on a particular problem.

Don't get completely obsessive, okay?

So in the past, some people have become so

obsessive that, you know, it was like way to,

you know, cool them down, okay? So we don't want that to happen.

Get good grades, come back to the

assignment, and get better grades later on.

Okay?

So, so you will have a lot of time also at the end.

I mean not a lot of time, a reasonable amount of

time to go back and fix the solution at the end.

There is a buffer at the end, just for you to do that.

And a lot of people are basically exploiting this.

Okay, so let me, let me, let, let, let me then

talk about one last topic, which is how you should approach this

class, such that it's, if, you know, you keep a reasonable

level of happiness during, you know, the time you take this class.

You still get a social life, you still are in a good mood,

you don't lose all your friends, your spouse, and all these things, okay?

And so let me give you an analogy, okay.

So the analogy is, you know, last year, well, no, in 2013 when, when

actually Raphael Nadal won Roland Garros, he

was interviewed by, you know, somebody in the

tournament, and they were asking me, how does it feel to win the tournament?

And Nadal, you know, this great tennis champion said, well,

you know, I'm going to be happy for two weeks, it's great.

And so you see this guy training like a beast for

50 weeks and then he's happy two weeks of the year?

This is terrible right?

That, I don't want that to happen to you. Okay, so look at this graph.

This is your level of happiness.

It's also your level of confidence technical

confidence in general. And, so what you will see here is time.

And this is the time during the class, okay, or during an assignment.

And you will usually start with, you know, a lot of confidence, a lot of

happiness, you come there, you design this

amazingly beautiful solution, and you start coding it.

And then as you code it, you know, and you fix things, and you

fix things, your level of happiness is

decreasing, your level of confidence is decreasing.

You kind of get desperate, desperate.

You know, it's a pain to actually work on this, and this, and then at

the very end, wow, you get a big high, because this thing's turned out to work.

Okay.

No, so, this is essentially what Raphael Nadal is experiencing.

He's training like a beast, and then he has these two weeks where he's happy.

For you, it's going to be basically, let's say a week

of work and then, two minutes where you will be happy.

We don't want that. Okay?

Because you will have to, you know, go

that, do the next assignments at that point.

We don't want, that's not what we want

you to do, okay?

So what we want you to do is something like this, okay?

So you start, you know, at the reasonable level of, of happiness and confidence,

and then you start building something which

is easy, let's say a greedy algorithm.

Your confidence decreased, but not very much, because this is pretty simple.

And then you get a solution, and you get a first high.

And you say wow, okay.

So hm, I'm happy, you know, I have something

that works, you know, and you say, good, okay.

Then you start looking around,

you see, oh, but maybe there are people

with better solution, maybe I can improve this.

And you start coding, let's say, local search solution.

And so it takes a little bit of confidence away from your level of happiness.

You have to work a little bit harder. You don't see your friend as much.

But then you have another high.

You know, wow.

We have a really good quality solution at this point.

And you say, oh wow, now this is good, this is good.

Now you have a lot of confidence, see here your confidence is increasing.

And you say,

oh no but now I want some kind of guarantees on how good I am, okay?

And you say oh, let me try a MIP approach to actually get that guarantee.

That's a little bit tougher.

You know, your confidence and your level of happiness is going to decrease.

But you know it's a very short amount of time here, and then wow, a big high.

Now, I know how good I am, right?

And you said, this is good, this is good, another high and, you know, even higher.

But you say, well, but this MIP solution for

this [UNKNOWN] problem is like a dog you know?

Let me

try CP to actually do better in terms of efficiency.

And then you get the final high, where you get this beautiful CP solution at the end.

Okay?

So, this is what this class is about.

This class is about being high all the time, legally high.

Right? All the time, right?

So this is what we want.

The dips are very low, the peaks are high,

and that's the best way to actually approach this class.

Don't wait until the last moment to experience this kind of satisfaction

at the end. Okay?

So do this like that.

Okay, so have fun, you know it's insane, but it's a

lot of fun, especially if you do it the right way.

Okay.

Don't get frustrated, you can always come back,

you have a lot of opportunities in this class.

Okay.

Enjoy it. Thank you very much, guys.

[BLANK_AUDIO]