Nesting algorithm for rectangular-based, fixed-orientation polygons

I'm looking for an algorithm that is closely related to the 2-dimensional nesting problem (also known as lay planning, bin packing, and the cutting stock problem).

The main differences between this and normal nesting are:

• A fixed number of elements to be placed
• The elements cannot rotate
• The elements must be placed in as small an area as possible, as opposed to placing as many pieces as possible in a fixed-size area.
• The elements are rectangular pieces with 0-4 fixed-orientation rectangular corner cutouts (“Utah-like”), as opposed to being randomly shaped

Input: n “Utah-like”, fixed-orientation polygons. n is in the range 1-20. The figures are not shaped to align perfectly with each other. Example figure set:

Desired output: A fixed-orientation nesting for a scaleable area with predefined proportions. The scaleable area should be scaled to fit the nested figures as snugly as possible, like so:

Note the area where the figures' rectangular boundaries overlap, preventing this from being a more trivial rectangle-packing problem.

I have perused several packing questions on SE (e.g. 1, 2, 3) as well as puzzle-solving questions (e.g. 1, 2, 3), and also outside Stack Exchange (1, 2, 3), but they don't describe this particular problem or don't include source code. Related GitHub repos: 1, 2, 3. Online solvers: SVGnest.com and Nestable.xyz.

I will describe how you can solve this with an ILP (integer linear programming) solver. For the size of problem you have, I expect it will work acceptably well.

Let's focus on just two of your shapes, say shape $$S_i$$ and $$S_j$$. Let $$(x_i,y_i)$$ denote the position of some fixed point of $$S_i$$ (say, the lower-left corner), and $$(x_j,y_j)$$ the position of some fixed point of $$S_j$$. Then it is possible to write down a formula $$\Phi_{i,j}$$ that captures the condition that $$S_i,S_j$$ do not overlap. This formula will have the form

$$(x_j-x_i \ge \alpha_1 \land y_j-y_i \ge \beta_1) \lor \cdots (x_j-x_i \ge \alpha_k \land y_j-y_i \ge \beta_k),$$

except that some $$\ge$$'s might be replaced with $$\le$$. Here the $$\alpha,\beta$$ values are constants that can be easily calculated from the shapes $$S_i,S_j$$. We can express $$\Phi_{i,j}$$ in a form suitable for use with an ILP solver using the methods in Express boolean logic operations in zero-one integer linear programming (ILP). In particular, we can encode $$\Phi_{i,j}$$ as the linear inequalities

\begin{align*} x_j-x_i &\ge \alpha_1 - C(1-t_1)\\ y_j-y_i &\ge \beta_1 - C(1-t_1)\\ &\vdots\\ x_j-x_i &\ge \alpha_k - C(1-t_k)\\ y_j-y_i &\ge \beta_k - C(1-t_k)\\ t_1 + \cdots + t_k &\ge 1 \end{align*}

except that whenever you replace $$\ge$$ with $$\le$$, you also replace $$-C(1-t_u)$$ with $$+C(1-t_u)$$. Here, $$t_1,\dots,t_k$$ are fresh new variables that are specific to $$\Phi_{i,j}$$, and they are constrained to be integers and constrained to be 0 or 1 (via the inequalities $$0 \le t_1 \le 1$$, etc.) Also $$C$$ is a large constant.

Finally, introduce a variable $$z$$, which represents the width of the containing rectangle. The containing rectangle's height will be $$\gamma z$$ where $$\gamma$$ is a known constant (the aspect ratio).

Add constraints to ensure that all shapes fit within the rectangle $$[0,z] \times [0,\gamma z]$$. In particular, for shape $$S_i$$, we obtain inequalities on $$x_i,y_i$$ (something like $$0 \le x_i \le z-\text{width}(S_i)$$, $$0 \le y_i \le \gamma z - \text{height}(S_i)$$ if $$(x_i,y_i)$$ is the lower-left corner of $$S_i$$, but the exact inequalities may vary depending on which fixed point of $$S_i$$ you chose).

Add the linear inequalities for each $$\Phi_{i,j}$$, for every pair $$i,j$$ with $$i\ne j$$.

The objective function is to minimize $$z \ge 0$$.

Finally, solve the resulting ILP instance obtained in this way. This should give you an optimal nesting.

• This seems like a great lead! I have no previous experience with integer linear programming, but your answer has motivated me to start on a primer :-) Nov 14, 2022 at 8:57
• This answer is supported by this comment on GitHub Nov 20, 2022 at 13:55
• D.W., do you know of any repository with ILP code for bin packing, strip packing or nesting? E.g. written in Python or JavaScript? My thought was to try and implement a more basic ILP strip packing proof of concept (PoC) first, and then work on the more complex nesting problem if I could solve the PoC. Nov 22, 2022 at 22:12