I am working on a practical problem which requires a theoretical analysis. Specifically, the problem is:

Given a list of items, each enclosed in a rectangular box and with a given weight, and given a list of wood containers, each with its cost, find the optimal distribution of the items in the containers. I mean: each container should no exceed a given weight, and the overall cost should be minimum.

At first I ignored the weight constaint and just looked for a solution to the following problem:

Find the optimal (minimum overall cost) number of containers (for each available type) such that the overall volume available in the containers is Greater than the overall volume of the items to be packed.

This second problem is easily solved numerically; namely, I just set up the problem in an Excel spreadsheet and used Excel's built-in solver to solve by the Simplex method.

Now the fist problem seems to be nonlinear: one has to decide

  1. How many items (of each type) to put into a container (of each type)
  2. How many containers (of each type) to use

I set it up at first by ignoring the weight constaint. I did it this way:

  1. For containers of type $i$, let $N_{ij}$ be the number of items of type $j$ included;
  2. For containers of type $i$, let $M_i$ be the number of containers required;
  3. Let $V_j$ be the volume of item $j$, and $U_i$ the available volume in container $i$;
  4. The first constraint is: $\sum_j N_{ij} V_j \leq U_i$, for each $i$;
  5. Let $P_j$ be the overall number of items $j$;
  6. The second constraint is: $\sum_i N_{ij} M_i = P_j$, for each $j$.

If $C_i$ is the cost of container of type $i$, the overall cost is $\sum_i M_i C_i$. One has to find the $N_{ij}$ and the $M_i$ such that the overall cost is minimum.

With this setup, Excel is completely unable to solve (tried with all available algorithms): either no solution, or a clearly non-optimal solution.

May anybody clarify to me how such a problem should be addressed, and if any tool is available to solve it numerically without programming effort?


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.