Suggestions for fragment proposal algorithm

2
votes

I'm currently trying to solve the following problem, but am unsure which algorithm I should be using. Its in the area of mass identification.

I have a series of "weights", *w_i*, which can sum up to a total weight. The as-measured total weight has an error associated with it, so is thus inexact.

I need to find, given the total weight T, the closest k possible combinations of weights that can sum up to the total, where k is an input from the user. Each weight can be used multiple times.

Now, this sounds suspiciously like the bounded-integer multiple knapsack problem, however

  • it is possible to go over the weight, and
  • I also want all of the ranked solutions in terms of error

I can probably solve it using multiple sweeps of the knapsack problem, from weight-error->weight+error, by stepping in small enough increments, however it is possible if the increment is too large to miss certain weight combinations that could be used.

The number of weights is usually small (4 ->10 weights) and the ratio of the total weight to the mean weight is usually around 2 or 3

Does anyone know the names of an algorithm that might be suitable here?

2
algorithm
If there are only 4-10 weights, you can just brute-force it. - Bernhard Barker
Speed is a concern, as the problem needs to be solved repeatedly for differing inputs. Also, the total weight to minimum weight ratio can be quite high <200 - AlgQuery
How much of a concern? I estimate brute-forcing 10 or less elements should take less than a second. - Bernhard Barker
The method needs to be applied for 20->100 total weights, depending upon the measurement, and needs to be interactive. - AlgQuery
Can you use fractions of a weight, or only the full weight? - Regenschein

2 Answers

1
votes

Your problem effectively resembles the knapsack problem which is a NP-complete problem.

For really limited number of weights, you could run over every combinations with repetition followed by a sorting which gives you a quite high number of manipulations; at best: (n + k - 1)! / ((n - 1)! · k!) for the combination and n·log(n) for the sorting part.

Solving this kind of problem in a reasonable amount of time is best done by evolutionary algorithms nowadays.

If you take the following example from deap, an evolutionary algorithm framework in Python: ga_knapsack.py, you realise that by modifying lines 58-59 that automatically discards an overweight solution for something smoother (a linear relation, for instance), it will give you solutions close to the optimal one in a shorter time than brute force. Solutions are already sorted for you at the end, as you requested.

0
votes

As a first attempt I'd go for constraint programming (but then I almost always do, so take the suggestion with a pinch of salt):

  1. Given W=w_1, ..., w_i for weights and E=e_1,.., e_i for the error (you can also make it asymmetric), and T.
  2. Find all sets S (if the weights are unique, or a list) st sum w_1+e_1,..., w_k+e_k (where w_1, .., w_k \elem and e_1, ..., e_k \elem E) \approx T within some delta which you derive from k. Or just set it to some reasonably large value and decrease it as you are solving the constraints.

I just realise that you also want to parametrise the expression w_n op e_m over op \elem +, - (any combination of weights and error terms) and off the top of my head I don't know which constraint solver would allow you to do that. In any case, you can always fall back to prolog. It may not fly, especially if you have a lot of weights, but it will give you solutions quickly.