Guidelines require to solve a mathematical intensive (or machine learning?) problem

Question

Hello,

The problem I have has got me puzzled. The problem is explained below,

There is a container, for example lets say which has a volume of "V". The container needs to be filled with various types of boxes, where each type has a unique size (volume), for example lets say

Box Type A - has a volume of K Box Type B - has a volume of L

Now the problem is that there is a requirement to find out whats the maximum number of boxes of both types which could be fit into the container (combination of both boxes)

To simplify lets say that "W" and "R" are quantities, then we get (K * W) + (L * R) = V

AND how the cartons(boxes) should be stacked up in the container.

For example the first row (by row I mean when the boxes are laid x co-ordinate wise) of boxes in the container should contain 4 stacks (starting from the floor of the container) of "Box Type A" and the topmost two stacks (nearing the top ceiling of the container) with "Box Type B" (By stacks I mean when the boxes are laid on top of each other [z co-ordinate wise]).Thereafter a new row is laid after the previous one is complete till the whole container is full.

The problem is what is the best way to layout these boxes in the container as to utilize all (or most) of the space in the container, and pack in the maximum possible number of boxes which can be a combination of 1 or more (max around 5 type of boxes in one container).

The program should simply take the inputs of the types and details of the boxes, the container and walla you get a full detailed analysis.

The problem is that I have not touched the area of machine learning or solving this kind of problem. I would appreciate if I was given advice on as what algorithm/s to use, where to start learning to solving this problem and such, whats the best way to approach this, any helpful machine learning libraries to use, etc.

Regards, Milinda

Answer 1

You might want to have a look at the answer to this question:

http://stackoverflow.com/questions/2329492/box-stacking-problem

Answer 2

If you really mean machine learning, rather than pre-programming an algorithm then I think that's really difficult. Simple trial and error approaches are going to perform really badly when the number of boxes becomes large.

I wonder whether it's worth looking at the approaches taken in programming computers to play Go. There's been a lot of progress in applying Monte Carlo methods especialy in the end-game, which is a similar kind of combinatorial problem to your packing problem. See This reference.

Answer 3

To solve this purely with machine learning is a bad idea. The reason being this is a deterministic problem, and other forms of AI are better suited for this. But, if your only option is machine learning I would look into reinforcement learning using a least-square error Gradient to Optimize with. It is one of the easier ways to understand machine learning, and applies to your problem, since it is deterministic. If at all possible use other algorithms to supplement the machine learning.

Answer 4

This problem is a variant of linear optimization called integer linear optimization link at wikipedia. This problem is known to be NP-hard in general, so most solutions out there are iterative. See the references in the article for further discussion

EDIT: I would suggest to look at LPSOLVE which already offers a lgpl solver library