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.