0

I've used Excel to do some linear programing, and I've found some Java libraries that can help with this, but I'm not sure linear programming is the right solution, or that the available libraries can handle what I'm trying to do.

I have a number of buckets, which will be different for each run of this program. for this run, let's say I have 8 buckets. I have several more objects. For this run, let's say I have 30 objects. Each object has a weight, which I know. I want to load the objects into the buckets, such that the sum of the objects in each bucket is as close as possible to equal.

I need identify which objects should be placed in which buckets to create this outcome.

From what I'm seeing in the documentation of JOptimizer and SCPSolver, I'm having trouble twisting this problem into a format that works.

My first problem is how to represent minimal variation in the sums of the buckets in a single problem. I thought maybe standard deviation of the sums would work. If I can get the sums to equal values, that works, but if not, standard deviation seems to allow for more than the minimum possible variability. I don't see how these libraries support standard deviation either. Is there a better way to structure this problem?

I also have the feeling I'm creating more constraints that necessary. I created a constraints for each combination of objects and buckets. The values of each constraint can either 0 or 1. 1 indicates that the object is placed in that bucket. Then, I have another constraint that sums each all buckets for each individual object, which must be 1. This ensures the object is placed in only 1 bucket. Then I can add the total of each bucket's objects by taking object weight * bucket presence, and summing the results. This seems like a more complex route than necessary.

Is this the best solution for this type of problem? What better ways exist?

Thanks!

Adam
  • 101
  • Are you interested in minimizing the deviations of the amount of objects or the weights ? – callculus42 Sep 18 '15 at 13:10
  • http://stackoverflow.com/questions/6669460/the-partition-problem -- might help. – uniquesolution Sep 18 '15 at 13:22
  • This sounds to me more like a dynamic programming problem, akin to the knapsack problem, than a linear programming one. I suspect that's the reason your linear programming solvers aren't proving immediately helpful. – Chris Kerridge Sep 18 '15 at 13:22
  • @calculus, I'm interested in making the buckets of equal weight. I'll read into he partition problem. – Adam Sep 18 '15 at 13:56
  • @Chris Kerridge I'm not familiar with the knapsack problem, but I'll look into that too. – Adam Sep 18 '15 at 13:56
  • @Adam I don't know that this problem can be reduced to the knapsack problem, but a similar strategy would work I think. Dynamic programming is essentially a caching brute-force strategy, especially useful for optimization problems. Very useful and worth learning about whether you employ it here or not. – Chris Kerridge Sep 18 '15 at 14:15
  • The knapsack problem doesn't look like the same problem. The partition problem is very similar, and is actually one variation of what I'm looking for. The more complex version that I really need is the partition problem without the constraint that the items must grouped into contagious sets. If I can achieve better balancing by putting arranging the items in a any order, I'd like to do that. Is there a more common name for this? – Adam Sep 18 '15 at 15:43

0 Answers0