Rectangle packing
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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.
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 R_1,...R_n with widths w_1,...,w_n , heights h_1,...,h_n and nets \mathcal{N}_1,...,\mathcal{N}_n as well as a larger rectangle with width W and height H , the integer program looks as follows: Objective minimizing bounding-box-netlength \min \sum_{N \in \cup_{i=1}^n\mathcal{N}_i} y_{N,t} - y_{N,b} + x_{N,r} - x_{N,l} Non-overlap constraints \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 Relative placement disjunction R_{j,i} + R_{i,j} + A_{j,i} + A_{i,j} \geq 1 \quad \forall\ 1 \leq i \ne j \leq n Net bounding box coverage constraints \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 Binary variables \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 Rectangle position variables \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} Net bounding box variables \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 For fixed relations R_{i,j}, A_{i,j} the above integer program is the dual of a maximum flow problem and therefore solvable in polynomial time. 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 O\left( n! \cdot C^n /n^6 \right) with C = (11 + 5\sqrt{5})/{2} spatial relations suffice. They also gave a lower bound of O\left( n! \cdot c^n /n^6 \right) with c = 4 + 2\sqrt 2. Heuristics Using different representations such as O-trees, B*-trees or sequence pairs 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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1373910553 under CC BY-SA 4.0; modifications have been made.