0
$\begingroup$

Suppose a cuboid $\mathbb{A}$ has $L$,$M$ and $N$ as its length, width and height respectively, where $L\ge{M}\ge{N}>0$; Now we want to cut $\mathbb{A}$ into smaller cuboids with length $x$, width $y$ and height $z$ respectively, where $x\ge{y}\ge{z}>0$, $L\ge x$, $M\ge{y}$ and $N\ge{z}$.

How to design an algorithm to obtain as many as possible smaller cuboids and give all the feasible cutting methods.

For example, when $x=y=2,z=1$, and $L=M=N=3$ an optimal solution is: at most 6 small cuboids, and typical cutting mode:enter image description here

$\endgroup$
2
$\begingroup$

This problem looks like a variant of a cutting stock problem. The general idea is to set up an optimization problem that encodes the geometric constraints (in your case, the cuboid shapes) and the objective (maximizing the number of cuboids). In the paper industry, the classical example is the 1-D cutting stock problem, where you try to cut a roll of paper into various lengths to satisfy demands for various products while minimizing the paper wasted (because the remnants cannot be sold as product). The 1-D cutting stock problem is a mixed-integer linear program, and I would not be surprised if your instance were also mixed-integer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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