Hi all

I am hoping this is a known problem.

Suppose we have N bins where N is maybe as large as two or three thousand. We have M items and M is as large as 5*N.

Every item must belong to one and only one bin (to keep things simple <g>), no bin is empty, a bin can hold any number of items but typically would hold 1,2,3...about 10 at maximum.

We ONLY know the characteristics of the bins and the items, and we wish to solve for the allocation of items to bins ie for every item, which bin does it belong to? We can accept some errors .. that is, a small number of misallocation of items to bins.

We are lucky in that we have TWO characteristics for each item, cube and weight (both integers), and the corresponding totals for each bin. Cube and weight vary very widely and at random, so you won't find many duplicates on these parameters at the item or the bin level. Cube and weight are not highly correlated.

OK, how do we do this.?

I hope it is not integer programming or linear programming because

a) I have no idea how to implement such things (in Delphi)

b) I am under the impression that such approaches are slow for large numbers of variables

c) I would like, eventually, to extend the solution to a situation where the variables (cube and weight) are measured with error

d) I have a suspicion that because we have two "dependent" variables, a solution should be easier to find .. and maybe I could have more in the future (ie change how things are measured, again maybe with error)

e) and in the future I would like some sort of estimate as to how likley it is that a particular item belongs to a bin (maybe that is too big an ask)

Is a GA going to work?

ok, over to the experts

for a,b chosen so that a*weight+b*volume is always unique

You can do this in pseudo-polynomial time with a branch and bound algorithm

For an approximation algorithm, we'd need to know what counts as close,

transforming the problem in the above manner may not transform the closeness criterion

in a way that lets standard bin-packing approximation algorithms find close solutions to your problem when they find close solutions to the transformed problem.