0:00

Okay guys, Discrete Optimization.

Â This is this is a transition lecture to tell you about how to explore

Â the material, and what is, you know, going to happen in this class, okay?

Â So I want to tell you about how you can explore the rest of the material.

Â And I want also to tell you how you can study, and how you can

Â do the assignments, and, and the various ways

Â you can be successful in this class, okay?

Â So it's something where, you know, I basically want to give

Â you all the options that you can have.

Â And we have designed this class in a such a way that you have a lot of freedom.

Â We are all about freedom in this class, okay?

Â So first, you know, we want to congratulate, to congratulate you.

Â You have made it this far.

Â But, you know, I also want to set expectations, right?

Â So this was the easy part of the class, right?

Â So you got the Knapsack assignment.

Â We gave you the algorithm.

Â It's the easy part, okay?

Â So what is going to come next is a nightmare, okay?

Â It's going to be amazingly hard, okay?

Â We won't give you the algorithm.

Â We're going to give you the techniques that you can use, all these hats.

Â But we won't tell you which one to use.

Â We won't tell you how to use them.

Â And we're going to make your life as mis, miserable as we can, okay?

Â So that's the goal, okay?

Â So essentially we give you three kinds of techniques that,

Â that you can apply: constraint

Â programming, local search, and mathematical programming.

Â They are beautiful techniques, okay?

Â So, but once again, when you get a problem,

Â you will not know exactly which one to use, okay?

Â And so

Â part of this class is about you getting an understanding of these techniques, and

Â finding out which ones are good for which problems, and which one to apply, okay?

Â 1:25

So this is essentially how the course is organized.

Â It's completely open. We give you all kinds of freedom.

Â So you have seen the intro of the material.

Â And then, essentially, in the chronological organization, you know, we

Â give you CP, and then local search, and then MIP.

Â But there

Â is no reason you need to follow that, okay?

Â So you could jump from one to the other.

Â You can start with another one.

Â You can do all kinds of things.

Â You can look at the introductory lecture for every one of these three,

Â then go deeper in some of them, and so on and so forth.

Â You have entire freedom to actually explore this material.

Â It's not going to disappear, unless something

Â really bad happens to Coursera, okay?

Â But this is going to stay, and you can explore these things the way you want.

Â And it is the

Â same thing for the assignments.

Â We are going to give you a bunch of assignments.

Â And once again, there is a specific order which we think, you know, makes sense.

Â But there is absolutely no obligation to actually do that.

Â You can do assignments in a different order.

Â Or, more, more likely, what you can do is start working on

Â an assignment, having some initial solutions

Â to them, and then leave them alone.

Â Start anther assignment, and then you become smarter and smarter.

Â And then you can decide oh, but no, I can go back

Â to this assignment and do a better job. And you can do that all the time.

Â You are graded on, you know, at the end.

Â Not at the beginning, not when you, when, when the, the initial deadlines are.

Â So you can always go back and re-find these things.

Â Complete freedom, okay?

Â You can do whatever you want, okay? Isn't that nice?

Â Okay.

Â So one thing that I want to tell you also is

Â a little bit of background knowledge of the various optimization techniques, okay?

Â And once again, I'm going to exaggerate.

Â So what I'm telling you now is a real lie, okay?

Â But for beginners, it's, you know, it's mostly true.

Â Even for sophisticated users, to some extent it's true.

Â But this is going to help you and actually figure out how you can get,

Â you know, how, what are the various things that you can do in this class?

Â So if you use techniques, you know, global techniques, techniques that are

Â guaranteed to find the optimal solution if you leave them enough time, okay?

Â Like CP, like MIP, like dynamic programming.

Â What you will get

Â is typically a method that will give very high quality

Â solutions, optimal solutions in general, if you give them enough time.

Â But they won't necessarily scale that well to huge

Â problems, problems of very large size, or sizes, okay?

Â So in a sense, this is something that, for a

Â number of problems, is going to give you an optimal solution in

Â this class, but for other problems is going to be very,

Â very challenging to actually find optimal solutions using these techniques, okay?

Â Local search is the exact opposite.

Â It's going to basically scale very well if you implement it correctly, but it may

Â not give you the best solutions all the time, or even a high quality solution.

Â It depends really how you implement it, okay?

Â But it's a completely orthogonal way of looking at the problem, okay?

Â And of course, you know, this is one of the hot topics in optimization these days.

Â Hybrid algorithm will combine these two things to actually give

Â you solutions which are of very high quantity, for which

Â you can actually give the quality, balance

Â on the qualities, and things like that, okay?

Â So this is like the, the Holy Grail of optimization these days, okay?

Â And so, you know, you can actually do these three things.

Â We don't expect you, everyone, to kind of do hybrid algorithms.

Â They are very sophisticated.

Â We'll only talk about some of them in this class at the end.

Â But you can use different techniques for different parts of an assignment.

