Solving Chip Stacking Problems with Lagrange Multipliers

[cjSlominski]

My math is a little rusty and I want someone to identify the category of problem (Lagrange Multipliers, Simplex method, ...) I have, so that I can read up on the topic and familiarize myself with the technique.

To make the problem simple, let's say I have some number of chips of varying thickness. I want to place these chips in some number of stacks so that the stacks are as close as possible to being the same height. How do I do that?

I'll define "close as possible" as the sum of the squares of the difference between actual stack heights and the nominal stack height is minimized. Note the nominal stack height is the total thickness of all chips divided by the number of stacks.

Thanks,
Chris

 

[arildno]

Sounds awful.
Suppose M is the number of chips, and N the number of stacks you want.
Let S_{N,i} be a set of disjoint subsets of your chips, so that each chip is member of one such subset. i indexes the S-sets.
To each S_{N,i} you may assign a number L_{N,i} which measures how close the stacks are in height.

Thus, you are to compare the L_{N,i} from all S_{N,i}, and find the least one.

I'm not sure there will exist a simple formula for this.

Perhaps there exists some clever combinatorial technique to do this effectively regardless of chip thicknesses, but I don't know about it.