# Arranging cubes in bins to minimize expected variation ratio

I am working on an optimization problem.

Let's say we have a grid of bins where solid metal cubes could be placed. We have a number of colored metal cubes to be arranged in the bins.

Each of these cubes weighs 1kg. But the weight could change slightly over time due to natural phenomena like rusting and becomes 1kg + delta(x,y) where x, y are the co-ordinates of the location of the cube. We are interested in making sure the ratio between the total weight of one color to another remains same over time. The total weight of a color is the sum of weights of all cubes of that color.

Observations from past experiments say that delta(x,y) is not completely random. It can be thought of as k0 + k1*x + k2*y + k3*x^2 + k4*y^2 + k5*x*y where the constants k0 k1 k2 ... are unknown at the time of arranging the cubes. But in all cases k0 > k1 > k3 > k5 and k0 > k2 > k4 > k5 We can assume k0/k1 as c1, k1/k3 as c2... and cn > 1 for all n. k1 and k2 are unrelated. Note that the constants k0, k1, k2 are same for all cubes.

This observation lets us cancel out certain terms in delta(x, y) by arranging carefully. For example, if we arrange two red balls and two blue balls as R B B R, we can expect the linear terms to cancel.

Take for example a grid of 3x3. Initially, we have the empty grid:

[ ]  [ ]  [ ]
[ ]  [ ]  [ ]
[ ]  [ ]  [ ]


and a number of metal cubes to be placed. As an example, let's say we are to arrange one red cube, two blue cubes, four green cubes and two dummy cubes.

Metal cubes to be placed:

1 x R
2 x B
3 x G
2 x *


One possible arrangement could be:

B * G
G R G
G * B


Given a set of values for c1, c2 etc, there is one arrangement that must be the best. I am trying to model a cost function which indicates the expected variation between the two colors. Then choose the arrangement that has minimum cost by iterating through all possible arrangement.

I am looking for some advice on how to model the expected variation between two colors.

Also, any advice on reducing the search space. Usually, the size of the grid is around 10x10 and can grow as big as 15x10 in some rare cases. There are, usually, about 3 to 10 colors of cubes (number of cubes 10x10 to 15x10) to be filled.

• What do you mean by "expected variation"? if it's an expected value, the expected value of what random variable? I don't see any randomization in your question -- it looks like everything is deterministic. Also I don't know what a "variation" is. Can you edit your question to formulate everything more carefully, and define your terms? – D.W. May 19 '17 at 15:58
• Each cube should ideally be 1kg. But over time it varies slightly based on the location it is in the grid. The variation is not completely random. It can be modeled as a sum of terms that vary linearly with x etc. The values of k0,k1,k2 are not known. – Suresh May 19 '17 at 16:29
• Thanks for the edits. That partly helps. I still don't understand how you want to define/quantify "variation", precisely. Can you give a mathematical specification of the variation, in terms of the total weights of the two colors? Is it the ratio of the total weights? Difference? Something else? And I still don't understand what you mean by "expected variation". Is there a random process somewhere? Does "expected" mean expected value of a random variable? Or do you just mean "the variation as calculated by the model in the question"? – D.W. May 19 '17 at 17:45
• Also, what do you mean when you say you want to "model a cost function"? What would an answer look like? It seems like you already provided a model (based on the constants c1, c2, etc.) -- is there something wrong with that model? We probably can't tell you how to construct a model of the physics of your setup, because that requires knowledge of physics or some non-CS subject, but if you can formulate your problem in precise terms that doesn't require non-CS knowledge, we might be able to suggest algorithms for it. – D.W. May 19 '17 at 17:48
• I'm a bit puzzled when you say "the variation is not completely random, but can be modelled..." Does that mean it is partly random? Or that it's random in reality but we can pretend it isn't for this question? When you say it can be modeled as such-and-such, does that mean you are willing to ignore the random part and just use the formula listed in your question (based on c1, c2)? Or is there also an extra random term that should be added on? If so, can you describe that random process, and the distribution of all random variables, and how they affect the final weight and variation? – D.W. May 19 '17 at 17:50