0:00

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 up the subset of them that you could put in your knapsack and

run away as quickly as possible.

Obviously, you want the highest value, 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 item is worth.

You have a weight, which is, 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 the 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,

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, we'll 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, okay?

So, you see these two constants already, okay, here in the input data, okay?

So, we have the number of the item and the capacity of the knapsack, okay?

And n, K are the first two things that you will find in the input data file, okay?

And then afterwards, now you know how many items there are.

So, you would see a long list for every one of these items.

And for every one of them,

there will be 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 everyone of the items, okay,

there would be an entry in that list.

And it gives you two values, the value of the item and

then the weight of the item, okay?

So, that's the input, obviously, we would expect you to submit something, right?

2:08

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 0, 1 value, okay?

And then you will basically output the solutions,

and in this particular case it's going to be a long list of 0 and 1s, okay?

Telling you whether this item has been selected in the solution or not, okay?

If we have n items, 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 values and

the weights of every one of the item, okay?

So, the first one has value of 8 and a weight of 4 and

the second one has a value of 10 and a weight 5, okay?

And so this is an example of input data file, okay?

So, you can expect to a sum that will be a little bit longer than this one.

And, this is your output here.

You're basically saying, this is a solution which has a value of 19.

This is the sum of the value of all the items.

I have absolutely no clue whether this is optimal, that's why you put a 0 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 1, that means that, I have a proof that this is the optimal solution.

And then you see the particular solution here, okay?

The solution here is 0 0 1 1,

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

you see that the capacity is indeed 11, so this is a feasible solution.

Now, as I told you many times,

this is one these beautiful features of NP complete problem, 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 when you are submitting an assignment, okay?

Now, how do you actually implement the assignment?

Remember, we talked about these two scripts, Python script, 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 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 a completely simple solution in general, okay?

And 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 will want to replay this simple solution with something which is

much more sophisticated.

And then the last part here,

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, sorry, the output here.

5:13

Okay, so essentially, so what you see, once again, to summarize,

you have the input, you parse the input, you have the output that you generate.

And they have to correspond to these two formats that you have.

In the middle,

we provide you with 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 into Python, okay?

Some people may want to do that, other people may not want to do that, okay?

So, you can actually call different processes inside this Python script, so

that you can call your Java program or your C program,

whatever language you like, okay?

And typically this will be done by coding a different process here,

you will open a process, okay?

Telling you which language you want to use and various files for

that languages, okay?

And then you can obviously, that what you see here, is that we've 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,

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 use a very simple way of doing this,

we use a standard output, so 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 database,

you can use portend a file, whatever you want, but essentially,

at some point, the Java program has to tell the Python program where the data is.

Python should actually get that data and

output it in exactly the format that we expect for grading the assignment, okay?

So, basic message is here, you basically change this solver script,

such that, you call a solver or you implement your solver in Python, okay?

And then you output the data in the right format, okay?

Once again, we give you a lot of this infrastructure.

We show you how to parse the data.

We show you how to format the output.

And we also show you 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 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 the 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?

7:50

And you run your solver and

your solver will obviously output a particular solution.

In this particular case, its output a solution 18,

you have no clue whether it's optimal or not.

And it's not, okay, and then you see the solution which is 1 1 0 0, okay?

So, that's how you can test your solver.

At this point, you know that the script is working and

you could actually submit this solution to the course.

And what you will do is essentially what we have seen in the first assignment.

You will have to enter your credentials, 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 subclasses of

problems for which you want to generate the solution.

You can choose them all, if you want, okay?

You can choose two of them, or one of them, or

anything you want essentially, okay?

So, for instance you can say,

the solver that I have is really good on problem 3, okay?

And basically, you choose problem 3, okay, and at this point your solver is run for

problem 3, okay?

You can choose, let's say problem 0, or you can choose 4 and

6 and what you get is essentially your solver is

going to be executed on anyone of these things.

Okay, when you put zero, you test everything, obviously.

So, typically, when we have these assignments video,

we'll give you some tips on things to think about, okay?

And 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 of actively reducing this 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 bonding,

and finding good bonds, and also computing these bonds very fast because you will

compute them many many times, okay?

So, if you improve the way to compute a bound, okay,

you will improve the overall efficiency of the branch and bound algorithm.

So, in this particular ways on the knapsack problem,

think about how you can actually implement 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 will experience the whole infrastructure.

And you will first experience NP complete on a very simple problem, I must admit.

Okay, thank you.