Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have been tasked with optimizing a manufacturing process. It is a non-trivial, NP hard problem. The problem is similar to the 2d bin packing problem, but we are trying to optimize the size of the bins.

The Problem:

Small rectangular shapes must be packed into larger rectangles in an optimal way. There are nesting algorithms to do this optimization where the large rectangle dimensions are inputs. However, we want to optimize the dimensions of the large rectangles.

The inputs are:

-A list of unique small rectangles. The list includes the dimensions of the small rectangles, a number that represents the rectangle’s frequency of usage relative to the other small rectangles, and the orientation (whether or not it can be rotated 90 degrees)

-The maximum number of large rectangle dimensions. And the minimum and maximum dimensions of the large rectangles.

The output is an optimized list of large rectangle dimensions.

Proof One way to prove the validity of the result is by creating a nest of the small rectangles within the large rectangles. Here is a paper and an open source project that provides a solution to the 2d bin packing problem that we are currently using to nest. We are using the Maximal Rectangle algorithm and we vary the heuristics (typically bottom left or contact point heuristics).

http://clb.demon.fi/files/RectangleBinPack.pdf https://github.com/juj/RectangleBinPack

How do I solve this problem?

share|improve this question
Also posted at mathoverflow.net/questions/126672/… –  Joel Reyes Noche Apr 6 '13 at 9:01
This sounds like the cutting stock problem. You should talk to this guy. (Actually, he should talk to you.) –  Douglas B. Staple Apr 15 '13 at 19:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.