This is supplemental material on the 
knapsack assignment for discrete 
optimization. 
And so, you remember the knapsack, right? 
So you had all these beautiful, very, 
very valuable artifacts, and you wanted 
to pick out the subset of them that you 
could put in your knapsack and run away 
as quickly as possible. 
obviously, you know, you want the highest 
value, and, but you also have the 
knapsack capacity. 
That's the first assignment that you will 
have to solve in this class, okay? 
And this is a formalization, very much 
the same thing as we saw in the lecture. 
So, you have basically, an item. 
For every one of these items, you have a 
value that's how much the, you know, the 
item is worth. 
You have a weight, which is, you know, 
the weight of the item. 
And then obviously the decision variables 
are going to be for every one of the 
items, whether you take it or not. 
Whether you put it in a knapsack or not. 
Okay? 
So it's a maximization problem, you 
maximize the value of the items that you 
will select. 
The sum of these, you know, of the weight 
of these items cannot exceed the capacity 
of the knapsack. 
And for every one of the items, you have 
to decide whether you take it or not. 
Okay? 
Very simple. 
Right? 
Now obviously when you look at these 
things you know that any particular 
instance of that problem will have to 
provide a set of input. 
Okay? 
Obviously we have to know how many items, 
okay. 
We have to know what is the capacity of 
the knapsack. 
These are two constants. 
So you see these two constants already. 
Okay, here in the input data, okay. 
So we have the number of items and the 
capacity of the knapsack. 
Okay, n and K are the first two things 
that you'll find in the input data file. 
Okay. 
And then afterwards now you know how many 
items there are, there are. 
So you would see a long list for, you 
know, for every one of these items. 
And for every one of them there will be, 
you know, two information that you need 
to give, okay. 
The value of the item, which is going to 
be the first value there, and then the 
second one is going to be the weight, 
okay. 
So your input file okay, once again, is 
going to tell you how many items there 
are. 
What is the capacity of the knapsack, and 
then a long list and for every one of the 
items okay, there will be an entry in 
that list. 
And it gives you two values, the, the 
weight of the, the value of the, of the 
item and then the weight of the, the, of 
the item, okay. 
so that's the input. 
Obviously we would expect you to submit 
something. 
Right? 
At least, you know, if you want a grade. 
Okay? 
And essentially, this is the format that 
we expect you for this particular 
assignment. 
Okay? 
You're going to give the objective 
function. 
You're going to give a flag which is opt, 
and I'll come back to that in a moment, 
but this is a zero one value. 
Okay? 
And then you will basically output the 
solutions. 
And in this particular case, it's 
going to be a long list of zero and ones. 
Okay? 
Telling you whether, you know, this item 
has been selected in the solution or not, 
okay? 
If we have n items, okay? 
There will be n entries inside that list. 
Okay? 
So this is a very particular example, 
okay? 
So what you see here. 
This is essentially a knapsack problem 
with four item. 
Really challenging, right? 
And the capacity of the knapsack is 11. 
And then what you see in this list is 
the, the values and the weights of every 
one of the item. 
Okay, so the first one has a value of 
eight and a weight of four, and the 
second one has a value of ten and a 
weight of five. 
Okay. 
And so this is, this is an example of 
input data file. 
Okay. 
So you can expect to have some that will 
be a little bit longer than this one. 
And this is your output here, you are 
basically saying, oh, this is a solution 
which has a value 19. 
This is a, the, the sum of the value of 
all the item. 
I have absolutely no clue whether this is 
optimal. 
That's why you put a zero there, this is 
this flag. 
This flag is telling you I don't know if 
this is optimal, I haven't proven it. 
Okay? 
if it's a one that means that oh, I have 
proved that this is the ultimate 
solution. 
And then you see the particular solution 
here. 
Okay? 
The solution here is zero zero one one 
which basically means that I select item 
three and four. 
If you look at item three and four, you 
see that the value is indeed 19. 
And then you see that the capacity is 
indeed 11, so this is a feasible 
solution. 
Though, as I told you many times, this is 
one of those beautiful features of 
NP-complete problems. 
Okay? 
I can check very quickly. 
If what you submit is actually a 
solution, okay. 
And obviously I can very quickly compute 
the objective function. 
Okay. 
So this is what I can always do, you 
know, when you are submitting an 
assignment. 
Okay. 
Now, how do you actually implement the 
assignment? 
Remember, you know, we talked about these 
two, you know scripts, Python scripts, 
that we have. 
The first one is the solver script, which 
basically is the core of your assignment, 
okay. 
So what you will have is essentially, you 
know, the input and the output and then 
in the middle your solver. 
Okay, so when we provide this script, 
we'll always have some code that outputs 
are completely simple solution, in 
general. 
Okay? 
And so, so we'll take the, so the input 
is going to basically be this file here, 
okay. 
Giving you all the data that you need to 
compute it. 
And basically the first lines here are 
basically parsing that input data to 
output a very simple solution in the 
script we are giving you, okay. 
Obviously you want to, you will want to 
replace this simple solution with 
something which is you know, much more 
sophisticated. 
And then the last part here, you know 
what you're computing here, what you're 
outputting there is basically the output 
and this output will have to have this 
format. 
Okay? 
So this is the critical part here. 
Okay, the output, the out, sorry, the 
output here. 
The output here. 
Okay. 
So, essentially, so what you see, once 
again to summarize, you have an input, 
you parse the input, you have the output, 
okay, that you generate, and they have to 
correspond to these two formats that you 
have. 
In the middle we provide you some code 
which is actually outputting a very basic 
solution, and that's where you put your 
solver, okay. 
Now, your solver doesn't have to be 
implemented in Python, okay. 
Some people may want to do that, other 
peoples may, you know, not want to do 
that, okay. 
So you can actually call different 
processes, you know, inside, you know, 
inside this python script, such that you 
can call your Java program or your C 
program or, you know, whatever language 
you like. 
Okay, and typically this is, this, this 
will be done by, you know, coding a 
different process here. 
You will open a process okay, telling you 
which language you want to use and, and 
various processes for that, various files 
for that languages. 
Okay? 
And then you can, and obviously you know 
what you see here is that we selected 
Java. 
And this is going to be the Java code for 
actually running your solver. 
Okay? 
So, in a sense, what is happening here is 
that the input is, you know, the input of 
the Python script is going to be 
transmitted to your Java program. 
And obviously your Java program here is 
going to output something which will be 
transmitted to the Python script. 
Okay? 
So, in this particular case, we used a 
very simple ways, simple way of doing 
this. 
We used a standard output. 
So that, you know, Java is outputting on 
the standard output and Python is 
retrieving that, and generating the 
output solution. 
But you can do that in many different 
ways. 
You can use a, you know, a database, you 
can use potent you know, a file, you 
know, whatever you want. 
But essentially at some point, the Java 
program has to tell the Python program 
where the data is. 
You know, Python should actually get that 
data and output it in exactly, you know, 
the format that we expect for grading the 
assignment. 
Okay? 
So, basic messages here, you know, you 
basically change this, this, this you 
know, solver script such that you call a 
server, or you implement your server in 
Python. 
Okay? 
And then, you output the data in the 
right format. 
Okay? 
Once again, you know, we give you a lot 
of this infrastructure. 
We show you how to parse the data. 
We show you how to, you know, format the 
output. 
And we also show you a basic, you know, a 
basic solution for actually computing a 
solution. 
But most of the interesting part is 
going to be for you to actually replace 
that basic solution and, and, and write 
your own solvers, okay. 
So, testing the solver once again, we saw 
that in the first lecture, in this 
particular case. 
You basically will take your solver and 
then one of your data files, okay? 
So this is the data files, this is the 
data that you saw here, right, okay? 
So that's what you are basically passing 
to the python script, okay? 
And, you know, you run your solver and 
your solver will obviously output a 
particular solution. 
In this particular case, this output of 
solution 18, you know, you have no clue 
whether it's optimal or not, and it's 
not. 
Okay? 
And then you see the solution which is 
one one zero zero. 
Okay? 
So that's how you can test your solver. 
At this point, you know, you know that 
the script is working and you could 
actually submit this solution to you 
know, to the, the course, to the course. 
And what you will do is essentially what 
we have seen in the first, you know, 
assignment. 
You will have to enter your credential. 
You know, the login and the password. 
And then in this particular case, you 
will get a menu. 
And that menu will tell you, okay, so 
these are the various problems for which 
you can actually produce a solution. 
And one of the options that you have here 
is basically choosing the sub-classes of 
problems for which you want to generate 
the solution. 
You can choose the mode if you want, 
okay? 
You can choose two of them or one of them 
or anything you want. 
Okay, essentially, okay? 
So, for instance, you can say, oh, you 
know, the solver that I have is really 
good on, you know, problem three, okay? 
And basically, you choose problem three, 
okay, and at this point, your solver is 
run for problem three, okay? 
You can choose, you know, let's say, 
problem zero or you can choose you can 
choose you know, four and six, and what 
you get is essentially a the, the, your 
summary is going to be executed on any 
one of these things. 
Okay, when you put zero, you test 
everything obviously. 
so the output. 
Okay? 
So, one of these flag that I discussed is 
the optimality flag. 
Okay? 
So, sometimes we'll have a, a, you will, 
you will, you, your assignment. 
Your solver will be able to prove 
optimality when you do so, essentially. 
You want, you, you, you may want to put 
the value 1 over there. 
It's basically telling us that not only 
you found the optimal solution, but you 
actually proved it. 
Okay. 
So we are not using that information for 
your grade. 
But this is something that is actually 
very valuable for us to know. 
And this will appear in the little boat 
and saying, you know, and, and tell the 
world that you have the optimal solution. 
And you have proven that it's optimal, 
nobody can improve what it is. 
Okay? 
so, in the little boat that's going to be 
highlighted by the fact that there will 
be a bold face on the value of your 
solution. 
So you see the solution here, 19, it's 
optimal, okay. 
Now one of the things that you have to do 
is you have to be careful if you put this 
flag, okay. 
So if you put, you know, the optimality 
flag to 1, and your solution is 10.5, you 
are not going to good, look you're not 
going to look good, okay. 
Because there will be obviously solution 
that have, you know, that may improve it, 
okay. 
Also, you don't want to cheat. 
You know, you may have the optimal 
solution, but you may not have been able 
to, to prove it, okay, so don't, you 
know, don't abuse the system, once again. 
You know, just you know, put the right 
value for the optimality flag. 
Once again, your grade doesn't depend on 
it, but it's a useful information to 
know, so that people know what is the 
best they could ever do. 
Okay, so typically when we have these 
assignments video we'll give you some 
tips on, you know, things to think about, 
okay. 
So these are some tips on the knapsack 
assignment, so if you do dynamic 
programming one of the big thing you have 
to think about is the space, okay? 
Dynamic programming when it works is very 
fast, but it may use a lot of space, so 
think about the space that a particular 
solution is using and whether it's 
practical. 
And think about ways our activity we're 
using the space if you can, okay? 
So, this is a critical issue in dynamic 
programming. 
Think about it when you do the 
assignment. 
Okay. 
Now, when you do the branch and when you 
implement a branch and bound algorithm, 
space is not an issue, okay. 
So what is really an issue, well in 
general, okay, so it depends also on the 
search strategy. 
But one of the big things in this 
particular case is actually bounding, and 
finding good bounds, and also computing 
these bounds very fast, because you will 
compute them many, many times, okay. 
So, if you improve the way to compute a 
bound, okay, you improve the overall 
efficiency of the branch and bound 
algorithm. 
So, in this particular way from the 
knapsack problem, think about how you can 
actually implement, okay, the best value, 
the best bounding techniques, and how 
fast you can actually compute it. 
Okay? 
So, good luck, this is your first 
assignment, okay? 
So, you know, you will experience our 
infrastructure and you will first 
experience, you know, you know, 
NP-complete on a very simple problems, I 
must admit. 
Okay. 
Thank you.