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]

Â