Math problem

[acelli]

My problem sounds like a classic math problem but I do not know the solution.

I have between 4 and 50 boxes with different weights.  I want to distribute them as evenly as possible by weight (without regard to box count) across 4 pallets.

My current plan is to sort by weight and starting with the heaviest add to the pallet with the least weight. 

I think this works but cannot be certain.  The person who asked me to do this suggested I try all possible combination's but I can't think how to write that program.

I thought I would give all the math expert here a chance.  Let me know if you have any ideas.

Thanks,
Alan Elliott

[billhsln]

First thing I would do is calculate the total poundage of all the boxes and divide by 4, giving you an average per each of the 4 pallets you want to load.  From there putting the largest that will fit under that weight on each pallet until you run out of boxes or if you have left over start at the least weighted pallet  and add boxes until you go over the average.

Bill

[acelli]

I thought about that but suppose one box was heavier than the average...  which pallet would you put it on in the end?  Certainly that wouldn't result in the pallets being closest to each other in weight.

One of my friends believes this is a variation on the http://en.wikipedia.org/wiki/Knapsack_problem

I am not sure I agree since my problem only has one variable - weight.  It does not matter the size, shape or number of boxes per pallet (as long as it has at least one)

Alan

[REDEBOLT]

This is a classic problem in combinations and permutations.

Code Select Expand

                    n!
C(n,m) = -------------------
               m! * (n-m)!

where n! = 1*2*3*4*...(n-2)*(n-1)*n
and is called n factorial.

So 50 objects taken 4 at a time = 230,300.

The factorial function can be found on the windows calculator.

I think your original solution of sorting by weight would be the best.

[acelli]

So you believe the brute force method is the only solution to this problem... try all possible combination's where each pallet has at least 1 box and the smallest total deviation is the answer?

Alan

[acelli]

Sorry Bob.  I missed the last line of your post

I think your original solution of sorting by weight would be the best.

I think the solution I proposed will be close and possibly even correct.  Still I do not think it will be unacceptably long to perform the number of brute force compares you calculated but I can't picture how to code it and I am not sure if the result will be significantly different.   

Alan

[sapero]

Having 4 pallets each box can be assigned to, you need exact 2 bits, in order to assing a number 0,1,2,3 for each box.
Having up to 50 boxes, you'll need up to 50 [boxes] * 2 [bits] = 100 bits for a table.
With 100 bits, you have 2^100 = 1.2E30 of all possible combinations. Even in pure assembly code on modern CPU, it can take months to find the best combination.

This simple program demonstrates it (64 bit counter). After 60 seconds on 1.86GHz intel cpu the most significant 32-bits of the counter are 24 (from 4294967295 total). After 4294967295/24 = 178956970 [minutes], (124275 days, 340 years) the counter will overflow. And this in only 64 bit counter, and all what it does is incrementing the counter.

Code Select Expand

DWORD time = MILLISECS()
_asm
mov eax,0
mov edx,eax
align 4
go:
add eax,1
jnz go
add edx,1
jnz go
_endasm
time = MILLISECS() - time
MessageBox 0, using("done, time elapsed: # seconds", time/1000), ""

[Ionic Wind Support Team]

No, you can do it without brute force using minima and maxima (calculus).

Paul.

[billhsln]

Here is a program that will read in a file of numbers and then load pallets, might not be 100% and handle every case.  But it is a start.  Made a few more mods to the program to handle if average was not high enough.

Success is measured by all boxes have been assigned to pallets.

Added my file with numbers in it.

Bill

Note:  Boxes[x,0] = Weight, Boxes[x,1] = Original record number read, Boxes[x,2] = Pallet number box goes in

[celphick]

Consider the case of 48 boxes weighing 2 units and 1 box weighing 1 unit.
There is obviously no perfect solution. This would then be the general case.

So there have to be some compromises, sometimes.

The starting point for a computer program would need to involve a metric to evaluate the success of a particular combination of boxes.

Since the number of combinations is an integer, and moving from 1 combination to another is a discrete process, the use of calculus is not really an option.

Sapero has pointed out the difficulties due to processing times and the large number of combinations.

