Conference rusure::math

    re .0
    
    Sounds like a variation on the knapsack problem. DIR/TIT=SACK came up
    with topic 377 which may be of some help. I don't know what the state
    of the art is on this problem.
    
    From a practical standpoint a lot depends on the number of pallets (n).
    If 2^n is a feasible number of computations then brute force works.
    
    Aside: Let's say I had a feasible algorithm for finding an exact set of
    pallets that comes to 15kg. Would this globally minimise the number of
    groups? That is, can anyone construct an example where blindly filling
    your early groups with exactly 15kg leads to more groups overall?
    
    Other asides: Is the knapsack problem known to be "hard"? Or if it is
    not known whether is is easy or hard, is it in NP-complete?

Dear Ica,

	I guess you're not looking for a guaranteed 100% optimal solution.
This is a notoriously hard problem mathematically, as Derek points out in
.1. However, to put an algorithm together that will be good for your particular
problem most of the time, is probably not too hard. And not worth sweating too
much.

	The basic approach would be the common sense one of trying to locate
the big pallets, before locating the small ones. Try to fill one pallet with a
few big weights, before placing something in an new pallet. However, the 
precise algorithm to be chosen would probably depend on other factors:

	(*) What is the rough pdf of weights?
	(*) What the ratio average_wt/max_pallet_weight?
	(*) What is the penalty cost if you happen to have one more pallet
than you theoretically need?
	(*) Is there any packing problem, for instance can you have 1 pallet
with two big weights on it, while another has lots of little ones?
	(*) Do you know all the weights at the beginning, or do they appear
as time goes on?
	(*) [Related, but not the same.] Does the packing have to be flexible 
to late orders arriving?

	You need to have someone look at typical real examples of the problem
that you are trying to solve. It'll be possible then to decide what makes
sense.

Cheers,
Andrew.

If the solution space is too large to search exhaustively, you might try
Simulated Annealing, which has proved useful for this kind of "combinational
minimization" problem.  (It's often used to allocate silicon real-estate on
chip, for example).  There's a pretty good description (with programs!) in
Chapter 10.9 of Numerical Recipes in C, Second Edition, ISBN 0-521-43108-5.

The choice of algorithm is motivated by the observation that slow cooling of
many substances can create very regular crystaline structures, which
represent the minimum energy state of the solid, even though this is only one
out of a very large number of possible states.  It sounds weird, but it often
works, particularly (as in this case) you don't necessarily want the absolute
best solution, but will settle for one that's close.

				-Michael

    Thanks for your input fellas,
    	We have an approximate solution that involves sorting into
    weight sequence and then allocating groups by attempting to add
    each pallet to the group if it will fit. Once it has 'busted' we go
    onto the next group. This is of course subject to practical
    considerations as .2 pointed out which will be more obvious once we get
    some real data. Minimising the standard deviation of the number of
    pallets in a group is one such consideration.
    
    Regards,
    Ica.   

I think that this is a set covering (packing or partitioning)
problem. The problem is NP (as mentioned by others). "Integer
and Combinatorial Optimization" by Nemhauser and Wolsey (spelling)
discusses this problem in detail. They also have a heuristic
for solving such problems (it seems to perform well in practice).
-Samer
[Posted by WWW Notes gateway]