Heuristics for Multidimensional Packing Problems

Ph.D. - Forsvar

Jens Egeblad, Heuristics for Multidimensional Packing Problems


The field of solving packing problems is an exciting application of computer science using techniques from computational geometry, operations research, efficient data-structures, fast algorithms, and plain hard-core optimized code.

Loosely defined, a packing problem asks for a non-overlapping placement of items within one or more containers that has maximal utilization. Items and containers may be rectangular or irregular (e.g. polygons and polyhedra). Although packing problems appear in several settings, they receive increasing interest from the industry, where high quality solutions can reduce transportation and production costs significantly. The problems and solution methods considered in the dissertation are mostly application-oriented and presented in the form of six individual papers.

The first two papers present a heuristic for, respectively, two and three-dimensional strip-packing problems with irregular shapes. The strip-packing problem asks for a minimum height container capable of enclosing the items. Experimental results are among the best published in the literature.

The next two papers present heuristics for variants of knapsack packing problems. In the knapsack packing problem, each item is given a profit value, and we seek a subset of the items with maximal profit-sum that can be placed within one container. In particular, one of the presented heuristics considers container loading of furniture (irregular items), and is now being used by one of world's largest furniture producers to solve hundreds of problems per day.

To further investigate the versatility of the relaxed placement method, the two final papers consider its application to weight-balanced placement of items, and a type of RNA-structure prediction problem that asks for a non-overlapping placement of interconnected cylinders within an irregular container.

In the talk I will focus on the solution methods for the strip-packing problem and container loading of furniture, and give a brief presentation of  the RNA prediction problem.


Professor Andrea Lodi (DEIS University of Bologna)
Professor Jose Fernando Oliveira (Departamento de Engenharia Electrotécnica e de Computadores)
Professor Pawel Vinter (DIKU, University of Copenhagen)
Vejleder: Professor David Pisinger (DIKU, University of Copenhagen)

Ønskes afhandlingen fremsendt som pdf-fil, skriv til Lorena: lorena@diku.dk med kopi til Kristina Kunak: kunak@diku.dk.