Duration: 3 weeks

You should do all your work in the lab5 directory of the COMP26120 2022 repository - see Blackboard for further details. You will need to make use of the existing code in the branch as a starting point.

Important: You submit this lab via a quiz on Blackboard. This will:

1. Ask you some questions about your implementation, including the hash and tag of the commit you want us to mark (see below for details of this).

2. Ask you to upload a zip file of the python, c or java folder you have been working in.

3. Ask you to upload PDF reports of the experiments you will run in Part 3 of this lab (one report for each experiment)

You can save your answers and submit later so we recommend filling in the questions for each part as you complete it, rather than entering everything at once at the end.

NB: We have made some changes to this lab since the start of semester 1 in the hopes it will be quicker to mark.  If you want a helper script for generating input for experiments and a LaTeX template for the report that reflects how it should be structured now, please pull from upstream:

You can do this by typing the following commands in your gitlab directory:

git  remote  remove  upstream

git  remote  add  upstream  https://gitlab.cs.man.ac.uk/t95229ld/comp26120_2022_base.git git  fetch  upstream

git merge  upstream/master

Code Submission Details

You have the choice to complete the lab in C, Java or Python. Program stubs for this exercise exist for each language. Only one language solution will be marked.

Because people had a number of issues with GitLab last year we are going to take a multiple redundancy approach to submission of code.  This involves both pushing and tagging a commit to GitLab and uploading a zip of your code to Blackboard.  By preference we will mark the code you submitted to GitLab but if we can’t find it or it doesn’t check out properly then we will look in the zip file on Blackboard. Please do both to maximise the chance that one of them will work.

When you submit the assignment through Blackboard you will be asked for the hash  and tag of the commit you want marked. This is to make sure the TAs can identify exactly which GitLab commit

Figure 1: Identifying the hash of your most recent commit in GitLab

Figure 2: Identifying the hashes of previous commits in GitLab

you want marked. You tag a commit lab5 solution (we recommend you use this tag, but you do not have to) by typing the following at the command line:

git  tag  lab5_solution

git  push

git  push  origin  lab5_solution

You can find the hash of your most recent commit by looking in your repository on GitLab as shown in figure 1.

You can also find the hash for a previous commit by clicking on the “commits” link and then iden- tifying the commit you are interested in. This is shown in figure 2.

Note that while the full hash for commits are quite long, we only need the first 8 characters (as shown in the screenshots) to identify for marking.

Reminder: It is bad practice to include automatically generated files in source control (e.g. your git repositories). This applies to object files (C), class files (Java), and compiled bytecode files (Python). It’s not fatal if you do this by mistake, but it can sometimes cause confusions while marking.

While it is fine to discuss this coursework with your friends and compare notes, the work submitted should be your own. In particular this means you should not have copied any of the source code, or the report. We will be using the turnitin tool to compare reports for similarities.

Learning Objectives

By the end of this lab you should be able to:

• To explain the 0/1 Knapsack problem and Fractional Knapsack problem.

• To implement a number of exact techniques for solving the 0/1 Knapsack problem.

• To implement one inexact technique - or heuristic - for finding good but not necessarily optimal solutions to the 0/1 Knapsack problem.

• To evaluate and compare running times of these techniques.

• To devise experiments to investigate factors that make Knapsack problems hard for various solution techniques.

Introduction

In this section we introduce two related ‘Knapsack’problems.

The 0/1 Knapsack Problem and Logistics

Suppose an airline cargo company has 1 aeroplane which it flies from the UK to the US on a daily basis to transport some cargo. In advance of a flight, it receives bids for deliveries from (many) customers.

Customers state

• the weight of the cargo item they would like to be delivered;

• the amount they are prepared to pay.

The company must choose a subset of the packages (bids) to carry in order to make the maximum possible profit, given the total weight limit that the plane is allowed to carry.

In mathematical form the problem is: Given a set of N items each with weight wi  and value vi , for i = 1 to N, choose a subset of items (e.g. to carry in a knapsack, or in this case an aeroplane) so that the total value carried is maximised, and the total weight carried is less than or equal to a given carrying capacity, C .  As we are maximising a value given some constraints this is an optimisation problem.

This kind of problem is known as a 0/1 Knapsack problem. A Knapsack problem is any problem that involves packing things into limited space or a limited weight capacity.  The problem above is “0/1” because we either do carry an item:  “1”; or we don’t:  “0”. Other problems allow that we can take more than 1 or less than 1 (a fraction) of an item. Below is a description of a fractional problem.

