Nesting rectangles/squares into rectangular sheets
Optimal nesting and practical limits: When considering different nesting options while searching for an optimal nesting solution, it is desirable to find the solution quickly. This begs the question: how do I know a solution is optimal? The answer is not always obvious.
An automated nesting search is part of the answer, which can explore a number of options quickly, automatically and report the results: finding the maximum number of parts in a full sheet or finding the smallest sized sheet required for a given number of parts.
The spacing between the rectangles/squares and the spacing to the edges has been left undefined in your problem. For real-life problems the spacing is non-zero. For Laser-cutting the kerf (width of cut) is generally 0.3mm. In addition, generally in that industry 5mm spacing is used perhaps less. That said, I have assumed zero spacing as per your question. A mixture of rotations is assumed: either 0 degrees or 90 degrees. It is unstated if the material is cut with a guillotine which would limit the arrangements possible. Non-guillotine cutting is assumed.
Note that no single nesting method gives the optimum yield for nesting every size rectangle into every sized sheet.
The optimum nesting method varies depending on the rectangle sizes and sheet dimensions. Hence a simple formula approach is not appropriate.
Rectangle Packing Software
This rectangle packing software calculates and compares five different packing methods and highlights the most efficient solutions. The user can highlight each nesting variation to dynamically compare sheet options and mixed rotations. The software actually explores many more options than this but only displays the maximum number for each type of nesting.
It can be an advantage to have a working knowledge of these expected packing efficiencies of typical cases. (See efficiency graph)
Rectangular nesting search options
Rectangular nesting search options: In early versions of this rectangular nesting software it was assumed the optimum rectangular nesting would be found by simply checking 0 vs 90 degree packing with perhaps one (1) extra row rotated 90 degrees (Example A or B). When re-writing the software, instances were noticed where true optimum packing would require a different search (Example D) using Diophantine Equations. Additionally, arrays of four rectangles in square sub-nests can be optimal in some instances (Example E).
Graphing the packing efficiency vs rectangle dimensions into a rectangular plate
Using the rectangular packing software, the best packing efficiencies of each sized rectangle into a standard sheet size can be graphed.
Nesting efficiency 1
Nesting efficiency 2
The nesting efficiency of rectangles packed into a rectangular sheet (3000x1500mm)
(2 views of the same 3D graph).
Note the general non-linear nature with 80-90% efficiency, small local peaks of 90-100% efficiency and pits of lower efficiency <80%.
Hence, when designing products, high efficiency material use could be achieved if the part sizes are within these local peaks.
Using these results in a practical sense helps halt the search with confidence if adding another rectangle (N+1) would require an efficiency that, by the graph, is not possible. Optimal packing algorithms for rectangles in rectangles is continually being researched and improved.
Packing efficiency of Rectangles into a 320x320mm sheet
From the 3D Packing efficiency graph it can be seen how non-uniform the efficiency is and hence how unlikely a simple formula is.
I have included a .CSV EXCEL table here, with data generated from the above software, noting the maximum number of rectangles from a 320x320mm sheet for each part length and width.
.CSV file link
Of course the actual arrangement of each optimal solution is not included in the spreadsheet but is displayed by the software.
McErlean, P. (2018) "The CAD/CNC Programming Handbook: 2D Material Optimization and Tips for Laser, Plasma and Oxy profile cutting"
I'm not sure if this is optimal, but it works.
My collection optimises "no wasted space", and it also minimises the number of boxes required in the sense that "the most efficient tiling of any space" is obtained by using the biggest boxes first. However, you may feel that there are too many boxes.
For $2$-dimensional space, I use $(x,y)$ to denote rectangles with side lengths $x$ and $y$.
- $\{(1,1), (1,2), (1,2), (2,2)\}$ will fill all spaces (with integer sides) up to $3\times 3$ with no gaps (with the greedy algorithm)
- $\{(1,1),(1,2),(1,2),(1,4),(1,4),(2,2),(2,4),(2,4),(4,4)\}$ will fill all spaces with integer sides up to $7\times 7$ with no gaps (with the greedy algorithm)
More generally, the collections of boxes are defined by:
one of each box of size $(x,x)$,
two of each box of size $(x,y)$ with $x\neq y$, where $x,y \in \{1,2,4,8,...\}$.
I conjecture that the collection of boxes generated in this way will always tile larger 2d spaces with no gaps using the greedy algorithm. (I have verified this for the two cases above, but not for e.g. $15\times 15$, $31\times 31$,...)
By "using the greedy algorithm", I mean that if you attempt to tile some space, you just have to start with the biggest box, then use the second biggest box, etc.
I suspect that there maybe a more optimal solution which makes use of golden-ratio-eqsue maths.
Best Answer
I have bad news.
Even a restricted problem where the space to fit has height $2$ and have to be filled tightly, objects are distinct rectangles of height $1$ and integer lengths, and in the placement all rectangles are axially aligned, is $NP$-hard. This is because it is equivalent to the Set Partition Problem. This problem takes as an input a set $S$ of natural numbers and the question is whether it can be partitioned into two sets $A$ and $S\setminus A$ such that $\sum_{x\in A} x=\sum_{x\in S\setminus A}$. It is $NP$-Complete (see, for instance, [N]).
When rotations and translation are allowed, the problem is strongly NP-hard and it is even not known whether it is in NP, because it is complicated to encode rotations efficiently (see [D, Sec. 2.2]).
References
[D] 6.890. Class 2 Scribe Notes. Notetakers: Jason Ku, Chelsea Voss Instructor: Erik Demaine 2014-09-09.
[N] Marvin Nakayama. *CS 341: Foundations of Computer Science II. Homework 13 Solutions.