Optimal paper-cutting

Question

I have a paper size $25 \text{ inches} \times 35.5\text{ inches}$. I need to print $8.268 \text{ inches} \times 11.693 \text{ inches}$ (A4) size in the big paper. How to maximize the number of paper that I can get from it? How to model this?

Answer 1

A $3\times3$ arrangement is possible, and there will be $17.4$ square inches left over. As an A4 sheet has an area of $>17.4$ square inches no arrangement in the world will allow to obtain $10$ sheets.

Here the invariant "area" has allowed to circumvent a difficult impossibility proof in terms of combinatorial geometry.

Answer 2

If you assume that only horizontal and vertical orientations are allowed (in other words, all cuts of the original sheet are parallel to an axis), you can use either mixed integer linear programming or constraint programming to solve a problem like this. This is a well-studied problem. The search phrase to use is "two-dimensional cutting stock problem". (If cuts must go all the way across the piece, every cut going from one edge all the way to the opposite edge, I believe you want to add the term "guillotine" to the search phrase.)