PSSD – AssignmentPSSD – AssignmentThe Travelling Thief ProblemThis assignment is to be done individually and handed in via the web submission system.The due date for this assignment is the end of semester. There will be a lot of assignments in other courses due by then – and the last prac exam is on Thursday in Week 12 – so you must plan your time carefully up that date and start as soon as you can.ResourcesA directory with some input and output cases can be found here. A description of what these mean is given near the end of this specification. There is a C++ included with these cases called Eval.cpp which evaluates your solution with respect to its TTP setup file. Eval sanity checks the tour for length and duplicates and checks the weight of the knapsack as well as checking that the tour starts at the first city. Any violations print a message to stderr and return a value of INT_MIN on stdin. If your solution is valid then Eval will print a number indicating how good your solution is. A higher number is better.
The Eval program is compiled using
g++ -g -o Eval Eval.cpp
and run using
./Eval fnl.ttp fnl_soln.ttpwhere you would substitute the name of your desired ttp setup file (see below) for fnl.ttp and your own ttp solution file for fnl_soln.ttp. As mentioned above, the result of running Eval is just a number string printed to standard out.
In your program you can call Eval and read it’s result using popen (see: http://www.sw-at.com/blog/2011/03/23/popen-execute-shell-command-from-cc/) for an example. The return string can be parsed using something like the ston<> template in the Eval source.
In an ideal world we would just ship the functions in Eval as a library, but that opens up a lot of failure modes so we are using a self contained executable instead. This has been tested to compile on debian and on the lab image.
The Eval file is the same as that used in testing. If there are are any changes (which we’re hoping will not be the case) then you all will get the new file, of course.The websubmission systems handin key will be set up shortly. The system has a process limit of one minute per test case, so your solutions will need to be constrained to working in a short time. You can use algorithms or ideas (but not code) from any location that you find. However, you must credit these ideas in your code comments and in your other submission files so that we know where they came from. If you use someone else’s idea or a published algorithm and you make clear the extent of someone else’s contribution then you cannot get into trouble for misconduct. However, the marks that you get will be aligned with the value that you personally add. If you use a published algorithm (again not code!) and it forms a small part of the total product and you acknowledge the use and you made substantial intellectual effort in the rest of the program then you can still get full marks. SpecificationYou are a thief planning a grand tour of a set of cities x={x1,…,xn}. You have to visit every city just once (a Hamiltonian tour) and collect loot from these cites in a knapsack. The cities are connected by a set of roads of known length (measured in kilometres). Your aim is to maximise the profit you make on the loot you collect.Each city has a number of items that you can steal. You cannot steal in one city the same item several times. For this assignment, you can assume that all cities have the same number of items (e.g. three per city). Since there are no items in the start/end city number 1, this means that the total number of items for a particular scenario is m=(n-1)*itemsPerCity.Each item of loot yk has a value pk and a weight wk. You are a very talented thief and you able to steal anything that you plan. However, this is the extent of the good news. You are faced with a series of constraints that will affect how much profit you will make. These constraints are:1. Your knapsack, like all knapsacks, has a limited capacity. The total weight of items that the knapsack can hold is W.2. Your knapsack is a premium knapsack and, as such, must be rented. You must pay a rent of $R for the knapsack per hour. This will have obvious implications for any profit that you make.3. Once you are in city you can steal items infinitely quickly. However between cites you can only travel at a maximum speed of vmax kilometres per hour. Moreover, you will go more slowly as the knapsack gets heavier. The formula for your speed is: vc= vmax- Wc ((vmax- vmin )/W)where vc is your current speed, Wc is the current weight of the knapsack and vmin is the minimum speed at which you can travel. Recall that W is the total capacity of your knapsack. The formula above means that when your knapsack is empty you can travel at vmax and when your knapsack is full you will travel at vmin.Now remember that you are in the business of making profit. Your profit can be expressed by the formula:Profit = LootValue – (R x TourTime)Where LootValue is the value of items in the bag when you reach home. R is the hourly rent for the knapsack and TourTime is the time it takes to complete the tour. According to this formula, you will want to make sure your tour happens quickly (so you don’t have to pay too much out in rent) and you collect the lightest and most valuable items as a priority. You will also want to plan your trip so that if you want to pick up a heavy (but valuable!) item you would be better leaving that till late in the tour rather than picking it up earlier and lugging it slowly around. Note that the calculation of the value of a tour is done by the Eval program you are provided with.. you do not need to code this part.Input and OutputThe input for your solution is the ttp setup file. This file contains the following on separate lines. See the example in the next section to clarify the meaning of the following.• n: the number of cities• m: the number of different items.• W: the maximum weight capacity of knapsack• vmax: maximum velocity• vmin: minimum velociy• R: the rent of the knapsack (per hour)• the next n lines define the coordinates of the cities• the next m lines define the items and where they are locatedVery important: city 1 does not contain any items, as it is the start and end city of the thief’s tour!Note you shouldn’t have to provide this file – we have given you some examples to work with at the link above but we have described it here (and shown an example listing below) in case you want to modify these.The output of your problem is in the form of a file with two lines of comma-separated integers (optionally surrounded by square brackets)• a tour consisting of the sequence of cities visited. This will basically be a permutation of the numbers 1 to n. • a picking plan, which is a sequence of numbers of length <=m denoting which items (given their item ID) you picked.An example input and output file is shown next.Example ProblemConsider the following instance simple4_n6.ttp:PROBLEM NAME: simple4-TTPKNAPSACK DATA TYPE: manual constructionDIMENSION: 4NUMBER OF ITEMS: 6CAPACITY OF KNAPSACK: 100MIN SPEED: 0.1MAX SPEED: 1RENTING RATIO: 1.00EDGE_WEIGHT_TYPE: CEIL_2DNODE_COORD_SECTION (INDEX, X, Y): 1 0 02 0 103 10 04 10 10ITEMS SECTION (INDEX, PROFIT, WEIGHT, ASSIGNED NODE NUMBER): 1 10 1 22 20 5 33 40 1 44 10 1 25 20 5 36 40 9 4With a solution (output) like[1,2,4,3][]your objective score is -40.With a basic optimisation algorithm that optimises tours and/or stealing plans, you can achieve a score of 29.0535. With a great optimisation algorithm you can achieve a score of 96.1371. The solution in this case looks like:[1,2,4,3][1,2,3,4,5,6]Note that, because each object is assigned to only one city in the picking plan in the ttp setup file the numbers second array can be in any order.
For one of the hidden test cases in websubmission, the values are as follows:• you steal nothing: -2037.9600000000003• basic algorithm: 3618.177567129562• great algorithm: 3840.452067682491For the fnl instance (not part of the testing) that is part of our distributed files, a basic approach will get you into the area of ~200,000, and a great value would be 256,591.What is a Basic Approach?For example the following two-phase approach is a basic approach:1. You generate a good tour for the traveling salesperson problem, e.g. using the Lin-Kernighan heuristic. Then, you keep this tour and you will not modify it anymore.2. In the next phase, you work exclusively on the set of items. For example, you can start with a random combination (or “none picked”). Then, iteratively you check whether adding or dropping a single randomly picked item increases your objective score (do this with the Eval executable). If the new stealing plan (in combination with the fixed tour from step 1) yields a better objective score, you take this new solution and you do step 2 again… until time is up. Make sure to generate the file in the end!What to submitNote: the following might change slightly in the next days, we will inform you as soon as possible. However, the changes here will not affect your search for good optimisation algorithms.In your svn repository in a subdirectory called 2015/s2/pssd/assign1 you are to commit the following files:• a C++ source file called TTP.cpp• a Makefile that will compile TPP.cpp to a binary called TTP when the user runs make.• any other source files you will need to compile • A journal.pdf file containing the notes you created when constructing your program. Note that this file is a PDF document so your source documents can be text or it can be direct scan of (readable) handwritten notes. This file must be a believable commentary of what you did and tried while developing your program.. writing it at the last minute is a bad idea.• A pdf file called algorithm.pdf that describes the algorithm you used in plain English (with snippets of pseudo code if you like). The formatting of this file can be basic – it can just be plain text but the content must be clear and informative.NOTE: The websubmission system is not yet set up. If you want to experiment with a more comlex instance, feel free to take this. Basic scores are at around 16000, and great scores are above 18000.How it will be testedIn the websubmission system will compile and run your program with a series of test maps. The largest instance might contain over 600 cities and over 6000 items. We will test your program according to three criteria:1. That optimisation is in under 60 seconds.2. If point 1. above is OK then we will check to see that the produced solution (in file instanceName_soln.ttp) defines a solution that: (1) does not overload the knapsack, (2) starts in city 1.3. If points 1 and 2 above are OK then we will compute the objective score and mark you accordinly.Note that we have some hidden thresholds (based on tours on which nothing is packed). Once you reach that threshold, you get 40% of the marks for that test case. In order to get more, you need to achieve better scores. Think of us as being godfathers who know what a good thief should be able to achieve.Testing your own programsIn the resources folder there are a couple of files to help you simulate the trip. Also look at the Resources section above.How your work will be assessedThe breakdown of marks for this assignment are:1. 45% for the actual results on the tests in websubmission2. 5% for style and commenting of your source code3. 30% for having the development process convincingly detailed in journal.pdf4. 20% for a clear explanation of your algorithm in algorithm.pdfFor the first part, we will compute your score based on the following pseudo code:You have to achieve at least the “basic value” in order to get 40% here. The remaining marks are based on your performancerelative to “great”:
FOREACH instance i do run instance for a maximum of 60 seconds, computes value obj[i] IF obj[i] >= basic[i] THEN marks[i] = (obj[i]-basic[i]) / (great[i]-basic[i]) marks[i] = marks[i]*0.6 marks[i] += 40markForStudent = marks[0] + … + marks[4]rescale to fit 45%Please note: this formula is subject to change in case we encounter problems.Journal AssessmentYour journal.pdf file must contain the notes that you wrote for your own use as you developed your code. It should contain your ideas, hypotheses, reflections, pointers to resources, commentary on mistakes and test results. It should read like a running commentary of your development. The English does not have to be polished. It can be handwritten (but readable). If you are already using a journal for your development and you are taking enough notes and making enough reflections for it to be helpful in your own development then you should be meeting the requirements to get the marks for this project. Note that we will expect the journal to be quite long if your program was challenging to develop in keeping with the length of the project.Algorithm Description AssessmentYour algorithm description must be in plain English with pseudo-code. You only have to describe the core of your algorithm the part that moves the cities. The description should be clear, concise and in your own words. We expect this part of the assignment to be between 500 and 1500 words.