CSC 495-001, Spring 2020 Programming/Homework Assignment 2 page 1 of 3 Due: Tuesday, March 24, at 11:00 PM Note: Due dates for the last two homeworks may need to be adjusted or, the two homeworks may be combined. Purpose. This assignment has several objectives. 1. You will formulate branching strategies, upper bounds, and lower bounds for a new problem. 2. You will formulate a problem instance as a binary integer programming instance. 3. You will carry out computational experiments and document their results. 4. You will develop a branch and bound algorithm with at least two levels of so- phistication. 5. You will develop/use infrastructure for running and documenting experiments, including techniques for reporting runtime, solution quality, and other statistics, putting these in spreadsheets, and creating charts. 6. You will (use scripts to) generate random problem instances to assess effective- ness of algorithms. Written part (counts as homework) Recall the definition of the knapsack (optimization) problem. Given n items, where item i has a weight wi and a value vi, and a capacity C, find a subset I of {1, . . . , n} such that ∑i∈I wi ≤ C and ∑i∈I vi is maximized. The following questions address strategies that will lead to a good branch and bound algorithm for the knapsack problem and an approach that allows it to be solved using CPLEX. Note: Since knapsack is a maximization problem the traditional roles of upper and lower bounds are reversed: the total value of a feasible solution is a lower bound on the value of an optimum solution; a “proof” that the value of a solution cannot be more than V is an upper bound. 1. Based on what we learned about the greedy heuristic for knapsack, what might be a good branching strategy? 2. A trivial lower bound for a smaller instance of knapsack is simply the total value of items chosen to be part of the solution. Come up with a better lower bound. CSC 495-001, Spring 2020 Programming/Homework Assignment 2 page 2 3. A trivial upper bound on the value of a solution is the value of items already packed plus the total value of the remaining items (omitting ones that have been excluded). Come up with a better upper bound. Think about the maximum value that could possibly fill the remaining empty space. 4. Formulate the knapsack problem as a binary integer programming problem. Programming part Your assignment is to implement a branch and bound algorithm for the knapsack problem that incorporates your answers to questions 1–3 above. Your program should be able to run in either plain mode (trivial lower and upper bound) or with the answers to 2 and 3 incorporated (tuned). Branching should be the same for both modes (using your answer to 1). Input format. Input should be a text file with the following specifications: (i) a line that begins with # should be ignored – it is a comment; (ii) (ignoreing comments) the file begins with a line of the form k n C, where n is the number of items and C the capacity; and (iii) each subsequent line is of the form i wi vi, where wi and vi are integers representing weight and value of item i, respectively. A small example of an input file is # This example is used to illustrate # case 1 of the proof of the ratio for the modified greedy heuristic k 4 30 # item a 1 10 15 # item b 2 10 14 # intem c 3 15 20 # item d 4 16 20 Output Format. When you debug your programs and even when you are running them in “production mode” you will want to print a variety of information. Anything that is not part of the specifications detailed below should be printed to stderr instead of stdout. Output for each run should consist of the filename, the number of items, the capacity, the number of items packed, the total value of items packed, the total weight of items packed, the mode (plain or tuned), the runtime (integer in milliseconds), the number of branches (each smaller instance generated counts as a branch), and a list of items in the solution, each item on a line starting with i- Each line should contain the name of the field, followed by whitespace (a tab makes the output easy to read). A sample output is as follows (runtime and branches are made up). CSC 495-001, Spring 2020 Programming/Homework Assignment 2 page 3 filename case_1.txt items 4 capacity 30 packed 2 value 35 weight 26 mode plain runtime 119 branches 2 i- 1 i- 4 Supporting scripts are still in progress. The highest priority is a script that generates random instances given the following information • number of items n (mandatory) • range of weights wlow, whigh • capacity, default is n/2·wavg, rounded to nearest integer, where wavg = (wlow + whigh)/2 • range of values vlow, vhigh Weights and values, respectively, will be chosen uniformally at random in ranges [wlow, whigh] and [vlow, vhigh]. Recommendations. As with Program 1, you may find it convenient to suppress output of the solutions when running on a large number of larger instances. Consider adding a command-line option that accomplishes this, e.g., -q or –quiet. The best way to store smaller instances is to maintain a vector of length n with each item marked as one of in, out, or undecided. When doing a recursive call, there is no need to copy this vector. All you need to do is push the item you are branching on onto a stack. When you return, you simply pop the item and reset it to undecided. You will also want to have a vector (or list) that records the current best lower bound. Report. The report and the grading scheme for the programming are based on those for Program 1. Be sure to take comments on your first program submission to heart.
