BAP Partitioning Challenge : Combinatorial and Graph Algorithms

Combinatorial and Graph Algorithms
School of Computing, National University of Singapore
(CS5234, Fall 2007)

The BAP Partitioning Challenge
Milestone M3 : [Extended to Thu, 15 Nov 2007, 23:59]

Aims of the Course Project

The aim of the course project is to apply advanced algorithms and data structures to solve real problems. The problem chosen for this purpose is the BAP partitioning, a sub-problem of the Berth Allocation Planning (BAP)

The BAP is an optimization problem that arises from operations in large transshipment ports such as PSA, Singapore. Very briefly, the BAP partitioning problem is to assign incoming vessels to different sections of the port (for berthing) so as to minimize the cost of transshipment (which is the cost of container movement between vessels and between vessels and the port).

BAP Partitioning Challenge

This project is to implement efficient and effective algorithms for BAP Partitioning, and verify the performance of your algorithm on various benchmark datasets. This project is modelled after various DIMACS Challenges, where researchers are invited to implement algorithms to solve specific problems. (Past DIMACS challenge problems include matching, network flows, graph colouring, maximum clique, satisfiability, TSP, shortest path, etc).

In this BAP Partitioning Challenge, the "challenge" is to do design the best possible algorithm for solving the BAP Partitioning Problem, which is known to be NP-complete. So, the twin sub-goals of the challenge are to come up with good heuristic algorithms on large instances, and to hopefully solve smaller instances almost optimally.

As far as I know, BAP partitioning is isn't a very well-studied problem, so there should be a chance to get some good research results in this class project. I also hope that some of the good projects can be suitably extended after this class into research papers. I will give some relevant references that you may want to consider in the design of your own algorithms.

The BAP Partitioning Problem

More details of the BAP partitioning problem can be found here.

The Benchmark BAP DataSets

An important aspect of the DIMACS Challenges is a publically available set of problem instances which made it possible to directly compare results. Likewise, the probem instances for the BAP Partitioning Challenge are made available in the course web-site.

BAP DataSets

These BAP datasets were randomly generated, although many of the parameters were based upon data that closely match real port situations.

BAP Source Codes and Resources

My research group (the RAS-Group, SoC, NUS) has developed a software prototype software system called BAPS that solves the BAP. The BAPS is developed in C++ and uses the LEDA software for some of its data structures. We have also extracted some key components and classes of the BAPS to be used for the case study in this project. It is provided here:

BAP Source Codes and Resources

The code gives a complete framework for solving the BAP (both partitioning and packing). The code for a BAP partitioner (called the Trivial Partitioner) is also given to you. The Trivial Partitioner assigns the vessels to sections randomly. Hence, we do not expect its results to be any good. However, the code for the Trivial Partitioner will give you a very good reference that will help you to implement your own BAP partitioners.

You will need to download the BAP source code, understand the code (with the help of the lecture notes). Read the BAP Package class since most of the functions/methods that you need should be found in there. You don't need to understand all the code in order to do your assignment. Pay more attention on the BAPTVPartitioner code since your own greedy algorithm will be based on it.

Added: 15-Oct-2007;
The concept of "time zones" is discussed in many BAP papers and can be found in Chapter 3.1.1 of David Ong's thesis. The link to the thesis can be found in the BAP description.

What You Have to Do

To help you achieve your project goal of implementing your best algorithm for BAP Partitioning, I have set three milestones for the project:

M1: Basic Greedy Partitioning Algorithm. [Due: 16 Oct 2007, 23:59]
You will be assigned a simple greedy algorithm to implement -- Greedy-2007.txt
You should use the Trivial Partitioner as a reference to help your implement your assigned greedy algorithm. After successful implementation, you should test them on the benchmark datasets. You need to print out the value of the objective function obtained by your algorithm on these datasets.

M2: Your Proposed BAP Partitioning Algorithm. [Due: 23 Oct 2007, 23:59]
For this milestone, you will first do suitable literature research. You should select a solution approach and work out some of the technical details for your proposed BAP partitioning algorithm. Then write out a solution proposal for your BAP Partitioner.
(Your proposel BAP partitioner should be much better than any of the greedy algorithms!)

M3: Your very own BAP Partitioner. [Due: ~~12 Nov~~ Extended to Thu, 15 Nov 2007, 23:59]
Finally, you will implement your proposed BAP partitioner. Remember that you will need to make a lot of refinements and improvements to your algorithm after you see the experimental results on the benchmark datasets. So start early.

