{{short description|Optimization problem in mathematics}} '''Rectangle packing''' is a packing problem where the objective is to determine whether a given set of small rectangles can be placed inside a given large polygon, such that no two small rectangles overlap. Several variants of this problem have been studied.
== Packing identical rectangles in a rectangle == In this variant, there are multiple instances of a single rectangle of size (''l'',''w''), and a bigger rectangle of size (''L'',''W''). The goal is to pack as many small rectangles as possible into the big rectangle without overlap between any rectangles (small or large). Common constraints of the problem include limiting small rectangle rotation to 90° multiples and requiring that each small rectangle is orthogonal to the large rectangle.
This problem has some applications such as loading of boxes on pallets and, specifically, woodpulp stowage. As an example result: it is possible to pack 147 small rectangles of size (137,95) in a big rectangle of size (1600,1230).<ref>{{cite journal|last1=Birgin|first1=E G|last2=Lobato|first2=R D|last3=Morabito|first3=R|year=2010|title=An effective recursive partitioning approach for the packing of identical rectangles in a rectangle|journal=Journal of the Operational Research Society|volume=61|issue=2|pages=306–320|doi=10.1057/jors.2008.141|s2cid=12718141}}</ref>
== Packing identical squares in a rectilinear polygon == Given a rectilinear polygon (whose sides meet at right angles) ''R'' in the plane, a set ''S'' of points in ''R'', and a set of identical squares, the goal is to find the largest number of non-overlapping squares that can be packed in points of ''S''.
Suppose that, for each point ''p'' in ''S'', we put a square centered at ''p''. Let ''G''<sub>S</sub> be the intersection graph of these squares. A square-packing is equivalent to an independent set in ''G''<sub>S</sub>. Finding a largest square-packing is NP-hard; one may prove this by reducing from 3SAT.<ref>{{Cite journal|last1=Fowler|first1=Robert J.|last2=Paterson|first2=Michael S.|last3=Tanimoto|first3=Steven L.|date=1981-06-13|title=Optimal packing and covering in the plane are NP-complete|url=https://dx.doi.org/10.1016/0020-0190%2881%2990111-3|journal=Information Processing Letters|language=en|volume=12|issue=3|pages=133–137|doi=10.1016/0020-0190(81)90111-3|issn=0020-0190|url-access=subscription}}</ref>
== Packing different rectangles in a given rectangle == In this variant, the small rectangles can have varying lengths and widths, and they should be packed in a given large rectangle. The decision problem of whether such a packing exists is NP-hard. This can be proved by a reduction from 3-partition. Given an instance of 3-partition with 3''m'' positive integers: ''a''<sub>1</sub>, ..., ''a''<sub>3''m''</sub>, with a total sum of ''m T'', we construct 3''m'' small rectangles, all with a width of 1, such that the length of rectangle ''i'' is ''a<sub>i</sub>'' + ''m''. The big rectangle has width ''m'' and length ''T'' + 3''m''. Every solution to the 3-partition instance induces a packing of the rectangles into ''m'' subsets such that the total length in each subset is exactly ''T'', so they exactly fit into the big rectangle. Conversely, in any packing of the big rectangle, there must be no "holes", so the rectangles must not be rotated. Therefore, the packing must involve exactly ''m'' rows where each row contains rectangles with a total length of exactly ''T''. This corresponds to a solution of the 3-partition instance.<ref>{{Cite journal|last1=Demaine|first1=Erik D.|last2=Demaine|first2=Martin L.|date=2007-06-01|title=Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity|url=https://doi.org/10.1007/s00373-007-0713-4|journal=Graphs and Combinatorics|language=en|volume=23|issue=1|pages=195–208|doi=10.1007/s00373-007-0713-4|s2cid=17190810 |issn=1435-5914|url-access=subscription}}</ref><ref name=":0">{{Cite web|last=Demaine|first=Erik|date=2015|title=MIT OpenCourseWare – Hardness made Easy 2 – 3-Partition I|url=https://www.youtube.com/watch?v=ZaSMm2xvatw|archive-url=|archive-date=|access-date=|website=Youtube}}</ref>
When there is an additional restriction that the packing must be exact (with no wasted space), the small rectangles may be rotated only by multiples of 90°. In this case, the problem is in NP. Without this requirement, the small rectangles may be rotated in arbitrary angles. In this more general case, it is not clear if the problem is in NP, since it is much harder to verify a solution.<ref name=":0" />
== Packing different rectangles in a minimum-area rectangle == In this variant, the small rectangles can have varying lengths and widths, and their orientation is fixed (they cannot be rotated). The goal is to pack them in an enclosing rectangle of minimum area, with no boundaries on the enclosing rectangle's width or height. This problem has an important application in combining images into a single larger image. A web page that loads a single larger image often renders faster in the browser than the same page loading multiple small images, due to the overhead involved in requesting each image from the web server. The problem is NP-complete in general, but there are fast algorithms for solving small instances.<ref>{{Cite journal|last1=Huang|first1=E.|last2=Korf|first2=R. E.|author2-link=Richard E. Korf |date=2013-01-23|title=Optimal Rectangle Packing: An Absolute Placement Approach|journal=Journal of Artificial Intelligence Research|volume=46|pages=47–87|doi=10.1613/jair.3735|issn=1076-9757|doi-access=free|arxiv=1402.0557}}</ref><ref>{{Cite web|title=Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites|url=https://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu|access-date=2020-09-09|website=www.codeproject.com|date=14 June 2011 |language=en-US}}</ref>
== Integer programming formulation==
One can model rectangle packing problem for fixed sizes and orientations as an integer linear program. Further, constraints and variables can be added to minimize the bounding-box-netlength. Given small rectangles <math>R_1,...R_n</math> with widths <math>w_1,...,w_n</math>, heights <math>h_1,...,h_n</math> and nets <math> \mathcal{N}_1,...,\mathcal{N}_n</math> as well as a larger rectangle with width <math>W</math> and height <math>H</math>, the integer program looks as follows: * '''Objective minimizing bounding-box-netlength''' ::<math> \min \sum_{N \in \cup_{i=1}^n\mathcal{N}_i} y_{N,t} - y_{N,b} + x_{N,r} - x_{N,l} </math>
* '''Non-overlap constraints''' : ::<math> \begin{matrix} x_i + w_i \leq x_j + W(1 - R_{j,i}) \\ y_i + h_i \leq y_j + H(1 - A_{j,i}) \end{matrix} \quad \forall\ 1 \leq i \ne j \leq n </math> * '''Relative placement disjunction''' : ::<math> R_{j,i} + R_{i,j} + A_{j,i} + A_{i,j} \geq 1 \quad \forall\ 1 \leq i \ne j \leq n </math>
*'''Net bounding box coverage constraints''' : ::<math> \begin{matrix} x_{N,r} \geq x_i + w_i \\ x_{N,l} \leq x_i \\ y_{N,t} \geq y_i + h_i \\ y_{N,b} \leq y_i \end{matrix} \quad \forall\ i \in {1, \ldots, n},\ N \in \mathcal{N}_i </math>
*'''Binary variables''' : ::<math> \begin{matrix} R_{i,j} \in {0, 1} \\ A_{i,j} \in {0, 1} \end{matrix} \quad \forall\ 1 \leq i \ne j \leq n </math>
*'''Rectangle position variables''' : ::<math> \begin{matrix} x_i \in {0, \ldots, W - w_i} \\ y_i \in {0, \ldots, H - h_i} \end{matrix} \quad \forall\ i \in {1, \ldots, n} </math> *'''Net bounding box variables''' : ::<math> \begin{matrix} x_{N,l},\ x_{N,r} \in {0, \ldots, W} \\ y_{N,b},\ y_{N,t} \in {0, \ldots, H} \end{matrix} \quad \forall N \in \cup_{i=1}^n\mathcal{N}_i </math>
For fixed relations <math>R_{i,j}, A_{i,j}</math> the above integer program is the dual of a maximum flow problem and therefore solvable in polynomial time.<ref name="Funke2016">{{Cite journal |last1 = Funke |first1 = Julia |last2 = Hougardy |first2 = Stefan |last3 = Schneider |first3 = Jan |title = An exact algorithm for wirelength optimal placements in VLSI design |journal = Integration: The VLSI Journal |year = 2016 |volume = 52 |pages = 355–366 |doi = 10.1016/j.vlsi.2015.07.001 |url = https://doi.org/10.1016/j.vlsi.2015.07.001 |access-date = 2025-06-12 }} </ref>
Not all choices for these spatial relation variables correspond to a feasible placement. A set of relations that contains all feasible placements is called complete. The best known upper bound on the size of a complete set of relations was proved by Silvanus and Vygen, who showed that <math> O\left( n! \cdot C^n /n^6 \right) </math> with <math>C = (11 + 5\sqrt{5})/{2}</math> spatial relations suffice. They also gave a lower bound of <math> O\left( n! \cdot c^n /n^6 \right) </math> with <math>c = 4 + 2\sqrt 2.</math><ref name="Silvanus2017"> {{cite journal | last1 = Silvanus | first1 = Jannik | last2 = Vygen | first2 = Jens | title = Few Sequence Pairs Suffice: Representing All Rectangle Placements | journal = SIAM Journal on Discrete Mathematics | volume = 34 | year = 2017 | pages = 2017–2032 | doi = 10.1137/16M1095880 | doi-broken-date = 1 July 2025 }} </ref>
'''Heuristics'''<br /> Using different representations such as O-trees,<ref name="Tang2005"> {{cite conference | last1 = Tang | first1 = M. | last2 = Sebastian | first2 = A. | title = A Genetic Algorithm for VLSI Floorplanning Using O-Tree Representation | book-title = Applications of Evolutionary Computing | series = Lecture Notes in Computer Science | volume = 3449 | pages = 215–224 | year = 2005 | publisher = Springer Berlin Heidelberg | doi = 10.1007/978-3-540-32003-6_22 }} </ref> B*-trees<ref name="Fernando2008"> {{cite conference | last1 = Fernando | first1 = J. | last2 = Katkoori | first2 = S. | title = An Elitist Non-dominated Sorting Based Genetic Algorithm for Simultaneous Area and Wirelength Minimization in VLSI Floorplanning | book-title = Proceedings of the 21st International Conference on VLSI Design | pages = 337–342 | year = 2008 | publisher = IEEE | doi = 10.1109/VLSI.2008.56 }} </ref> or sequence pairs<ref name="Lin2009"> {{cite journal | last1 = Lin | first1 = P.-H. | last2 = Chang | first2 = Y.-W. | last3 = Lin | first3 = S.-C. | title = Analog Placement Based on Symmetry-Island Formulation | journal = IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems | volume = 28 | issue = 6 | pages = 791–804 | year = 2009 | publisher = IEEE | doi = 10.1109/TCAD.2009.2015708 | doi-broken-date = 1 July 2025 }} </ref> for the spatial relations between rectangles, various heuristic algorithms have been proposed to solve floorplanning instances in practice. Some of them restrict the solution space by only considering '''sliceable''' floorplans.
== Related problems ==
* '''Guillotine cutting''' is a variant of rectangle packing, with the additional constraint that the rectangles in the packing should be separable using only ''guillotine cuts''.
* '''Maximum disjoint set''' (or '''Maximum independent set''') is a problem in which both the sizes and the locations of the input rectangles are fixed, and the goal is to select a largest sum of non-overlapping rectangles. In contrast, in rectangle packing (as in real-life packing problems) the sizes of the rectangles are given, but their locations are flexible. Some papers use the term "packing" even when the locations are fixed.<ref name="Chan2003">{{Cite journal |last1=Chan |first1=T. M. |year=2003 |title=Polynomial-time approximation schemes for packing and piercing fat objects |journal=Journal of Algorithms |volume=46 |issue=2 |pages=178–189 |citeseerx=10.1.1.21.5344 |doi=10.1016/s0196-6774(02)00294-8}}</ref>
* Circle packing in a rectangle * Square packing in a square * De Bruijn's theorem: packing congruent rectangular bricks of any dimension into rectangular boxes.
== References == <references /> Category:Packing problems Category:Geometric algorithms Category:NP-hard problems