Java程序辅导

Lab Exercise 1: Enumeration, Greedy Search and Branch-and-Bound COMP60342 Lab Exercise 1: Enumeration, Greedy Search and Branch-and-Bound Duration: 2 weeks   Advice WARNING: This lab is designed to take 2 weeks of work; make a start as soon as possible. For this assignment, you MAY use code taken from other sources. If you do, you must clearly indicate the source in your code. Also, please check that the code functions correctly. Aims To gain experience of three related approaches to solving discrete optimization problems. To begin to understand when each is applicable; to appreciate their strengths and weaknesses. Learning Outcomes On successful completion of this exercise, you should: Understand the general 0/1 Knapsack Problem, the Fractional Knapsack Problem and the Subset Sum Problem. Appreciate how these have practical significance in logistics and other domains. Have implemented two exact techniques for solving the 0/1 Knapsack Problem. Have implemented one inexact technique - or heuristic - for finding good but not necessarily optimal solutions to the 0/1 Knapsack Problem. Have compared the time complexity and running times of these techniques. Have appreciated why these methods work, including being able to reason about their correctness. Have understood how to generalize the techniques to another problem (extension material). Lab Summary The lab is marked out of 20. The lab will contribute 25% of your coursework mark, or 10% to you overall mark. The task is to write three programs (enumeration, greedy and branch-and bound) for solving the 0/1 Knapsack Problem. The programs will be compared for their running time and solution accuracy on some test instances of the problem. (Total: 10 marks out of 20) There are 10 questions requiring written answers. Marking Procedure You will hand in your written answers to SSO by Friday April 17th, 9am. We will check your code during the week 3 lab. Please save your code by the morning of Friday April 17th and do not adjust it after that. Code Choice The programs may be written in any language that can be run in the laboratory (including C, C++, Java, Python, MATLAB). Choose the language you feel most confident about. No matter which language you choose to implement your code in, we will only ask that it reads in and writes out correctly to text files, and that you can explain it. Task List In summary, the lab breaks down into the following tasks. Week 1 1a. Write code to read in an instance of a 0/1 Knapsack problem. (1 mark) 1b. Write code to do a Full Enumeration of the 0/1 Knapsack search space, and print out the optimum found. (2 marks) 1c. Write code to implement a Greedy Search for the 0/1 Knapsack Problem. (2 marks) Week 2 2. Write code for a Branch-and-Bound algorithm. This is based on adjusting your greedy algorithm code to calculate a fractional knapsack upper bound. (3 marks) 3. Conduct experiments with all algorithms and produce results. Write this up as answers to Question 1 and Question 2. (2 marks) 4. Questions 3-9 (short answer exercises). *These may be started in Week 1. (7 marks) 5. Question 10: choose one from two alternative written extension exercises. (3 marks) -> April 17th, 9am: HAND IN all written work. Save all code for marking. The deadline for finishing code is Friday 17th April, 8.59am. i.e. before your third lecture. Background Knapsack Problems Knapsack problems are planning problems involving the optimal selection of differently-sized items, which must be placed in a container of limited capacity. These problems are common in logistics (where items must fit into cargo bays, aeroplanes, trucks), in the buying/selling of advertising space (e.g. online) and in cutting problems (e.g. how best to cut up a board or strip into component pieces.) Often, knapsack problems are multi-dimensional and may involve multiple knapsacks (containers). However, we will consider three simple 1-D knapsack problems here, as follows. 0/1 Knapsack Problem An instance consists of a set of N items with weights wi and values vi, for i=1 to N, and an integer, C, the carrying capacity of the knapsack. A solution to the problem is a subset of items having a total weight less than or equal to C that is maximal in total value (among all such subsets). 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. Fractional Knapsack Problem An instance is defined as for the 0/1 problem above, but the optimum is defined differently. Given a set of N items each with weight wi and value vi, for indexes i=1 to N, choose the amounts xi, of each item to carry, where xi is any real number in the range 0 to wi, so that the total value carried is maximized, and the total weight carried is less than or equal to a given carrying capacity, C. Another related problem to the 0/1 problem is subset sum. Subset Sum Problem You are given a set of N items with weights wi for i=1 to N, and an integer, C, the carrying capacity of the knapsack. Find a subset of items that maximizes the weight in the knapsack subject to the constraint that it must be less than or equal to C. This problem is like 0/1 Knapsack except that the values of items are their weights. We will be concerned mainly with the 0/1 Knapsack Problem in this lab. The other problems support our understanding. Programming Tasks (10 marks) Task 1a: Input/Output Write a program that reads in a knapsack problem instance text file written in the form N 1 v1 w1 2 v2 w2 . . . . . . N vN wN C Test your code by reading in the knapsack problem instance easy.20.kp.txt. Get it to write the instance back out to the screen. We may check this output and your code next lab (Lab 2: March 20th) You do not need to provide a written answer. Task 1b: Full Enumeration The 0/1 problem can be solved by a full enumeration of the search space. Every binary string of length N represents a valid candidate solution. Adding to your code from the previous part, write a program that loops through every possible binary string of length N and evaluates the value and weight of each of these solutions. Output Upon termination, the program should output the following: Best feasible solution found: ... where the items are the indexes of the items to be placed in the knapsack, listed in ascending index order. You could also get the program to output something to show its progress, i.e. the fraction of the search space it has enumerated. E.g. every 1,000 solutions evaluated it could output a line like "Y % of the search space enumerated so far". Run your code on easy.20.kp.txt. We will check this output and your code next lab. You do not need to provide a written answer. Task 1c: Greedy Search Greedy search can be applied to the 0/1 Knapsack problem, but it does not guarantee to give an optimal solution (see pencil and paper questions). Remember that a greedy search has the form: While solution not constructed Select best remaining element and try adding it in What is the sense of "best" here? I.e. what is the criterion by which the items should be ordered? Write a program that implements the greedy method for the 0/1 problem. In your implementation, first sort the items by your criterion so that you don't have to search through all of them each step. Output Upon termination, the program should output the following: Greedy solution (not necessarily optimal): ... We will check this output and your code next lab. You do not need to provide a written answer. Run your greedy algorithm code on the three problem instances, easy.20.kp.txt, easy.200.kp.txt, and hard.200.kp.txt. You should have reached here by the end of Week 1. You may look ahead to Task 4 - the short-answer questions. Task 2: Branch-and-Bound You will recall that a branch-and-bound approach is based on a tree search. At each node of the tree is a partial solution, with some solution components (items) determined, and some not. At the leaves of the tree are complete solutions. A partial solution can be represented as a string such as 011011*****, where the *s represent the parts of the solution that are not specified. (There is always a block of 0s and 1s followed by a block of *s). All possible ways of filling in the remaining bits of the solution will be below this node in the tree. Here is a search tree for a problem with three items: The idea of branch-and-bound is to visit some of the internal nodes, but to prune off the subtrees of nodes where an optimal solution cannot possibly lie, thus reducing the number of nodes that need visiting. To fathom a node (to dismiss it without expanding it), we make use of a bound function. The bound you will use is the fractional knapsack upper bound. This will give an estimate of the best possible value that can be achieved in the subtree. The estimate is guaranteed to be not smaller than the best solution in the subtree. The bound is calculated by greedy search, using the same technique as you used previously to order the items. The items from the specified part of the candidate solution are placed (or not placed) in the knapsack, and the value of those packed items is calculated. Then for the remaining part, the greedy algorithm is applied until the capacity of the knapsack is matched or exceeded. If it is exceeded then remove the last item added and place just that fraction of it that will fit (as if you are solving the fractional knapsack problem). Calculate the total value and return this as the bound. Write a function that gives the fractional knapsack upper bound of a candidate solution. Here is how its C prototype might look: double frac_upper_bound(int *partial_solution) { ... } The branch-and-bound will use a best-first search strategy based on these bound values. Every time it generates a partial solution that is feasible, it will calculate its bound value and then place the item in a priority queue. The queue will maintain an order so that the item at the head of the queue (the one that will be served next) is the partial solution with the best bound seen so far. The pseudocode is BRANCH-AND-BOUND-FOR-KNAPSACK Best_solution_value = 0 Sort the items (as for greedy) Current = ****.... Current.bound = Fractional_bound (Current) Add_to_PriorityQueue( Current) while ( notEmpty(PriorityQueue) && Best_solution_value< Current.bound) Current = Remove_from_PriorityQueue() if ( Current is not a fully-specified solution){ Left = Current with leftmost * replaced by 0 Right = Current with leftmost * replaced by 1 Add_to_PriorityQueue( Left ) if (Right is feasible) { Add_to_PriorityQueue( Right ) Right.solution = Right with all *s replaced by 0s if ( value(Right.solution) > Best_solution_value) { Best_solution=Right.solution Best_solution_value = value(Right.solution) } } } end while Comment added 24th March: Please notice in the above pseudocode that the Current.bound IS updated within the main while loop. This is implicit in the actions of the priority queue. Read the paragraph above the pseudocode again to see this. Basically, Current.bound always holds the bound value of the highest priority node (partial solution) in the queue. Implement this branch-and-bound algorithm. Output Upon termination, the program should output the following: Best feasible solution found: ... Remember, a priority queue is an abstract data structure that allows items to be stored in it, and the highest priority item to be retrieved from it. The simplest way to implement it is to do it inefficiently using a simple list. (Advice: use the simple way at first so you don't waste time). The efficient implementations usually use an ordered heap. You will gain an extra half a mark if you use an efficient implementation. Here are some links to help with more advanced priority queue implementation. Java PQ library C example source code We will check the output of your branch and bound algorithm on the easy20 instance, and your code, next lab. You do not need to provide a written answer. Task 3: Experiments (2 marks) Run greedy and branch-and-bound on each of the datasets easy.20.kp.txt, easy.200.kp.txt, and hard.200.kp.txt. Run enum on easy.20.txt only. (You cannot run enum on the larger instances. Think why.) Note: If you have coded your branch and bound efficiently, it should terminate within a few minutes on hard200. If it doesn't, you can stop it early and take the best value feasible solution to that point as your answer (you would need to add some code to print out the best value every time it finds a new one). Question 1: For each of the following seven experiments record the best value found and the total weight of items packed. Results should be recorded in a table like the one below. easy20 easy200 hard200 Enum value(weight) N/A N/A Greedy value(weight) value(weight) value(weight) B'n'B value(weight) value(weight) value(weight) Question 2: Explain why the Branch-and-Bound algorithm finds hard200 difficult (e.g. compared to easy200, which is of the same size). Task 4: Short-answer exercises (7 marks) The following are Questions 3-9. They require written answers. 1 mark is available per question. Please carefully check your answers are full and correct. No half marks will be awarded for incomplete or inaccurate answers. Explain the meaning of the following statement: "The fractional knapsack problem is in P". (You need more than a couple of words here. You need accurate definitions of terms used). Prove that a version of the greedy algorithm solves exactly (any instance of) the fractional knapsack problem. In what order does the greedy algorithm consider the items in order to solve the problem? In the subset sum problem, the value of an item is its weight, and only whole items can be taken. (a) Give a problem instance involving four items that shows that sorting items in descending order of weight and applying the greedy algorithm is not optimal. (b) Give a different problem instance of four items to show that putting items in ascending order is not necessarily optimal either. (c) What does this show about greedy on 0/1 Knapsack problems, and why? For the following set of items and knapsack capacity, work out the fractional knapsack upper bound. Note: the items need to be sorted first. Capacity C=60. Item index  1 2  3  4  5  6 Value  2 10 12 18  9 10 Weight 10 4 20 24 18 5 Repeat the exercise for the partial solution 01****. I.e. what is the bound if you are not taking item 1, and definitely taking item 2 (where the numbers refer to the position of the item in the sorted list, not the index of items). Prove that the greedy solution to the fractional knapsack problem is an upper bound to the 0/1 problem (in other words the solution to the 0/1 problem is guaranteed to be less than or equal to the solution of the fractional problem). Show that the current bound in the branch and bound algorithm is always nonincreasing. (An example will not do; you need to show why it is true in general). Task 5: Extension Material (3 marks) Question 10: Do Either (i) Or (ii). (i) The bin-packing problem is another type of knapsack problem. An instance of the problem consists of a number C the capacity of a bin, and a set of N items with weights wi for i is 1 to N. The solution is a partition into a minimal number of subsets, such that the items in each subset have combined weight not exceeding C. Explain how you would design a branch and bound algorithm for this problem. In particular, explain how you would represent a (candidate) solution, how you would branch, and how would you compute a bound suitable for pruning the search tree. For fun, try implementing your method. (ii) Give a brief description of the main procedures used in the advanced branch-and-bound algorithm reported in this paper. Explain how this differs from the simple one you implemented. Your answer should be between 300 and 600 words long.