The BAP Partitioning Class Challenge Web-site

We have a set up a BAP Partitioning Class Challenge Website that publishes the best solutions obtained by the students in the class. As you find better solutions to each BAP instance, please submit your solution to this challenge web-site. Please read the "Help" file on the web-site.

In addition, for each student, we have set up a "Personal Score Page" that tracks the student's personal BAP partitioning results. For example, if you are user "leonghw", your personal page is at http://www-appn.comp.nus.edu.sg/~cs5234/cgi-bin/2007-08/bap-results.cgi?personal=leonghw. (Please see the "Help" page in the Challenge site for more details.)

For milestone M3, please post your own results to your "Personal Score Page" -- as this will make it easier for my graders to see your results.

For fun, you can also see the 2001 CS5234 TTP Challenge Web-site that contains the best tours obtained by 2001 class for a different problem, the Travelling Tourist Problem (TTP).

Your BAP Project Deliverables

For Milestone M1:

After you have completed your Greedy BAP Partitioner (the one that is assigned to you), please integrated your partitioner, together with the Trivial Partitioner into your version of the BAPS. Create project files (and parameter files as necessary) to run your Partitioner on all the datasets that has been given to you. (It may be useful to write some short scripts to automate this process of "running on all the datasets" as you will find it extremely useful for Phase M3 of this project.)

Give a brief report (call it BAP-M1-Rep-[your-name].doc/pdf/ps) on your greedy partitioner that includes a table of the results obtained. The table of results should contain at least, columns for the number of vessels unassigned, the transshipment cost, and the penalty cost. (An additional thing that you may want to do is to try to draw some conclusions (good, bad, or ugly) on your assigned greedy heuristic algorithm.) Put your report under a new directory called "Reports".

To submit your BAP M1 deliverables, please do the following:

first create a README-GDYnn.txt file (where nn is your assigned number) that contains instructions on how to compile and execute your programs. Even if it contains just a simple "go to directory XXX; make;".
If you have included little scripts that help you run the BAPS multiple times, please include them and also instructions on how to use them in the README.txt file.
Also make sure you include the solution files produced by your partitioner (these should be in a separate directory).
Include your report in the directory called "Reports" as described above.
Zip everything into a zip file called CS5234-BAP-M1-[your-name].zip.
Submit this zip file to CS5234 IVLE workbin called "CS5234-BAP-M1".
(Go to CS5234 IVLE Page here. Click "Workbin", View it, then Click "CS5234-BAP-M1" Folder. Submit there.)

For Milestone M2: [Due: 23 Oct 2007, 23:59]

Write up your solution proposal as a 2-page document that outlines your proposed algorithm (with some details to make it understandable for me) and call it BAP-M2-Prop-[your-name].doc/pdf/ps and submit this zip file to CS5234 IVLE workbin called "CS5234-BAP-M2".

For Milestone M3: [Due: 12 Nov Extended to Thu, 15 Nov 2007, 23:59]

(Submit to Your "Personal Page") -- After you have run your M3 algorithm on the datasets, please submit to "Your Personal Page" on the BAP Partitioning Class Challenge web-site. You are free to re-submit improved solutions as you get them (as many times as you like).

Your BAP Report -- For Milestone M3, you should write a proper project report that should have (at least) the following sections:

No:	Section Name	Description
1.	Problem Statement	Explain the BAP partitioning problem.
2.	Overview of Your Algorithm for M3	Explain the general idea(s) behind your BAP partitioning algorithm for M3. Give possible reasons why you think it should give good results for BAP partitioning.
2.	Details of Your Algorithm for M3	Give the technical details of your algorithm here. Together with information on how you implemented it. Clearly state any parameters you have in your algorithm and describe briefly how you choose their values.
3.	Complexity Analysis	Analyse the time complexity of your algorithm.
4.	Result and Observations	Results obtained by your ~~greedy~~ M3 algorithm, observations, if any, and recommendations for better approaches.

Please put your report in your BAP code, under the directory "Report".
Again, include a README file to help us compile and run your code.
Then, zip everything into a zip file called CS5234-BAP-M3-[your-name].zip.
Submit this zip file to CS5234 IVLE workbin called "CS5234-BAP-M3".

BAP Partitioning Challenge Project, (CS5234, SoC, NUS)

Combinatorial and Graph Algorithms School of Computing, National University of Singapore (CS5234, Fall 2007) The BAP Partitioning Challenge Milestone M3 : [Extended to Thu, 15 Nov 2007, 23:59]