This paper considers the two dimensional rectangular packing problem. The mathematical formulation is based on the optimization of a non-linear function with piecewise linear constraints with a small number of real variables. The presented method of m-M calculus finds all optimal solutions on small instances. Computational performance is good on smaller instances. | Yugoslav Journal of Operations Research 21 (2011), Number 1, 93-102 DOI: SOLVING THE TWO-DIMENSIONAL PACKING PROBLEM WITH m-M CALCULUS Aleksandar SAVIĆ, Faculty of Mathematics, University of Belgrade aleks3rd@ Tijana ŠUKILOVIĆ, Faculty of Mathematics, University of Belgrade tijana@ Vladimir FILIPOVIĆ Faculty of Mathematics, University of Belgrade vladofilipovic@ Received: July 2010 / Accepted: May 2011 Abstract: This paper considers the two dimensional rectangular packing problem. The mathematical formulation is based on the optimization of a non-linear function with piecewise linear constraints with a small number of real variables. The presented method of m-M calculus finds all optimal solutions on small instances. Computational performance is good on smaller instances. Key words: Non-linear optimization, m-M calculus, two dimensional packing. MSC: 90C30, 90C56 1. INTRODUCTION Packing problem and the closely related problem of cutting, encompass a wide range of industry originated problems. A successful optimal solution, or even finding an approximately good solution, significantly facilitate in both saving money and raw materials. Most of the contributions in literature are devoted to the case where the items to be packed have a fixed orientation with respect to the stock unit(s), ., it is not allowed to rotate them. This case, which is the object of the present article, reflects a number of 94 A. Savić, T. Šukilović, V. Filipović / Solving 2-dim. Packing Problem practical contexts, such as the cutting of corrugated or decorated material (wood, glass, clothing stripes), or the newspapers paging. For variants allowing rotations (usually by 90º) and/or constraints on the items placement (such as the ‘‘guillotine cuts’’) the reader is referred to [1, 8], where a threefield classification of the area is also introduced. General surveys on cutting and packing problems can be found in [10, 11, 12]. .
