[home][mail][print]

DM519 Exam Project 2007

The Hungry Assassinating Ninja Problem (HASP)

a.k.a. The Maximum Traveling Salesman Problem

DM519 Exam Project

Motivation

Uma Thurman facing the Crazy 88The not-so-known ninja 高瀬 慶 (Kei Takase) wants to become a member of the well-known Crazy88 ninja gang. To become a member 慶 needs to do a certain number of very secret assassinations.

Hence, by secret methods 慶 very recently received a list of people that his coming ninja master wants to have assassinated as soon as possible. To help 慶 buy important ninja accessories, like e.g., a Nunchaku (ヌンチャク) or Shuriken (手裏剣), this is of course not a completely unpaid job. The Danish Ninja Trade Union (DNT) has set very strict rules for how ninjas should be payed doing their work. Since ninjas are expected to enjoy the actual assassinations, these are unpaid. But ninjas are payed by the distance they have to travel to do their assassinations. Currently, ninjas get exactly 103 € per traveled hectometer (hm).

Since 慶 is still a student ninja, he of course wants to maximize the profit gained from the assassinations. Consequently, what he is actually facing (apart from the assassinations) is an instance of the Hungry Assassinating Ninja Problem (HASP).

As an example, see the image to the right where a possible solution for HASP is presented. In this, the ninja needs to travel from his home base 四 (4) to assassination of person 一 (1), then to person 三 (3), person 二 (2), and finally returns to his home base 四 (4) again. A better and optimal solution for the problem is the tour (四, 一, 二, 三, 四).

Note that this is very close to solving a TSP problem, except that we for the HASP want to find a tour of maximal length.

In general an instance of HASP can be defined by:

To help 慶 solve this the Ninja Student Association (NSA) has released a sequential Java program which basically solves HASP using Branch and Bound. Your assignment is to extend the sequential version, such that it can run efficiently on a computer with more CPUs and also extend it to run on more machines. For details, see below.

Sequential Code

The sequential code from NSA is available here:

Assignment

You should extend the sequential HASP program in two steps:

  1. A version which uses more threads to efficiently use a SMP machine. While doing this you should consider both static and dynamic orchestration.
  2. A version which distributes the problem to run efficiently on more computers. This could be done using e.g. RMI or a direct socket connection.

You may base your new versions on the above sequential code, but can also implement your own. The only requirement is that your solution is correct and can solve the test cases given above correctly.

You should show that your version using more computers can be run using at least 3 computers, and also how to easily extend this to any number n, n ≥ 2, of computers.

You can implement your solution in either Java (recommended), C, C++ or Python. If you prefer a language not mentioned here, let me know and it will possibly be added to the list. Note that Java is the only language for which you can expect any support from us.

Remember that any optimizations you use to improve the performance of your new versions should also be used on the sequential version if applicable.

Test Instances

You should possibly include your own test instances aswell. The format used in the test instances is explained in Problem.java

Questions

To ensure that everybody gets a fair chance of solving this, and nobody gets more information than anybody else, questions should be posed either at the lectures or the discussion sections. You can also send questions using the mailing list.

The Report

The report should contain the following:

The report should have a maximal size of 10 pages (normal A4 pages, 12 pt text) excluding your code and large figures (if any). If you use more than 10 pages, only the first 10 will be read.

Important: You should deliver your report in TWO (2) COPIES!

Dates

Release date
The project was released February 28 at 12.15.
Deadline
You should turn your project in by March 30, 2007 at 9.00. Late deliveries are generally not accepted, and you will have to do a new project next year instead. Extensions of the deadline need to have an acceptable reason due to the study board, e.g., it is not enough that your Windows computer broke down, you accidentally deleted all your files, your dog ate your computer or that you were secretly abducted by ninjas.

Your report should be turned in at IMADA's secretaries' office.

Exam Rules

This project is an exam project. All the rules for a normal exam also applies here. Specifically, you are not allowed to get help from anybody, and you should ensure that nobody but you can access your files and your thoughts.

You are allowed to talk with the other students about general ideas used to implement the solution (e.g. at the discussion sections), but have to work on your own when you are actually thinking, writing or implementing anything. Breaking these rules is considered cheating and will be treated as such!

Links and Extra Literature

The following could possibly help you doing your project:

Solving HASP exactly is can be done by transforming it into a normal TSP problem in polynomial time. For approximation algorithms, such a transformation is problematic (why?). If you are interested, you could have a look at the following paper. This is not in any way required for doing the assignment, but is only here to show that you are actually solving an interesting problem.