Â I'm going to come back to that, okay?

Â So keep this picture in mind when you are trying to solve the problems.

Â And don't get frustrated, right?

Â So if you try to apply a technique like

Â this to really huge problems, you may get into trouble.

Â And this is fine.

Â We want you to get into trouble so that you get the intuition, okay?

Â So there are many ways you can be successful in this

Â class, and I'm going to give you some of them right now, okay?

Â So there are many things you can do.

Â Once again, it's about freedom and exploring many different things, okay?

Â One of the things that you can do is to say, okay

Â I'm going to use one technique, for instance, and apply it to everything.

Â And of course I know that I'm going to sacrifice

Â something when I do that, but you can do that.

Â Or you can say no, I want to understand this material, you know, like crazy.

Â And I will apply all the techniques to all the problems.

Â You can do that as well, okay?

Â And all these approaches are going to be successful in some fashion, right?

Â So for instance, assume that you want to focus

Â on one of the techniques, like MIP, or CP, okay?

Â And you want to apply that to all the problems, okay?

Â So this is like what we call a solution, you know, a quality based solution, okay?

Â And what you do there is that for some

Â of these problems, these approaches are not going to scale.

Â So you won't be able to find the optimal solution.

Â So when you look at the particular problem, okay, the particular

Â assignment, most of these assignments will have about six parts, okay?

Â And the complexity is growing.

Â The size of the instances are growing, okay?

Â So if you do a solution a method which is based on, on finding very

Â good solution, optimal solution, you are likely going to

Â get optimal solution to some of these instances,

Â let's say four of them, where you will have the maximum grade.

Â And some lower grade for, you know, the, the largest

Â one, because that approach is not going to scale up, okay?

Â You would get 46 points, for instance, okay?

Â Now if you do local search, for instance, you're going to scale nicely.

Â But you won't find the best quality solution.

Â And so let's say you would get a seven for all these six instances.

Â And you will get something which is like,

Â you know, 42 points for that particular assignment.

Â Both of these things,

Â you know, 42 and 46, are sufficient for you to

Â get a certificate in the class and pass the class, right?

Â And so this is nice.

Â Okay, you can do that.

Â Of course what we want you to do, really,

Â you know, deep heart, you know, deep inside your heart,

Â is that in, you know, is basically you finding

Â top solutions for every one of them, getting ten everywhere.

Â But that will mean that this is a significant,

Â you know, a more significant investment of your time.

Â You need to

Â actually, you know, use some of the most sophisticated methods on a smaller

Â instance, and then use methods that are

Â more scalable on the larger instances, okay?

Â So these are the various ways you have to, you

Â know, you can, you can try to do this class, okay?

Â So you can look at the material, and try to get a certificate.

Â And that means that you can explore only some of the techniques.

Â So you want, really, to do really well, and

Â you have to use a combination of these techniques, okay?

Â So various ways you can find, you know, you can

Â be successful in this class.

Â Obviously, we encourage you to understand and, and master the whole material.

Â 7:17

Let me give you also some kind of feedback on what are

Â the differences, from a cognitive standpoint

Â in essen, essentially, for these various methods.

Â They, they use different kinds of ma, different kinds of techniques, okay?

Â So constraint programming is all about discrete, dis,

Â discrete, you know, algorithms, discrete mathematics, solving puzzles.

Â It's essentially

Â a generalization of solving puzzles, and of course it's a very nice generalization.

Â It's beautiful.

Â But this is something, you know, if

Â you like discrete math, discrete algorithm, this is,

Â this is where, you know, this is something

Â that's going to resonate with you very well, okay?

Â Mixed integer programming is also beautiful, but is very different.

Â It is based on continuous math, linear algebra, and things like this, okay?

Â And, and it has its own beauty.

Â But it's a very different way of thinking than, than,

Â than, than constraint programming.

Â So this is about, you know, pruning the search base.

Â This is the goal, this is going to be

Â about finding really clever relaxations, and things like that.

Â And we'll talk about these topics in detail, right?

Â So in practice, both of these things are very octogonal.

Â And, and, you know, it's, it's very good to know about both of them.

Â But they require very different kinds of backgrounds, which is nice, you know?

Â Optimization, you get to touch on, you know, upon many, many topics.

Â And then local search is this completely different

Â framework, which is very intuitive, you know?

Â When, when I give my kids, you know, some of

Â these puzzles to solve, they will always do local search.

Â They, they put things around and try to fix them.

Â That's what local search is about.

Â But it's also, it, you know, there is also a very systematic theory that

Â will go, we're going to go over later on in the class as well, okay?

Â So what you have to do here is, is much more intuitive.

Â You can see things, you know, and, and

Â they correspond more to your intuition, at least initially.

Â But they may require a lot

Â of programming experimentation compared to some of these techniques, where

Â we'll have more support if you use, you know, available solvers.

Â