Rectangulation Framework for Packing Rectangles into a Rectangular Area

We propose a novel unified combinatorial formulation for the problem of packing rectangles into a single rectangle of unspecified size, in the spirit of the strip packing problem. The framework encompasses both guillotineand non-guillotine packings, as well as a broad class of objective functions and constraints. The two-dimensional bin-packing problem is beyond the scope of this paper.In the proposed formulation, the combinatorial domain consists of feasible configurations that can be enumerated autonomously. Every feasible packing is represented as a rectangulation. We introduce an equivalence relation on the set of rectangulations and describe the equivalence classes using a family of recursive combinatorial d-codes. The quotient set ofrectangulations is bijective with the set of d-codes. The autonomous enumeration of the set of d-codes follows from the recursive structure of the d-codes. For each d-code, the width and height of the bounding rectangleof the corresponding packing are expressed as two max-plus polynomials in terms of the dimensions of the rectangles of the given instance. The proposed model places the rectangle packing problem within a coherent family of well-posed planar geometric NP-hard optimization problems. Standard solution methods are applicable in this setting, including widely used approaches within the framework of parameterized complexity.