2

I am looking for a fast solution for a multiple/multiobjective subset-sum problem.

As aditional restraints (which make a litte easier to calculate IMO) we can assume that all values included in the sum are positive and are all bound to a known limit value.

I know there is a O(NK) pseudopolynomial solution for a one-objective subset sum problem, I have implemented a solution based in wikipedia and in this stack exchange answer.

Explaining this problem in other way, I have two sets of positive numbers which limit is known. For each value A in the first set there is a combination of values in the second set that sums up to A. Knowning a priori that all values in the first set have a corresponding and not conflicting combination of values associated in the second set, is there a known, fast way to calculate which elements in the second set are associated with each of the first set values?

Community
  • 1
  • 1
viniciuscb
  • 123
  • 1
  • 7
  • What exactly do you mean by "not conflicting"? Do you mean each value in the second set is used to create only one of the values in A? Or do you, perhaps, mean each solution for a value in A is unique (i.e., only one subset of the second set will produce that value) or perhaps something else? – Jerry Coffin Jul 13 '12 at 20:29
  • @JerryCoffin, each value in the second set is used to create only one of the values in A. – viniciuscb Jul 13 '12 at 20:35
  • In a problem like this, there can be several combinations in the second set that can sum up to a value in the first set. The problem is that we must find one combination for each value in the first set and all found combinations use exclusive values in the second set - this is what I mean when I say they do not conflict. – viniciuscb Jul 13 '12 at 20:41

1 Answers1

1

I think your problem is a variation of multiset constraint problem which I studied in my master thesis.

In this project, I designed an algorithm which searches in the DP table to find the solution. It is not Pseudo polynomial but I think it is fast enough in general cases.

I also implement a Python tool to solve these problems. Maybe you want to try it !

This tool called msat and it is maintained on github.

You can reference to msat.

Or simply use pip to install it(it is a Python3 tool):

$ pip install msat

There are also slides of introduction: slides.

If you want to know the details, reference to thesis.

dokelung
  • 206
  • 1
  • 5