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.

Â