6.338J Final Project
(Updated) Progress Report

Asanka Herath (asanka AT mit.edu)
Buddhika Kottahachchi (buddhika AT mit.edu)

Based on the work we've done in the past week, the progress made and the lessons learned, we have had to re-think our strategy and re-scope the problem we wish to solve as part of our final project. However, we believe the new focus does not take away from our original objective. Therefore, we first re-state our project objective in a more concrete manner.

Project Objective
To explore the intuition that applying a parallel approach to a search problem not only allows us to deal with problems that have large search spaces, but that applying branch and bound techniques to the parallelized approach actually reduce the subset of the search space that needs to be traversed before reaching the desired solution. (ie. we wish to show a relationship between the number of nodes used and the size of the subset of the search space that actually needs to be traversed while searching for a solution).

Given this objective, and our belief that we had found a reasonable starting point based on some previous work done in Denmark (report), we framed the project originally towards practical applications in the apparel industry. Unfortunately, the authors of the aforementioned report declined to work with us and so, we were left with the option of replicating some of their work. In order to do so, we needed a means to manipulate polygons. We considered writing our own library for this, realized it was a futile exercise and then considered FastGEO (an object Pascal based geometry library) and CGAL (a C++ based geometry library). CGAL didn't have the functionality we desired (ie. even simple boolean operations on polygons required convoluted coding), but FastGEO was promising. However, manually porting it to C or C++ was not possible in the given time frame. We did attempt to do an automated port using PtoC but that wasn't successful.

At this point we stepped back and re-examined our goals. Writing a geometry library didn't seem to fit well with the goals of our project and of the class. So, we tried to re-scope what we will be implementing.

Our new implementation goals are as follows:
Implement a solution to a specialized case of the bin-packing problem where we consider a 2D constant width W, variable height H bin being filled with rectangles of arbitrary dimensions (fulfilling the condition that a given rectangle can be placed in a bin of width W). Our solution will optimize H for a given set of rectangles. We will be running independent instances of the search on multiple nodes and will be co-ordinating the branch and bound operations via the front-end. Thus, once a particular node finds a partially optimal solution H1 none of the nodes will thereafter explore candidate solutions that exceed H1. We will also collect empirical data of the search space that was actually traversed against the number of nodes used, in order to provide evidence supporting our thesis.

Progress Made
General design of the code structure.
A Rectangle class implementing the set of operations we desire . These include intersection detection, rotation(to simplify things we only consider 2 orientations: horizontal and vertical).
I/O functionality to load problems and save solutions.

Need to be done
The serial solution generator (bounded exhaustive).
The front-end branch and bound co-ordinator.
Visualization functionality.
Data collection functionality.

Potential Issues
Ensuring that all the nodes are working on different candidate solutions (ie. avoid redundancy).
Simply sharing bounds might not give enough of an improvement to compensate for the overhead of parallelization and still demonstrate an improvement.  We are considering several methods of sharing optimal bounds for subproblems which could be implemented if time permits.

Last modified on 04/24/2004