5
$\begingroup$

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:

enter image description here

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:

enter image description here

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.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 :-) $\endgroup$
    – bjornte
    Nov 14, 2022 at 8:57
  • $\begingroup$ This answer is supported by this comment on GitHub $\endgroup$
    – bjornte
    Nov 20, 2022 at 13:55
  • $\begingroup$ 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. $\endgroup$
    – bjornte
    Nov 22, 2022 at 22:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.