Okay guys Discrete Optimization, Mail Bag Week 1.
So so whatever we are going to do, we're going to try to do because some of us may
be travelling during some of the classes. it's basically giving you some update,
weekly update as we can of what's going on in the, in the class.
As you know giving you feedback, you know, answering some of the questions and
so on. Okay, so that's what we going to do
today. the first thing that I want to say is
that's it's pretty cool to see all you guys actually doing these assignments
and, you know, interacting on the forum. This is really, this is really cool.
For the first time in this class we're actually realizing that there are people
we are talking to, right? So so this is a little bit of the
statistics. There are about 17,000 students active.
in the class. 10,000 have viewed the, have viewed the
introductory video. these are the completion of the
assignments, so the screen name assignment, which was really tough,
right? Was it was about 4,500 students.
Knapsack we have more than 2,000 people completed, completing the knapsack
assignment and rough coloring at this point, although it's due in a week time
is about 250. Okay you know, a week time from the time
I'm basically speaking, right? we have a lot of auditors which is
typically common in these massively online courses, this is not to worry
about. this is essentially the overview of the
student body by country. There are some interesting things here.
so the three top countries are the US, India, and Russia.
Okay well, you know, you would expect something like.
this is actually a picture of the entire world okay with a various countries and
the number students in every one of the countries.
It's a very nice coverage so we would like to encourage from, you know, that,
that is not covered. You know, why is everybody not interested
optimization in Greenland lot of in Africa?
some tiny places in in South America, some in the middle of you know, Asia and
so on. I mean, it's kind of an interesting map.
This is the US, okay? So, a lot of people in California and
nobody interested in discrete optimization in Wyoming.
So if you know somebody in Wyoming, tell them just to register to the classes so
that we feel good, right? So nobody in Wyoming, why?
What is happening in Wyoming? Actually, I, so this is India, this is
where a lot of people in India are actually are actually taking.
Well, at least looking at some of the lectures in their, in their, in their
class, okay. So some inten, intense activity in this
part of India, okay? You can guess which one it is.
this is like, you know, part of Europe and part of Asia, okay?
Other part of Asia, okay? And you see once again the various
activities of the various countries. There is a tiny little things here, very
interesting, right? So, what is this thing?
I have no clue. anyway so, so there are four you know,
about 4,500 student active. That means students who've actually
submitted some assignment, okay? So overall, there were 50,000 submission
made. This, this is actually really, really
interesting. I mean, we are really surprised that so
many submissions have already been done, okay?
For the knapsack assignments there are more than 2,000 people, students active,
okay? And for the graph coloring assignment,
although it's due in a week from the time I'm speaking, there are 250 students
active right now, okay? so we're going to also give you progress
by the various part in the statistics and, and so there are six parts for
everyone of the assignments. And on track is going to be this
completely crazy standard where essentially you basically very high
standards. Where you have basically 7 to 10 on every
one of the parts, okay? So, you are like, you know, the people in
that track are certain to have a certificate at the end, okay?
So, this is like doing, doing really great work on every one of the parts,
okay? So, this is essentially the assignments
part per student. So, the students who submitted various
assignment. Of course, in this particular bar there
is also the screen name, so that's the The highest.
But you see people completing a lot of the possible, in that side, you know,
about 59 [UNKNOWN] students have completed six or more parts here, okay?
So, that's what you see over there. And obviously, what we want is to take
this line over here and move it over there.
And move all these, you know, body of students, you know to the right, okay?
So, this is this is the same statistics, but for students who are on track, okay?
So, what you see is that there are lot of students here which are close, close to
completing knapsack, okay? We're just going to pull them a little
bit. Such that they, you know, all these
people go over the line, okay? Remember it's a tough class, okay?
So, you don't have to have a perfect grade on everyone of the parts to move
on, okay? So, sometimes you can move to the next
assignment. You have to balance that, right?
So, you can move to the next assignment, okay?
and, and try to do the next assignment, and then you can always come back to
Knapsack and try to get a, you know, a better grade.
On, on better, you know, grade on some multiple part if you have a seven and you
want really to get to 10. So, try to balance the time you spend to
the assignment, you know, to the, to the, to the grade that you have, okay?
So common question that we saw on the, on the forum, is there a mistake in the
dynamic programming table in the knapsack lecture?
Yes. Okay, once again, once we found the
mistake or once it's reported, we typically try to correct it in the slide.
It's discussed in many of the forum, it's discussed in the Wiki and things like
this, okay? So that, you know, when you see some
mistake, go to the forum, check if it has been reported or not.
You don't have to repost or you don't have to or your don't have to you know
you don't have to, you know, what until we answer.
Most the the time the answer is on, already, already going to be there.
so there was some interesting questions on how we test various assignments, okay?
So we give you a lot of instances, but we test on all of them.
But we are not completely stupid so we don't tell you which instances we are
testing it on. so otherwise you could tailor everything
you do to those specific instances. So, we choose a random set of instances
from the set we are giving you. So, if your program does well on all the
instances you find, okay? Otherwise, it's going to be on some of
these instances that we're going to test the your assignment, okay?
So, you know, we could do even worse than this, right?
Give you some instance, and test on another test of instance.
We don't do that. That's the right way to do it, but here
we give you, we try to make your work, you know, simpler.
We give you all the instance. If you do well on all these instances,
you are guaranteed to do very well on, on the grading.
so when, when you get out, you know, a feedback which is, which seems to be
wrong. You know, check, check the order of the
variables, and make sure that they match essentially the import order that we
expect, and things like this. Once again, you know, when you see your
assignment and you see the value of your objective function.
You can always go the leader board and see how people are doing, okay?
So, this is what is nice about this leader board in a sense.
What we give you the value of the objective function.
You can always see how well you do. If you do, if you're, you know, like 10
times better than, you know, everybody else, probably that means something is
wrong. If you are very low and you, you get a
low grade, if you get a low grade, you can see all of the people have actually
done better. And that, you know, it can motivate you,
okay? So, so one of the things that this class
does is, you know, trying to encourage some competition.
You can always see how well the other people are doing.
Now on the knapsack, it's reasonably easy.
On graph coloring and other problems, it becomes much more interesting because
some of these problems. It's very hard to actually find the
optimal solution, graph, in graph coloring in particular, okay?
Now, some people ask why branch bound for the knapsack problem can still be can it
still be a exponential does it behave exponentially what are the typical case
where it would be bad, okay? So, I'm going to show you some examples
here, okay? So, once again, you know, if you want to
find out if something is working well or not if an algorithm is working well or is
not working well. Most of the time, what you have to do is
exaggerate. Try to find a case which seems to be
crazy and study hard the algorithm is working on it, okay?
So, I'm going to assume here. Let's look at the problem for branch
bound where we have a lot of items, right?
But, they have all essentially the same ratio between the value in, you know, in
the objective function, the profit, and then the weight, okay?
So, assume they look all very very similar, okay?
So, what's going to happen is that the branch and bound is going to basically
explore many of the possibilities. Many of the combinations of these item.
Why? Because the lower bound here in the
branch and bound is not going to be able to differentiate them.
So, let me give you an example. Assume that we have a knapsack of
capacity, you know, 701, okay? The one is very important, okay?
So, then you have the item weights, okay? And I'm giving you the item weights,
which are basically 2, 2, 2, 2, 2, 2, 2, 2, 2.
You know, huge amount of 2s, and then a 1 at the end, okay?
And then, I'm giving you the item volume. Which are basically almost all the same.
You know, a rate, I'm going to give you a ratio which is very, very similar.
So we have the volume of the item which is 2.00001, and then all this huge number
of items is like that. Except for the last one, okay?
The one that you see there is going to be 1 as well.
So, the ratio, essentially is mostly, you know, 1.
Except that you have 1 plus epsilon for this huge amount of items, okay?
So, you know, you need to think about what is the linear relaxation going to
do, okay? So remember, this is, you need, well, you
haven't seen those lecture yet, probably. But this, you know, the, the relaxation
that we have, okay? Here is, is going to do something very
interesting, okay? And you have to think about what, what it
does, okay? But essentially, which are the items the
most, which are the most valuable? That's the one with a two, okay?
They are barely more valuable than the one with a one, okay?
But since the capacity is, you know, 701, you will have to take item one at some
point, okay? So, so that you really match the
capacity, okay? So if you take an item two, you will only
be able to take a fraction of it, okay? So in a sense, so you, you can see all
the combination. We can take many, many, many, many of the
computation of the twos, okay? Of the, of the items which have a two.
And, but, and, and we go to ignore the 1 essentially until the very end.
In general, if you, if you, if you order them, let's say by value, okay?
Which is typically what the reaczation is doing, right?
And so you, you can see, I know, you just should, you should do the exercise of
seeing what the branch and bound is going to do, okay?
And it's going to be pretty bad on the instances like this, okay?
So in a sense, if you have a very large capacity, all kinds of, you know, items
that are very tiny and we say, most follows the same ratio.
The branch and bound algorithm is likely to spend a long time, okay?
That's so you get exponential time in this particular, in this particular
context. Of course, there are ways around it,
okay? And when you get to the mixed integer
programming lecture, you will see that we actually give you some ways of actually
overcoming this this thing. So, there is a way to fix the branch and
bound such that this doesn't happen. So, I'm giving you some kind of
indication that there are techniques that we'll see later in the class that can fix
this. So, it doesn't mean that all of the
branch and bound algorithms are going to behave badly.
I think that what is presented in class for an example is going to behave badly,
okay? So some suggestions you know, before
reporting a, a, a problem, okay? So, check the forum, okay?
Check if the problem has been reported. You know, if you have, if you believe you
have an issue, go and see the forum of the week to see if that problem has
reported already, okay? check the Twitter account as well for you
know, some of the announcements that we make.
If we find, you know, mistakes in the slides, we would report them there as
well, okay? use the course Wiki.
We're going to tell you where it is, okay?
So, this is the resource column here that you see.
Go through course Wiki over here, and then you, this is the page that you see.
And this is where you know we put the, you can put, we put corrections, you can
put corrections. There will be some implementations and
things like this, okay? So, you can use that, use these
resources, okay? So, once again, there're lot of resources
in the class in the, on the website and you should actually look at them all the
time. no one of the things I told you many
times is that this is a hard class and the knapsack assignment is a warm up,
okay? So, it's the easiest assignment.
Rough coloring is actually is pretty difficult.
Rough coloring is really the assignments when you'll experience exponential growth
okay so it's very difficult to find optimal solution.
It's very difficult to prove optimizing, okay?
So, it's going to be the first experience where you will really see that, wow,
these problems are really tricky, okay? It's really difficult.
At the same time, you can find very high quality solution and, you know, the
leaderboard is going to tell you how good you are doing.
And in general, you know, what, what, what we found is that in this class there
is a wide variety of solutions, okay? That people are going to produce, they
can use very different techniques. And but, but the quality is going to, is
going to differ. typically the run time is going to differ
as well, but in this class we basically don't, you know, we, we, we don't check
the run time, okay? so, so coloring is hard as I just said,
and finding an optimal solution really hard, proving it even worse, okay?
So once again, what you have to remember is that you don't have to have the
ultimate solution. And prove the ultimate solution to, you
know, get a certificate at the end of the class, right?
So, 7 to 10 is fine. And we, we have reasonable standards.
That doesn't mean that this is easy, right?
So, that we don't expect you to find and prove optimality on these problems.
Now if you you know, if you find and prove optimality on all the benchmarks
that you have. Just give me a call.
Don't tell anyone, just give me a call, okay?
good news, okay? So, the, the graph coloring assignment is
covering many of the lectures to some level, okay?
so you have it in constrained programming.
Mostly what I recommend is that before you actually try.
If you use constrained programming, okay? So before you actually try it, you know,
look at, you know, Lecture from 1 to 5 at least.
Six is also useful if you want to be really clever, okay?
So, that's what I would recommend before you try look at these lectures, okay?
Up to Cp6, okay? It's also covered in one of the local
search lectures section number four. Once again, go a little bit further and
look at the metaheuristic lecture. That's when you can get a lot of clues on
actually solving this using local search, okay?
So, this is what I would recommend for people who are really brave, okay?
So you can look at, you know, advanced techniques in mixed integer programming
as well. But this is really advanced for this
particular problem, okay? so thanks for all the feedback that you
gave us, okay? We work very hard, we try to respond to
all the questions as soon as possible. You know, keep going, I think we'd like,
we'd like to take this, you know, this red, red line and move it, you know, to
the, to the right, okay? and we'll be back next week with more,
you know, answers to your questions and more feedback on the class, okay?
Thank you guys, keep the good, keep the good work.