See the description in Algorithm  Design  and  Applications, p.   498.   or the briefer description in Introduction to Algorithms, p. 417.

An Enumeration Method for solving 0/1 Knapsack

A straightforward method for solving any 0/1 Knapsack problem is to try out all possible ways of packing/leaving out the items.  We can then choose the most valuable packing that is within the weight limit.

For example, consider the following knapsack problem instance:

The first line gives the number of items; the last line gives the capacity of the knapsack; the remaining lines give the index, value and weight of each item e.g. item 2 has value 12 and weight 10.

The full enumeration of possible packings would be as follows:

Items Packed

000

001

010

011

100

101

110

111

Value

0

8

12

20

5

13

17

25

Weight

0

5

10

15

4

9

14

19

Feasible?

Yes

Yes

Yes

No

Yes

Yes

No

No

The items packed column represents the packings as a binary string, where“1”in position i means pack item i, and 0 means do not pack it.  Every combination of 0s and 1s has been tried.  The one which is best is 101 (take items 1 and 3), which has weight 9 (so less than C = 11) and value 13. We can also represent a solution as an array of booleans (this approach is taken in the Java and Python stubs).

Some vocabulary

• A solution: Any binary or boolean array of length N is referred to as a packing or a solution; This only means it is a correctly formatted instruction of what items to pack.

• A feasible solution: A solution that also has weight less than the capacity C of the knapsack.

• An optimal solution: The best possible feasible solution (in terms of value).

• An approximate solution: Only a high value solution, but not necessarily optimal.

In this lab we will investigate some efficient ways of finding optimal solutions and approximate solu- tions.

Description

This lab asks you to implement four different solutions to the 1/0 Knapsack problem over three weeks. We have provided partial solutions and it is your job to complete them.

Important Note 1: The C support code represents Knapsack solutions as a bitstring (an array of 0s or 1s) indicating whether an items should (1) or should not (0) be packed into the knapsack. The Java and Python code represent solutions as arrays of booleans (True and False).  The Java and Python support code, converts the boolean values to 0 or 1 for printing so there can be a uniform presentation of results.  In what follows we will sometimes use T as shorthand for True and F as shorthand for False.

Important Note 2: In the input files, items for the Knapsack are numbered from 1 to N. The support functions read these into arrays of size N+1 (one for item weights, one for item values and one to map the index of the item in the input file to that in a sorted array (for the algorithms where sorting by value/weight ratios is useful)).  These arrays all have a null or None value (depending on language) as the 0th element of the array. In this way the array indices match up with the numbering in the input files, but it does mean that functions and methods working with these arrays have to account for the irrelevant 0th element. This is easier in C where you can simply pass a pointer to the element of the array at position 1 than in Python or Java where you need to start any iterations etc., explicitly at element 1.

Task 1a: Full Enumeration

Time Budget: Task 1a is primarily intended to help you familiarise yourself with the input files and running the knapsack program.  You should not spend more than an hour on this task and it is not needed for later tasks in this coursework.  If you are stuck on this for some reason but are confident that you understand how our input files work, how problems are represented internally in the program and how the program can be run, then we would recommend you move on to the rest of this coursework after an hour.

We have provided an implementation of the enumeration method for the Knapsack problem in each language.  You can (compile, if necessary, and) run this program on data/easy .20 .txt.  The program enumerates the value, weight and feasibility of every solution and prints them to the screen. However, it does not “remember”the best (highest value) feasible solution or display it at the end.

1. Adapt the code so that it does that. NB. on data/easy .20 .txt this should compute a solution value of 377.

2. It would also be useful to display how much of the enumeration has been done – like a progress bar.  Add code to the enumeration loop to print out the fraction of the enumeration that is complete and the value of the current best solution.  Note: If you update the progress bar too often it will slow you down a lot. You may want to think about how often you update it if you want a more efficient program.

You may change the value of the QUIET variable to suppress output to the screen and make the code run faster.

Running on our Example Inputs

In the data directory you will find four files:

easy.20.txt

easy.200.txt

hard.200.txt

hard.2000.txt

In each case the number in the file name (20, 200, 2000) indicates how many items the example wants you to put into the knapsack. Your enumeration algorithm will probably only manage to solve the 20 item knapsack.   The correct optimal answers for the problems are 377  (easy.20.txt), 4077 (easy.200.txt), 126968 (hard.200.txt), 1205259 (hard.2000.txt).

Blackboard Submission

Once you have completed this implementation you should look at the Blackboard submission form where you will be asked the following question about Part 1a.

