Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

A novel non-linear approach to minimal area rectangular packing

 
: Maag, V.; Berger, M.; Winterfeld, A.; Küfer, K.-H.

:

Annals of operations research 179 (2010), 1, pp.243-260
ISSN: 0254-5330
ISSN: 1572-9338
English
Journal Article
Fraunhofer ITWM ()

Abstract
This paper discusses the minimal area rectangular packing problem which is to pack a given set of rectangles into a rectangular container of minimal area such that no two rectangles overlap. Current approaches for this problem rely on metaheuristics like simulated annealing, on constraint programming or on non-linear models. Difficulties arise from the non-convexity and the combinatorial complexity. We investigate different mathematical programming approaches for this and introduce a novel approach based on non-linear optimization and the “tunneling effect” achieved by a relaxation of the non-overlapping constraints. We compare our optimization algorithm to a simulated annealing and a constraint programming approach and show that our approach is competitive. Additionally, since it is easy to extend, it is also applicable to a variety of related problems.

: http://publica.fraunhofer.de/documents/N-151203.html