Efficient Algorithms for 2-D Rectangle packing
British German Academic Research Collaboration Programme
This is a project to implement and evaluate known shelf algorithms for 2-D rectangle packing problems. The goal is essentially twofold:
In the end, we expect to have a software package with all coded algorithms, and a website with all testing and evaluation results. There are two groups in the project.
The British group (from University of Liverpool) is presented by
The German group (from University of Kiel) is presented by
The experience of British group in codeing and experimental work and theoretical knowledge on approximation algorithms for packing problems by the German group can be used complementary to each other. In addition to expected results, this project primary aims at training the students in both groups.
Rectangle packing, approximation, shelf algorithms
New fast algorithmic solutions for the 2D-rectangle packing problem can have a great impact on a variety of important applications from Computer Science and Operations Research, e.g. cutting stock, VLSI design, image processing, bandwidth management, multiprocessor scheduling, just to name a few. So far, the following versions of the problem have been studied:
Even very simple cases of these problems are known to be NP-hard, and hence, it is very likely that no efficient algorithms for them exist. So, we should look for alternative algorithmic solutions.
Indeed, one can use exact methods like Integer Linear Programming, heuristic methods like Local Search and enumeration methods like Branch-and-Bound. Even if these methods could prove to be useful, the underlying algorithms are either very slow or produce very sub-optimal packings. In contrast, we aim at so-called approximation algorithms which run fast and produce near-optimal packings with quality guarantees.
Recently, we have developed a number of best quality guarantee (1+ε)-approximation algorithms. However, the design techniques used in these algorithms are quite complicated. In this project we propose to implement and evaluate so-called shelf algorithms. In the design of such algorithms, a simple shelf technique is used: order the rectangles according to a sorting rule like decreasing width, increasing height, etc. and then greedily pack them one by one in this order overpackage shelves according to some rule, like Bottom-Left, Next-Fit, First-Fit, Best-Fit, and so on. This allows a simple code design, a very fast running time, and a relatively good quality guarantee.