A novel non-linear approach to minimal area rectangular packing

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.