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.