1. When you ran your enumeration solution on data/easy .20 .txt (no more than 100 words):

(a) How long did it take to run? You can use the Unix time utility for this. It is fine to just

report the real time from this function.

(b) What did value did it report as the maximal possible knapsack value?

(c) What was the difference between the reported value and the optimal value (377)?  (NB. The answer to this will be 0 if your implementation returned the optimal solution).

For instance, if your code took 20.34 seconds to run and reported a maximal possible knapsack value of 374. I would expect to see here something like:

easy .20 .txt:  20 .34s,  reported  value:  374,  difference  to  optimal:3

Task 1b: Dynamic Programming

Time Budget: Task 1b is the key task in this coursework and you will need it working for your report. The intention is that task 1b should take you 1-2 hours to complete. Dynamic programming can sometimes be a bit fiddly so you might want to budget this time to include one of the drop-in sessions so you can access TA help if necessary.  If you are going over 3 hours it might be worth “borrowing” some of the time allowed for later parts of the coursework, but you might want to look ahead, check out the marking scheme, and think about where you can best spend time.

Unlike the enumeration approach  (which generated all possible solutions and picks the best), dynamic programming approaches iteratively compute the solution to larger and larger subproblems using the results of smaller subproblems until we have the solution to the overall problem.

Complete the program that solves the 0/1 Knapsack Problem by dynamic programming.  Using the program stubs and support files we provide for you.

The Dynamic Programming Solution

There is a detailed explanation of the dynamic programming approach to the 0/1 Knapsack Problem with examples on p. 343-345 of Algorithm Design and Applications. In brief the solution is as follows:

Identify sub-problems in a tabular form We will use a two dimensional array, V , for our sub- problems.  V [i][w] is the maximum value we can achieve with the first‘i’items in our input list using at most weight‘w’. If we have a list of N items and a capacity of C, then if we can compute all values in the array V the value at V [N][C] will contain the optimal value of the items can can fit into our aeroplane.

Initialise the array If we have no items then our optimal value is 0, so V [0][w] = 0 for all 0 ≤ w ≤ C . All other values in the array we initialise with null or None (depending upon the language).

Recursive Step The maximum value we can make with the first i items and a weight limit of w , where the value of the ith item is vi  and the weight of the ith item is wi  is either:

1. The maximum value we could make with the first i − 1 items (ignoring the ith item), or

2. The maximum value we could make by adding the value of the ith item, vi , to the maximum value we could make using the first i − 1 items and a maximum weight of w − wi .

This is V [i][w] = max(V [i − 1][w],vi + V [i − 1][w − wi]) for 1 ≤ i ≤ N, 0 ≤ w ≤ C .

The table V just tells us the best value we can get after considering i items it doesn’t tell us which ones we added. We can update the algorithm to keep track of this information by using an auxilliary array, keep where keep[i][w] records whether the ith item is used in the maximal solution for V [i][w]. If keep[i][w] = 0 then we know that the ith item has been ignored and this maximal solution has been constructed from the maximal solution for V [i−1][w] so we should use keep[i−1][w] to find out which other items are included. If keep[i][w] = 1 then we know that the ith item has been included and this maximal solution has been constructed from the maximal solution for V [i − 1][w − wi] so we should use keep[i − 1][w − wi] to find out which other items are included.

The following pseudo-code outlines the complete solution

