0
$\begingroup$

So, I have an optimization/space management problem. This same question is posted on two SE sites simultaneously, Stack Overflow and Mathematics, since I think it is fitting for both.

Let's say I have containers of (X,Y) dimensions. Inside, I want to place as many smaller containers of (x_i, y_i) dimensions as possible. These smaller containers can vary in size. Inside these smaller containers, I have a given item wich is the smallest unit I have.

Basically: Items, inside variable small boxes, inside variable big boxes.

Provided I know all of the following:

  • Larger containers' dimensions.
  • Smaller containers' dimensions.
  • Ammount of all containers available to me.
  • Ammount of basic items that need to be packaged.

Is there currently a known alghorithm that can be applied to determine the following?

  • The best selection of small boxes to be used (they can vary in size).
  • The optimal ammount of large containers required for storage.
  • The appropriate placement of the smaller packages inside the larger one.

IF this is a thing that already exists, can it be extended to three dimensions, rather than only two, as my example states? That is to say, calculate packaging configurations for dimensions (x,y,z).

EXAMPLE:

I have 25 items. I have small containers of the following dimensions: 3x3, 2x2, 1x2. I have large container of 5x5.

Through trial and error (or intuition?), I can see that a valid configuration is as follows:

1 small container of 3x3 3 small containers of 2x2 2 small containers of 1x2 All inside a 5x5 container.

Now, it's a matter of tetrising/tangraming my way into a solution. So, for example, the following two are valid placements/configurations:

Valid Configurations

While this one isn't since it would require a second large container:

Invalid Configuration

$\endgroup$
1
  • $\begingroup$ I strongly suspect this is a provably hard problem. Search for knapsack problem and bin packing. $\endgroup$ – Ethan Bolker Feb 23 at 18:25

Your Answer

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

Browse other questions tagged or ask your own question.