billhsln unfortunately did not supply his data file so his program terminated as I was unable to point it to the required data.


A practical approach might be as follows;

1. input the list of weights and count them for a generalization.

2. calculate the mean loading per pallet as a floating point number, though if it is an integer a perfect solution is possible, but not absolutely certain [necessary but not sufficient].

3. set up a metric as a function, namely the sum of the absolute difference [for each pallet] between the weight on  the pallet and this initial mean.
   [The squares could be used, butsome ot the following steps would not be as simple.]

4. load the pallet from the top of the list until the weight equals or exceeds the mean.

5. repeat for all the other pallets, except the last which will have a weight less than or equal to the mean.

6. if the weight of last pallet equals the mean, then the loading is done and we stop, otherwise

7. calculate the metric for the loading.

8. arrange the loads in order, the last loaded being the least.

9. take 2 pallets, say the heaviest and the lightest, and get the difference in weights.

10. if this difference is acceptably close to the weight of any item on the heavier pallet, move it to the other one.

11. if not, compare items on the pallets to find the differences. Take the difference is closest to the difference found in step 9, and swap the items involved.

12. repeat steps 10 & 11 using the other 2 pallets.

13. redo step 7 and compare with the previous metric. It should be less than or equal [only if no changes were made].

14. if happy, stop. Otherwise take a different pairing of pallets [there aren't many combinations of these], and repeat steps 11, 12 & 13.

At this stage you are probably as close to the optimum answer as you can get in a very short time.

[Boris]

Interesting problem. I like it. Here’s my attempt:

Visualise it like this: Line all the boxes up into one long â€ËÅ"snake’. Mentally adjust the sizes so that they are all the same height, but are different widths proportional to their weights. Now imagine dividing lines drawn at regular intervals to indicate the pallets. Like this:



The red numbers identify individual boxes. First you measure the distance between each pallet line and the closest box-weight-divider line. Like this:



Giving d1, d2, d3. Add these together and that is your â€ËÅ"error’ factor for this design. Now choose two boxes at random and swap them, creating a new design. Measure the new error factor, is it more than before or less? If more, then discard this design and try again from the previous design. If less, this is your new â€ËÅ"best design’. Swap two more boxes. Etc.

The error factor will get smaller and smaller over time until it refuses to get any smaller. (EG: If you have not found a better design in the last, say, 100 swaps, then you’re finished). That is your final design. An arbitrary minimum unit of weight must be chosen for the scale. The larger the unit, the lower the resolution, the fewer iterations will be necessary and the quicker the program will arrive at the optimal solution.

It’s not a mathematical solution, more of an algorithmic solution, but that’s how I think

[acelli]

Hello,

I wanted to thank everyone for their suggestions.  I demo'd my solution today to a very pleased audience.  This is what I did...

I sorted the boxes heaviest to lightest and placed the heaviest on the lightest pallet, then the next heaviest on the lightest pallet and so on until I was out of boxes. 

Then I took the heaviest and lightest pallets and generated a list of the combined weights of all possible pairs of boxes on each pallet.  Next I subtracted every pair on the lightest pallet from those on the heaviest pallet looking for the best swap which would reduce the heaviest pallet and increase the lightest pallet to make their weights together as close as possible.  Then I re-calculated the pallet weights to determine the new heaviest and lightest pallets and generated a new list of the combined weights of all possible pairs of boxes on each pallet.  I repeat this process until a swap does not exist which bring the heaviest and lightest closer together.

The whole thing only takes a second or two, even for 50+ boxes.  The program actually works better with more boxes.  I used SQLite for the sorting and to generate the list of possible pairs per pallet. 

On the sample data they provided the largest deviation between heaviest and lightest was 44/100's.  The best result was 3 of the 4 pallets matched exactly with the 4th 2/100's less than the other 3.

The program is not perfect.  On the sample with the largest deviation, I could manually identify a swap where moving all but one box on one pallet for a very heavy box on the other pallet would bring them closer together but nobody seemed to mind since they had been trying different combination's manually until now.

Anyway I just wanted to say thank you and share my happiness with those who might appreciate the solution.

Thanks,
Alan