KnapSack(v,  w,  N,  C)  {

for  (w  =  0  to  C)  V[0][w]  =  0

for  (i  =  1  to  N)

for  (w  =  0  to  C)

if  (w[i]  <= w) and (v[i] + V[i - 1][w - w[i]] >  V[i  -  1,  w])  {

V[i][w]  =  v[i]  +  V[i  -  1][w  -  w[i]]

keep[i][w]  =  1

}  else  {

V[i][w]  =  V[i  -  1][w]

keep[i][w]  =  0

}

K  =  C

for  (i  =  N  downto  1)

if  (keep[i][K]  ==  1)  {

output  i

K  =  K  -  w[i]

}

return  V[N,  C]

You may want to run a few simple examples of the algorithm by hand to check you understand how it works. For instance, how does it behave with the following four items:

i 1 2 3 4

vi 10 40 30 50

wi 5 4 6 3

Implementing and Testing the Dynamic Programming Solution

You can find further instructions for approach to this in  dp . c/dp kp .java/dp kp .py  file (depending upon which language you are using). If you wish, you may ignore these program stubs and implement your own dynamic programming approach to the 0/1 Knapsack problem.

Test your code on the instance file, data/easy .20 .txt. You should get the same answer as with the enum program.

Try the harder problems in the data directory. If interested, and you have time, you might want to investigate the space and time complexity of your solution.

Once you have completed this implementation you should look at the Blackboard submission form where you will be asked the following questions about Part 1b.

Blackboard Submission

Once you have completed this implementation you should look at the Blackboard submission form where you will be asked the following question about Part 1b.

1. Run your dynamic programming solution on the four files in the data directory, killing it if it runs for more than 60 seconds.  Then answer the questions below for each of the four files (no more than 100 words in total):

(a) Did the run complete in under 60s?  If so, how long did it take to run?  You can use the

Unix time utility for this. It is fine to just report the real time from this function.

(b) Did it report a value as a possible knapsack value when it finished running or you killed

it? If so what was that value?

(c) If it reported a value, what was the difference between this and optimal value for that

problem (See the end of Task 1a for a list of the optimal values)?

I would expect to see here something like:

easy .20 .txt:  20 .34s,  reported  value:  374,  difference  to  optimal:3  easy .200 .txt:  35 .5s,  reported  value:  4077,  difference  to  optimal:0

hard .200 .txt:  killed,  reported  value:  none,  difference  to  optimal:  not  applicable  hard .2000 .txt:  killed,  reported  value:  none,  difference  to  optimal:  not  applicable

2. How does your implementation of dynamic programming work. Illustrate this with the part of your code that is equivalent to lines 3-11 of the pseudocode we have given above.  In partic- ular, explain in your own words, the role of your equivalent of the arrays V and keep in your implementation. (no more than 300 words, not including code snippet)

You should be here by the end of week 1 of this lab.

Task 2a: Fractional Knapsack Bound

Time Budget: Tasks 2a and 2b, taken together, are intended to take between 1 and 2 hours to complete. They are not needed for any other part of this lab. If you have spent more than two hours on Part 2 we recommend proceeding to tasks 3a and 3b.

Imagine we have decided we definitely want to pack some particular items, and definitely don’t want to pack some particular other ones.  For the remaining items we are not sure yet.  We can represent this situation as

001110*****             or           FFTTTF*****

where 0 or F (False) means definitely won’t take the item, 1 or T (True) means definitely will, and * means don’t know. We call these partial solutions.

We can now calculate an estimate of the best value of all possible ways of replacing the *s by 0/Fs and 1/Ts. This will be an overestimate. We call it an upper bound.

To calculate the estimate we take the * items in decreasing order of value-to-weight ratio and add them to the knapsack, until we go over the capacity.  For the last item added, we take it out again and only add that fraction of its weight that would fit, and adding the same fraction of its value to the total value of the knapsack. This is a kind of cheating; however, we are only interested in making an estimate.

In  the  bnb.c/bnb kp.java/bnb kp.py  code,  we  have  already  provided  an  almost  complete  func- tion frac bound() which accepts a partial solution of the form 01101****** (C) or FTTFT****** (Java/Python) as input and does the following things:

1. Checks the feasibility of the partial solution and sets the solution value to -1 if it is infeasible, and returns.

2. If the partial solution is feasible then its value is calculated, i.e. the value of the items already packed, and the value is updated

3. If the partial solution is feasible then its upper bound is also computed and updated.

Make sure you understand this frac bound() function and complete it by filling in the two missing lines.

Task 2b: Branch-and-Bound

The branch and bound approach was covered in lectures as a backtracking method for optimisation problems. You should also see pages 521-524 of Algorithm Design and Applications.

Let’s consider how we might, as people, solve the 0/1 knapsack problem.  We would try the‘best’ item first (e.g.  the one with the highest value-to-weight ratio) and see if we can fit the best items  in.  This is also a reasonable approach for a computer e.g.  to sort the items in descending order of value-to-weight ratio, and add items in that order until the knapsack is full. However, we might realise  that putting that really big item in the bag means there is left over space and putting two smaller  items in would have been better i.e. we back-track by removing an item and trying something else. We get computers to do the same thing when systematically exploring the search space.

In order to prevent us backtracking through every possible solution, we can “prune” off parts of the set of the solutions we know cannot contain a feasible/optimal solution. If we know that a particular subset of items is heavier than the capacity, we do not need to consider any solutions that use that subset. Similarly, if we know that not including a particular item (e.g. the first item) the best we can do is value vupper , and we have already found a solution better than vupper , then we no longer have to consider any solution that does not contain that crucial item.

You must now use the frac bound() function to complete the branch-and-bound implementation. The outline of the algorithm can be given as follows (see Algorithm  Design  and  Applications  for more details).

1. Sort the items by decreasing value-to-weight ratio.

2. Compute the upper bound of the solution ****...

3. Compute the current values of each of the two solutions 0***...  (or F***...)  and 1***...  (or T***...) (i.e. the total value of all the 1/Ts in each string), also their upper bound values, and check they are feasible.

4. If they are feasible we place them on a priority queue (Note we have provided implementations of a priority queue for all three languages).

5. In the next and all subsequent iterations, we remove the item with best bound value off the priority queue and again consider appending a 0 (C) or False (Java and Python) and a 1 (C) or True (Java and Python) to it.

6. The algorithm stops when the queue is empty or a solution (a complete solution with no stars in it) with value equal to the current upper bound is found.

Complete the  branch and bound  function given in bnb.c/bnb kp.java/bnb kp.py .  This will call the fractional knapsack bound function frac bound() and use the priority queue functions provided. More instructions are given in the code files.

When testing branch-and-bound you should consider stopping the program early if it is taking too long and think about how close the current best solution is to the actual optimal solution. Note that if you wait long enough you might hit the capacity of the priority queue – this probably indicates that you should give up trying to find an exact solution with branch-and-bound, although you can try making the queue larger.

Blackboard Submission

Once you have completed this implementation (or got as far as you can with it) you should look at the Blackboard submission form where you will be asked the following question about Part 2.

1. Run your branch-and-bound solution on the four files in the data directory, killing it if it runs for more than 60 seconds.  Then answer the questions below for each file (no more than 100 words in total):

(a) Did the run complete in under 60s?  If so, how long did it take to run?  You can use the

Unix time utility for this. It is fine to just report the real time from this function.

(b) Did it report a value as a possible knapsack value when it finished running or you killed

it? If so what was that value?

(c) If it reported a value, what was the difference between this and optimal value for that

problem (See the end of Task 1a for a list of the optimal values)?

I would expect to see here something like:

easy .20 .txt:  20 .34s,  reported  value:  377,  difference  to  optimal:0              easy .200 .txt:  35 .5s,  reported  value:  4077,  difference  to  optimal:0            hard .200 .txt:  killed,  reported  value:  126967,  difference  to  optimal:  1    hard .2000 .txt:  killed,  reported  value:  1205250,  difference  to  optimal:  9

2. What does the frac bound function compute (there should be two things)? How do these relate to a partial solution? What is a feasible partial solution? (no more than 200 words).

3. Have you used a priority queue in your solution? If so, what does the queue use to prioritise its elements, where have you used it and what role is it playing? If not, what have you used instead of the priority queue where this was suggested in the code stub and what role is it playing? Illustrate your answer with the relevant parts of your code – you may omit lines of the code (use ...) to focus on those bits most relevant to the use of the priority queue (don’t show the code that implements the queue, but the code where you check elements of the queue, remove and add things to the queue). (no more than 300 words, not including code snippet).

You should be here by the end of week 2 of this lab.

Task 3a: Greedy Algorithm

Time Budget: Task 3a is intended to take less than half an hour to complete.  It is not needed elsewhere in the lab and should be abandoned if time is running out.

The greedy algorithm is very simple. It sorts the items in decreasing value-to-weight ratio. Then it adds them in one by one in that order, skipping over any items that cannot fit in the knapsack, but continuing to add items that do fit until the last item is considered. There is no backtracking to be done.

Write your own greedy algorithm in greedy .c/greedy kp.java/greedy kp.py . Note that we have pro- vided a sort by ratio function/method (you should have encountered this when implementing the branch-and-bound solution).

Blackboard Submission

Once you have completed this implementation (or got as far as you can with it) you should look at the Blackboard submission form where you will be asked the following question about Part 3a.

1. Run your greedy solution on the four files in the data directory, killing it if it runs for more than

60 seconds. Then answer the questions below for each file (no more than 100 words in total):

(a) Did the run complete in under 60s?  If so, how long did it take to run?  You can use the

Unix time utility for this. It is fine to just report the real time from this function.

(b) Did it report a value as a possible knapsack value when it finished running or you killed

it? If so what was that value?

(c) If it reported a value, what was the difference between this and optimal value for that

problem (See the end of Task 1a for a list of the optimal values)?

I would expect to see here something like:

easy .20 .txt:  0 .05s,  reported  value:  368,  difference  to  optimal:9              easy .200 .txt:  0 .1s,  reported  value:  4075,  difference  to  optimal:2            hard .200 .txt:  2s,  reported  value:  1