A novel non-linear approach to minimal area rectangular packing

作者：Maag Volker^*; Berger Martin; Winterfeld Anton; Kuefer Karl Heinz

来源：Annals of Operations Research, 2010, 179(1): 243-260.

DOI：10.1007/s10479-008-0462-7

• Rectangular packing
• Non-overlapping constraints
• Non-linear optimization
• Regularization
• Relaxation

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.

• 出版日期2010-9