Redistribution Algorithm

Question

I've one thousand buckets of different sizes. Each bucket consists of red and blue balls of different weights. I know that 60 percent of the total ball weight comes from the red balls and 40 percent from the blue balls. Each bucket has a random number of balls, a random distriution of red and blue balls, and random distribution of ball weights.

I need to do a redistribution of the balls so each bucket consists of 59-61 percent ball weight from red balls, and 39-41 percent ball weight from blue balls. Each bucket should have exactly the same weight as it had before the redistribution, but the number of balls in each bucket doesn't have to match the earlier number. It's possible to split balls, but each split has a cost.

Can anyone point me in the direction of an algorithm?

Thanks.

Answer 1

One possible way is to formulate a Mixed Integer Programming Problem in the following way. I am not sure, there may be other much more efficient solutions.

Say there are a total of R red balls and B blue balls, each with a weight of r1, r2, ..rR and b1, b2, ...bB respectively.

Say Rij is the fraction of the red ball i that is assigned to bucket j. RBINij is a binary number that is 1 if Rij > 0 and 0 otherwise. We want to make as many Rij's 0 (and RBINij's 0) as possible for minimum number of cuts.

Similarly Bij is the fraction of the blue ball i that is assigned to bucket j. BBINij is a binary number that is 1 if Bij > 0 and 0 otherwise. We want to make as many Bij's 0 (and BBINij's 0) as possible for minimum number of cuts.

Constraints:
summation over i( wi*Rij ) <= 1.564*summation over i( wi*Bij ) (61-39 ratio) { for all j buckets }
summation over i( wi*Rij ) >= 1.439*summation over i( wi*Bij ) (59-41 ratio) { for all j buckets }
RBINij >= Rij
BBINij >= Bij
+ maybe more constraints like the total weight etc.

Objective Function:
Minimize( Ci*summation over i(RBINij + BBINij) )