I am a total novice, but I think what I'm looking for is help with an optimization problem.

I have a set of about 26 items, each with a certain value. I want to distribute these items into 8 groups as equally as possible, having granted that a perfectly equal distribution is not possible because of the individual item values. I think, one way of measuring how equally the items have been divided into groups is by taking the standard deviation of the sums of the values of the items in each group.

Is there a package in R that could help me to minimize the standard deviation of these sums by altering the allotment of items to groups?

FWIW, this is an 'estate division' problem, in which each item has a known value, and no bidding/auctioning can take place.

  • I think this is a purely mathematical (optimization) problem rather than a statistical one and as such probably belongs on math.SE rather than here. If you can make it statistical (see th coverage of stats.SE in the FAQ), then it might fit here. If you'd like it moved, you can flag it and a moderator will shift it for you. – Glen_b Feb 18 '13 at 23:54
  • (But please don't cross-post) – Glen_b Feb 19 '13 at 0:05
  • Do you mean numerically equally as possible, or both numerically and in terms of the number of items? I ask because if the number of items in each group is bounded only between 1 and 19 it seems like the space in which to optimize is kind of huge. – russellpierce Feb 19 '13 at 1:04
  • 1
    I don't know Glen_b, it seems like just in the identification of the number of possible states (excluding groups that are essentially aliases for each other) which is a sort of precursor to developing an optimization methods is itself a relatively complex problem worthy of CV consideration. – russellpierce Feb 19 '13 at 1:06
  • 1
    @drnexus thanks for your comment. i mean in terms of 'weights' or 'item values', not in terms of the number of items. so, in the optimal solution, group 1 could have just one item of sufficient value, while the other 7 groups each have, say, 3. – dubhousing Feb 19 '13 at 14:39

There are a variety of measures of evenness of the sums (group-values). For example, one alternative is to try to minimize the difference between the biggest and smallest sum.

Minimizing the standard deviation is the same as minimizing the variance.

However, the mean of the sums is fixed, so minimizing the variance is the same as minimizing the sum of squares of the group-values.

This is getting a bit closer to a 'standard' optimization problem.

It's somewhat related to the Job-shop scheduling problem and a number of other problems.

There are various job-scheduling programs, some of which might be able to work on your problem, but they usually tend to focus on minimizing the maximum completion time (that would correspond to minimizing the largest set, which may not give you a good solution).

From a quick glance it looks like the partitions package in R can generate partitions for you - but unfortunately the number of possible partitions is going to be huge in your case, so you may have to settle for some approximate algorithm (in a similar fashion to some of the bin-packing problems, for example). [Approximate algorithms can often generate very good solutions.]

There may be some value in this:

http://www.colorado.edu/education/DMP/fair_division.html

but it does seem to look mostly at bidding-solutions.

If you have a mixed problem (that is, one which includes divisible assets like cash), your job should be easier.

There might be something to be said for starting with some reasonable solution and using say tabu-search or simulated annealing or something to try to improve it.

If this is a one-off problem can you post the some numbers proportional to the values (it won't affect anything to multiply them by some arbitrary constant like 1.375) - it might help to have something concrete to think about.

  • 1
    x <- restrictedparts(26,8,include.zero=FALSE) #gives 288 possible item counts for partitioning groups... then there is also the valid permutations of assigning actual assets to the 1:26 ordering... so, there are... a lot of possible allocations. Not very promising. – russellpierce Feb 19 '13 at 1:27
  • @drknexus Yes, I calculated a very weak lower bound on the problem size ...and went 'Ack!' -- without some really good way to cut things down, it looks like a pretty large problem. With additional details of the specifics (e.g. if some items will clearly be by themselves or can only be paired with a couple of things), enough of the solution might be "obvious" that the remaining search space is cut way down. – Glen_b Feb 19 '13 at 1:53
  • The most obvious constraint is the largest single item. One group will have to be of at least that value. That should cut down a lot of the parameter space as no group can have a combination of items that is substantially less than the value of that single item. – russellpierce Feb 19 '13 at 3:34
  • Notably a sum of squares optimization may yield different results than a sum of absolute deviations optimization. It isn't clear that SS is better that abs dev in this context. We could probably toss a lot of options based on individual means being a certain distance from the optimal grand mean of the value of 26 items divided by 8... but testing that condition alone would be time consuming. – russellpierce Feb 19 '13 at 3:49
  • @Glen_b Indeed, it is a one-off problem. My grandmother passed away and left behind a lot of valuable jewelry. I will post proportional values later on. – dubhousing Feb 19 '13 at 14:52

This is known as the 'partition problem' and is preferably solved by a dynamic programming approach. You can read about it in Chapter 8.5 of "The Algorithm Design Manual" by Steven Skiena. And you can find an R implementation for minimizing the variance in the thread "optimization challenge" of R-help in January 2010.

EDIT: I'm sorry, I somehow misread the task, assuming the sequence of values would play a role. As a kind of compensation I will show how I would solve this as a multiple knapsack problem, reducing knapsack capacities until no solution is found.

library(adagio)                     # contains a multiple knapsack solver
set.seed(7531)
w <- sample(1:100, 26)              # 26 items used as weights (integers)
p <- rep(1, 26)                     # with equal profits all

t <- 200; k <- rep(t, 8)            # 8 knapsacks with equal capacities
sol <- mknapsack(p, w, k, bck = 1)  # starting with capacity 200
while (all(sol$ksack > 0)) {        # diminish capacity until not all
    t <- t-1; k <- rep(t, 8)        # items can be packed
    Sol <- sol                      # keep the last feasible solution
    sol <- mknapsack(p, w, k, bck = -1)
}                                   # will take a few seconds to minutes

y <- numeric(8)                     # find weight in each knapsack
for (i in 1:8) y[i] <- sum(w[Sol$ksack == i])
y                                   # 161 161 160 161 161 161 159 161

This will not in all cases lead to a solution of smallest variance, but come very close to it.

I would argue that one solution (I cannot prove it is optimal) for such a problem is arranging the items from smallest to largest and then going from there. In such an arrangement the items next to each other will always give the least possible contribution to the overall SD.

I had a similar problem and solved it this way. I did however have the benefit of a constant group size. The method for your problem would still have to evaluate all the possible groups..

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.