MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).

How do I solve this problem?

share|cite|improve this question
crosspost… – Will Jagy Apr 6 '13 at 1:09

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.