Tired of solving Sudokus by hand? This class teaches you how to solve complex search problems with discrete optimization concepts and algorithms, including constraint programming, local search, and mixed-integer programming. Optimization technology is ubiquitous in our society. It schedules planes and their crews, coordinates the production of steel, and organizes the transportation of iron ore from the mines to the ports. Optimization clears the day-ahead and real-time markets to deliver electricity to millions of people. It organizes kidney exchanges and cancer treatments and helps scientists understand the fundamental fabric of life, control complex chemical reactions, and design drugs that may benefit billions of individuals. This class is an introduction to discrete optimization and exposes students to some of the most fundamental concepts and algorithms in the field. It covers constraint programming, local search, and mixed-integer programming from their foundations to their applications for complex practical problems in areas such as scheduling, vehicle routing, supply-chain optimization, and resource allocation.
Assignments Getting Started
Loading...
来自 The University of Melbourne 的课程
Discrete Optimization
224 个评分
从本节课中
Knapsack
These lectures introduce optimization problems and some optimization techniques through the knapsack problem, one of the most well-known problem in the field. It discusses how to formalize and model optimization problems using knapsack as an example. It then reviews how to apply dynamic programming and branch and bound to the knapsack problem, providing intuition behind these two fundamental optimization techniques. The concept of relaxation and search are also discussed.
与讲师见面
Professor Pascal Van Hentenryck
Dr. Carleton CoffrinAdjunct Lecturer
Computing and Information Systems
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.
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]
